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

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

13 Downloads (Pure)

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.

Original languageEnglish
Title of host publicationPartitioning Vectors into Quadruples: Worst-Case Analysis of a Matching-Based Algorithm
EditorsWen-Lian Hsu, Der-Tsai Lee, Chung-Shou Liao
Place of PublicationWadern
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Number of pages12
ISBN (Electronic)9783959770941
DOIs
Publication statusPublished - 1 Dec 2018
Event29th International Symposium on Algorithms and Computation, ISAAC 2018 - Hotel Royal Chiaohsi, Jiaoxi, Yilan, Taiwan
Duration: 16 Dec 201819 Dec 2018

Publication series

NameLeibniz International Proceedings in Informatics (LIPIcs)
Volume123
ISSN (Print)1868-8969

Conference

Conference29th International Symposium on Algorithms and Computation, ISAAC 2018
CountryTaiwan
CityJiaoxi, Yilan
Period16/12/1819/12/18

Keywords

  • And phrases approximation algorithm
  • Clustering problem
  • Matching

Fingerprint Dive into the research topics of 'Partitioning vectors into quadruples: Worst-case analysis of a matching-based algorithm'. Together they form a unique fingerprint.

Cite this