Constrained Minimum-k-Star Clustering and its application to the consolidation of farmland

Steffen Borgwardt; Andreas Brieden; Peter Gritzmann

doi:10.1007/s12351-009-0041-y

Constrained Minimum-k-Star Clustering and its application to the consolidation of farmland

Steffen Borgwardt
, Andreas Brieden
, Peter Gritzmann

Chair of Geometry

Technical University of Munich
Universität der Bundeswehr München

Research output: Contribution to journal › Article › peer-review

15 Scopus citations

Abstract

The present paper introduces and studies a new combinatorial clustering model for the consolidation of farmland. While the general problem turns out to be NP-hard even in quite restricted cases, the Size-restricted Minimum-k-Star Group Partition problem is solvable in polynomial time. Based on this tractability result, we derive a general approximation algorithm which, as the mathematical analysis and economic evaluation shows, performs well in theory and practice.

Original language	English
Pages (from-to)	1-17
Number of pages	17
Journal	Operational Research
Volume	11
Issue number	1
DOIs	https://doi.org/10.1007/s12351-009-0041-y
State	Published - May 2011

Keywords

0-1-Integer programming
Clustering
Combinatorial optimization
Land consolidation
Mathematical programming
Partition

Access to Document

10.1007/s12351-009-0041-y

Cite this

@article{afbb3937a80b4e54a3d04255076ace12,

title = "Constrained Minimum-k-Star Clustering and its application to the consolidation of farmland",

abstract = "The present paper introduces and studies a new combinatorial clustering model for the consolidation of farmland. While the general problem turns out to be NP-hard even in quite restricted cases, the Size-restricted Minimum-k-Star Group Partition problem is solvable in polynomial time. Based on this tractability result, we derive a general approximation algorithm which, as the mathematical analysis and economic evaluation shows, performs well in theory and practice.",

keywords = "0-1-Integer programming, Clustering, Combinatorial optimization, Land consolidation, Mathematical programming, Partition",

author = "Steffen Borgwardt and Andreas Brieden and Peter Gritzmann",

year = "2011",

month = may,

doi = "10.1007/s12351-009-0041-y",

language = "English",

volume = "11",

pages = "1--17",

journal = "Operational Research",

issn = "1109-2858",

publisher = "Springer Verlag",

number = "1",

}

TY - JOUR

T1 - Constrained Minimum-k-Star Clustering and its application to the consolidation of farmland

AU - Borgwardt, Steffen

AU - Brieden, Andreas

AU - Gritzmann, Peter

PY - 2011/5

Y1 - 2011/5

N2 - The present paper introduces and studies a new combinatorial clustering model for the consolidation of farmland. While the general problem turns out to be NP-hard even in quite restricted cases, the Size-restricted Minimum-k-Star Group Partition problem is solvable in polynomial time. Based on this tractability result, we derive a general approximation algorithm which, as the mathematical analysis and economic evaluation shows, performs well in theory and practice.

AB - The present paper introduces and studies a new combinatorial clustering model for the consolidation of farmland. While the general problem turns out to be NP-hard even in quite restricted cases, the Size-restricted Minimum-k-Star Group Partition problem is solvable in polynomial time. Based on this tractability result, we derive a general approximation algorithm which, as the mathematical analysis and economic evaluation shows, performs well in theory and practice.

KW - 0-1-Integer programming

KW - Clustering

KW - Combinatorial optimization

KW - Land consolidation

KW - Mathematical programming

KW - Partition

UR - https://www.scopus.com/pages/publications/79953044699

U2 - 10.1007/s12351-009-0041-y

DO - 10.1007/s12351-009-0041-y

M3 - Article

AN - SCOPUS:79953044699

SN - 1109-2858

VL - 11

SP - 1

EP - 17

JO - Operational Research

JF - Operational Research

IS - 1

ER -

Constrained Minimum-k-Star Clustering and its application to the consolidation of farmland

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this