Document Open Access Logo

Partitioning Vectors into Quadruples: Worst-Case Analysis of a Matching-Based Algorithm

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

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2018.45.pdf
  • Filesize: 439 kB
  • 12 pages

Document Identifiers

Author Details

Annette M. C. Ficker
  • Faculty of Economics and Business, KU Leuven, Leuven, Belgium
Thomas Erlebach
  • Department of Informatics, University of Leicester, Leicester, United Kingdom
Matús Mihalák
  • Department of Data Science and Knowledge Engineering, Maastricht University, Maastricht, The Netherlands
Frits C. R. Spieksma
  • Department of Mathematics and Computer Science, Eindhoven University of Technology, Eindhoven, The Netherlands

Funding

  • Erlebach, Thomas: Supported by a study leave granted by University of Leicester.

Cite As Get BibTex

Annette M. C. Ficker, Thomas Erlebach, Matús Mihalák, and Frits C. R. Spieksma. Partitioning Vectors into Quadruples: Worst-Case Analysis of a Matching-Based Algorithm. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 45:1-45:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.ISAAC.2018.45

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 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.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Approximation algorithms
Keywords
  • approximation algorithm
  • matching
  • clustering problem

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. J. Barát and D. Gerbner. Edge-Decomposition of Graphs into Copies of a Tree with Four Edges. The Electronic Journal of Combinatorics, 21(1):1-55, 2014. Google Scholar
  2. C. Berge. Sur le couplage maximum d'un graphe. Comptes Rendus de l'Académie des Sciences, 247:258-259, 1958. Google Scholar
  3. T. Dokka, M. Bougeret, V. Boudet, R. Giroudeau, and F.C.R. Spieksma. Approximation algorithms for the wafer to wafer integration problem. In Proceedings of the 10th International Workshop on Approximation and Online Algorithms (WAOA 2012), volume 7846 of LNCS, pages 286-297. Springer, 2013. Google Scholar
  4. T. Dokka, Y. Crama, and F.C.R. Spieksma. Multi-dimensional vector assignment problems. Discrete Optimization, 14:111-125, 2014. Google Scholar
  5. F. Dong, W. Yan, and F. Zhang. On the number of perfect matchings of line graphs. Discrete Applied Mathematics, 161(6):794-801, 2013. Google Scholar
  6. Annette M. C. Ficker, Thomas Erlebach, Matús Mihalák, and Frits C. R. Spieksma. Partitioning Vectors into Quadruples: Worst-Case Analysis of a Matching-Based Algorithm. CoRR, abs/1807.01962, 2018. URL: http://arxiv.org/abs/1807.01962.
  7. A. Figueroa, A. Goldstein, T. Jiang, M. Kurowski, A. Lingas, and M. Persson. Approximate clustering of fingerprint vectors with missing values. In Proceedings of the 2005 Australasian Symposium on Theory of Computing (CATS 2005), volume 41 of CRPIT, pages 57-60. Australian Computer Society, 2005. Google Scholar
  8. D.S. Hochbaum and A. Levin. Covering the edges of bipartite graphs using K_2,2 graphs. Theoretical Computer Science, 411(1):1-9, 2010. Google Scholar
  9. M. Jünger, G. Reinelt, and W.R. Pulleyblank. On partitioning the edges of graphs into connected subgraphs. Journal of Graph Theory, 9(4):539-549, 1985. Google Scholar
  10. S. Onn and L.J. Schulman. The vector partition problem for convex objective functions. Mathematics of Operations Research, 26(3):583-590, 2001. Google Scholar
  11. S. Reda, G. Smith, and L. Smith. Maximizing the functional yield of wafer-to-wafer 3-D integration. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 17(9):1357-1362, 2009. Google Scholar
  12. C. Thomassen. Edge-decompositions of highly connected graphs into paths. In Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg, volume 78, pages 17-26. Springer, 2008. Google Scholar
  13. V.V. Vazirani. Approximation Algorithms. Springer-Verlag, Inc., New York, USA, 2001. Google Scholar
  14. D.P. Williamson and D.B. Shmoys. The Design of Approximation Algorithms. Cambridge University Press, New York, USA, 1st edition, 2011. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact