Paper Info
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.
Year
DOI
Venue
2018
10.4230/LIPIcs.ISAAC.2018.45
ISAAC
DocType
Volume
Citations 
Conference
abs/1807.01962
0
PageRank 
References 
Authors
0.34
8
4
Name
Order
Citations
PageRank
Annette M. C. Ficker121.70
Thomas Erlebach21233102.74
Matús Mihalák315122.49
Frits C. R. Spieksma459158.84