@inproceedings{7e7c72b752954370adf0e2b5f3fe7d88,

title = "Partitioning vectors into quadruples: Worst-case analysis of a matching-based algorithm",

abstract = " Consider a problem where 4k given vectors need to be partitioned into k clusters of four vectors each. A cluster of four vectors is called a quad, and the cost of a quad is the sum of the component-wise maxima of the four vectors in the quad. The problem is to partition the given 4k vectors into k quads with minimum total cost. We analyze a straightforward matching-based algorithm and prove that this algorithm is a 2 3 -approximation algorithm for this problem. We further analyze the performance of this algorithm on a hierarchy of special cases of the problem and prove that, in one particular case, the algorithm is a 5 4 -approximation algorithm. Our analysis is tight in all cases except one. ",

keywords = "And phrases approximation algorithm, Clustering problem, Matching",

author = "Ficker, {Annette M.C.} and Thomas Erlebach and Mat{\'u}{\v s} Mihal{\'a}k and Spieksma, {Frits C.R.}",

year = "2018",

month = dec,

day = "1",

doi = "10.4230/LIPIcs.ISAAC.2018.45",

language = "English",

series = "Leibniz International Proceedings in Informatics (LIPIcs)",

publisher = "Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik",

editor = "Wen-Lian Hsu and Der-Tsai Lee and Chung-Shou Liao",

booktitle = "Partitioning Vectors into Quadruples: Worst-Case Analysis of a Matching-Based Algorithm",

note = "29th International Symposium on Algorithms and Computation, ISAAC 2018 ; Conference date: 16-12-2018 Through 19-12-2018",

}