Partitioning vectors into quadruples: Worst-case analysis of a matching-based algorithm

Annette M.C. Ficker, Thomas Erlebach, Matúš Mihalák, Frits C.R. Spieksma

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

9 Downloads (Pure)

Samenvatting

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.

Originele taal-2Engels
TitelPartitioning Vectors into Quadruples: Worst-Case Analysis of a Matching-Based Algorithm
RedacteurenWen-Lian Hsu, Der-Tsai Lee, Chung-Shou Liao
Plaats van productieWadern
UitgeverijSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Aantal pagina's12
ISBN van elektronische versie9783959770941
DOI's
StatusGepubliceerd - 1 dec 2018
Evenement29th International Symposium on Algorithms and Computation, ISAAC 2018 - Hotel Royal Chiaohsi, Jiaoxi, Yilan, Taiwan
Duur: 16 dec 201819 dec 2018

Publicatie series

NaamLeibniz International Proceedings in Informatics (LIPIcs)
Volume123
ISSN van geprinte versie1868-8969

Congres

Congres29th International Symposium on Algorithms and Computation, ISAAC 2018
LandTaiwan
StadJiaoxi, Yilan
Periode16/12/1819/12/18

Vingerafdruk Duik in de onderzoeksthema's van 'Partitioning vectors into quadruples: Worst-case analysis of a matching-based algorithm'. Samen vormen ze een unieke vingerafdruk.

  • Citeer dit

    Ficker, A. M. C., Erlebach, T., Mihalák, M., & Spieksma, F. C. R. (2018). Partitioning vectors into quadruples: Worst-case analysis of a matching-based algorithm. In W-L. Hsu, D-T. Lee, & C-S. Liao (editors), Partitioning Vectors into Quadruples: Worst-Case Analysis of a Matching-Based Algorithm [45] (Leibniz International Proceedings in Informatics (LIPIcs); Vol. 123). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ISAAC.2018.45