Document Open Access Logo

Optimal Matroid Partitioning Problems

Authors Yasushi Kawase, Kei Kimura, Kazuhisa Makino, Hanna Sumita

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2017.51.pdf
  • Filesize: 0.57 MB
  • 13 pages

Document Identifiers

Author Details

Yasushi Kawase
Kei Kimura
Kazuhisa Makino
Hanna Sumita

Cite As Get BibTex

Yasushi Kawase, Kei Kimura, Kazuhisa Makino, and Hanna Sumita. Optimal Matroid Partitioning Problems. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 51:1-51:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ISAAC.2017.51

Abstract

This paper studies optimal matroid partitioning problems for various objective functions. In the problem, we are given a finite set E and k weighted matroids (E, \mathcal{I}_i, w_i), i = 1, \dots, k, and our task is to find a minimum partition (I_1,\dots,I_k) of E such that I_i \in \mathcal{I}_i for all i. For each objective function, we give a polynomial-time algorithm or prove NP-hardness. In particular, for the case when the given weighted matroids are identical and the objective function is the sum of the maximum weight in each set (i.e., \sum_{i=1}^k\max_{e\in I_i}w_i(e)), we show that the problem is strongly NP-hard but admits a PTAS.

Subject Classification

Keywords
  • Matroids
  • Partitioning problem
  • PTAS
  • NP-hardness

Metrics

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

References

  1. L. Babel, H. Kellerer, and V. Kotov. The k-partitioning problem. Mathematical Methods of Operations Research, 47:59-82, 1998. Google Scholar
  2. R. E. Burkard and E. Yao. Constrained partitioning problems. Discrete Applied Mathematics, 28:21-34, 1990. Google Scholar
  3. S.-P. Chen, Y. He, and G. Lin. 3-partitioning for maximizing the minimum load. Journal of Combinatorial Optimization, 6:67-80, 2002. Google Scholar
  4. M. Dell'Amico and S. Martello. Bounds for the cardinality constrained p||c_max problem. Journal of Scheduling, 4:123-138, 2001. Google Scholar
  5. P. Dell'Olmo, P. Hansen, S. Pallottino, and G. Storchi. On uniform k-partition problems. Discrete Applied Mathematics, 150:121-139, 2005. Google Scholar
  6. I. Dinur and D. Steurer. Analytical approach to parallel repetition. In Proceedings of the Forty-sixth Annual ACM Symposium on Theory of Computing, pages 624-633. ACM, 2014. Google Scholar
  7. J. Edmonds. Minimum partition of a matroid into independent subsets. JOURNAL OF RESEARCH of the National Bureau of Standards - B. Mathematicsnd Mathematical Physics, 69B:67-72, 1965. Google Scholar
  8. J. Edmonds. Submodular functions, matroids, and certain polyhedra. In Combinatorial Structures and their Applications, pages 69-87. Gordon and Breach, New York, 1970. Google Scholar
  9. J. Edmonds and D. R. Fulkerson. Transversals and matroid partition. Journal of Research of the National Bureau of Standards, 69B:147-153, 1965. Google Scholar
  10. U. Feige, D. Peleg, and G. Kortsarz. The dense k-subgraph problem. Algorithmica, 29(3):410-421, 2001. Google Scholar
  11. A. Frank. A weighted matroid intersection algorithm. Journal of Algorithms, 2(4):328-336, 1981. Google Scholar
  12. M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman New York, 1979. Google Scholar
  13. Y. He, Z. Tan, J. Zhu, and E. Yao. k-partitioning problems for maximizing the minimum load. Computers and Mathematics with Applications, 46:1671-1681, 2003. Google Scholar
  14. Y. Kawase, K. Kimura, K. Makino, and H. Sumita. Optimal Matroid Partitioning Problems. arXiv preprints cs.DS/1710.00950, October 2017. URL: http://arxiv.org/abs/1710.00950.
  15. H. Kellerer and G. Woeginger. A tight bound for 3-partitioning. Discrete Applied Mathematics, 45:249-259, 1993. Google Scholar
  16. B. Korte and J. Vygen. Combinatorial Optimization: Theory and Algorithms. Springer, 2002. Google Scholar
  17. E. L. Lawler. Matroids with parity conditions: A new class of combinatorial optimization problems. Memo erl-m334, Electronics Research Laboratory, College of Engineering, UC Berkeley, Berkeley, CA, 1971. Google Scholar
  18. J. Lee, M. Sviridenko, and J. Vondrák. Matroid matching: The power of local search. SIAM Journal on Computing, 42(1):357-379, 2013. Google Scholar
  19. J. K. Lenstra, D. B. Shmoys, and É. Tardos. Approximation algorithms for scheduling unrelated parallel machines. Mathematical Programming, 46:259-271, 1990. Google Scholar
  20. W. Li and J. Li. Approximation algorithms for k-partitioning problems with partition matroid constraint. Optimization Letters, 8:1093-1099, 2014. Google Scholar
  21. L. Lovász. Matroid matching and some applications. Journal of Combinatorial Theory, Series B, 28(2):208-236, 1980. Google Scholar
  22. D. Moshkovitz. The projection games conjecture and the NP-hardness of ln n-approximating set-cover. Theory of Computing, 11(7):221-235, 2015. Google Scholar
  23. A. Schrijver. Combinatorial Optimization. Springer, 2003. Google Scholar
  24. J. Verschae and A. Wiese. On the configuration-LP for scheduling on unrelated machines. Journal of Scheduling, 17:371-383, 2014. Google Scholar
  25. B. Wu and E. Yao. k-partitioning problems with partition matroid constraint. Theoretical Computer Science, 374:41-48, 2007. Google Scholar
  26. B. Wu and E. Yao. Lower bounds and modified LPT algorithm for k-partitioning problems with partition matroid constraint. Applied Mathematics-A Journal of Chinese Universities, 23:1-8, 2008. 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