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 3/2-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.
@InProceedings{ficker_et_al:LIPIcs.ISAAC.2018.45, author = {Ficker, Annette M. C. and Erlebach, Thomas and Mihal\'{a}k, Mat\'{u}s and Spieksma, Frits C. R.}, title = {{Partitioning Vectors into Quadruples: Worst-Case Analysis of a Matching-Based Algorithm}}, booktitle = {29th International Symposium on Algorithms and Computation (ISAAC 2018)}, pages = {45:1--45:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-094-1}, ISSN = {1868-8969}, year = {2018}, volume = {123}, editor = {Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.45}, URN = {urn:nbn:de:0030-drops-99933}, doi = {10.4230/LIPIcs.ISAAC.2018.45}, annote = {Keywords: approximation algorithm, matching, clustering problem} }
Feedback for Dagstuhl Publishing