Document Open Access Logo

Preprocessing Under Uncertainty: Matroid Intersection

Authors Stefan Fafianie, Eva-Maria C. Hols, Stefan Kratsch, Vuong Anh Quyen

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2016.35.pdf
  • Filesize: 490 kB
  • 14 pages

Document Identifiers

Author Details

Stefan Fafianie
Eva-Maria C. Hols
Stefan Kratsch
Vuong Anh Quyen

Cite As Get BibTex

Stefan Fafianie, Eva-Maria C. Hols, Stefan Kratsch, and Vuong Anh Quyen. Preprocessing Under Uncertainty: Matroid Intersection. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 35:1-35:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.MFCS.2016.35

Abstract

We continue the study of preprocessing under uncertainty that was initiated independently by Assadi et al. (FSTTCS 2015) and Fafianie et al. (STACS 2016). Here, we are given an instance of a tractable problem with a large static/known part and a small part that is dynamic/uncertain, and ask if there is an efficient algorithm that computes an instance of size polynomial in the uncertain part of the input, from which we can extract an optimal solution to the original instance for all (usually exponentially many) instantiations of the uncertain part. 
 
In the present work, we focus on the Matroid Intersection problem. Amongst others we present a positive preprocessing result for the important case of finding a largest common independent set in two linear matroids. Motivated by an application for intersecting two gammoids we also revisit Maximum Flow. There we tighten a lower bound of Assadi et al. and give an alternative positive result for the case of low uncertain capacity that yields a Maximum Flow instance as output rather than a matrix.

Subject Classification

Keywords
  • preprocessing
  • uncertainty
  • maximum flow
  • matroid intersection

Metrics

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

References

  1. Martin Aigner and Thomas A Dowling. Matching theory for combinatorial geometries. Transactions of the American Mathematical Society, 158(1):231-245, 1971. Google Scholar
  2. Sepehr Assadi, Sanjeev Khanna, Yang Li, and Val Tannen. Dynamic sketching for graph optimization problems with applications to cut-preserving sketches. In Prahladh Harsha and G. Ramalingam, editors, 35th IARCS Annual Conference on Foundation of Software Technology and Theoretical Computer Science, FSTTCS 2015, December 16-18, 2015, Bangalore, India, volume 45 of LIPIcs, pages 52-68. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2015. URL: http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2015.52.
  3. Dimitris Bertsimas, David B. Brown, and Constantine Caramanis. Theory and applications of robust optimization. SIAM Review, 53(3):464-501, 2011. URL: http://dx.doi.org/10.1137/080734510.
  4. Hans-Georg Beyer and Bernhard Sendhoff. Robust optimization-a comprehensive survey. Computer methods in applied mechanics and engineering, 196(33):3190-3218, 2007. Google Scholar
  5. Leonora Bianchi, Marco Dorigo, Luca Maria Gambardella, and Walter J Gutjahr. A survey on metaheuristics for stochastic combinatorial optimization. Natural Computing: an international journal, 8(2):239-287, 2009. Google Scholar
  6. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. URL: http://dx.doi.org/10.1007/978-3-319-21275-3.
  7. George B. Dantzig. Linear programming under uncertainty. Management Science, 50(12-Supplement):1764-1769, 2004. URL: http://dx.doi.org/10.1287/mnsc.1040.0261.
  8. Reinhard Diestel. Graph theory (Graduate texts in mathematics). Springer Heidelberg, 2005. Google Scholar
  9. Randall Dougherty, Chris Freiling, and Kenneth Zeger. Network coding and matroid theory. Proceedings of the IEEE, 99(3):388-405, 2011. Google Scholar
  10. Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, 2013. URL: http://dx.doi.org/10.1007/978-1-4471-5559-1.
  11. Jack Edmonds. Submodular functions, matroids, and certain polyhedra. Combinatorial structures and their applications, pages 69-87, 1970. Google Scholar
  12. Stefan Fafianie, Stefan Kratsch, and Vuong Anh Quyen. Preprocessing under uncertainty. In Nicolas Ollinger and Heribert Vollmer, editors, 33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016, February 17-20, 2016, Orléans, France, volume 47 of LIPIcs, pages 33:1-33:13. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.STACS.2016.33.
  13. Harold N Gabow and Ying Xu. Efficient theoretic and practical algorithms for linear matroid intersection problems. Journal of Computer and System Sciences, 53(1):129-147, 1996. Google Scholar
  14. J. F. Geelen. Matching theory. Lecture Notes from the Euler Institute for Discrete Mathematics and Its Applications, 2001. Google Scholar
  15. Nicholas J. A. Harvey. Algebraic structures and algorithms for matching and matroid problems. In 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 21-24 October 2006, Berkeley, California, USA, Proceedings, pages 531-542. IEEE Computer Society, 2006. URL: http://dx.doi.org/10.1109/FOCS.2006.8.
  16. Stefan Kratsch and Magnus Wahlström. Representative sets and irrelevant vertices: New tools for kernelization. In 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012, pages 450-459. IEEE Computer Society, 2012. URL: http://dx.doi.org/10.1109/FOCS.2012.46.
  17. Stefan Kratsch and Magnus Wahlström. Compression via matroids: A randomized polynomial kernel for odd cycle transversal. ACM Transactions on Algorithms, 10(4):20:1-20:15, 2014. URL: http://dx.doi.org/10.1145/2635810.
  18. Eugene L Lawler. Matroid intersection algorithms. Mathematical programming, 9(1):31-56, 1975. Google Scholar
  19. Dániel Marx. A parameterized view on matroid optimization problems. Theor. Comput. Sci., 410(44):4471-4479, 2009. URL: http://dx.doi.org/10.1016/j.tcs.2009.07.027.
  20. Kazuo Murota. Matrices and matroids for systems analysis, volume 20. Springer Science &Business Media, 2009. Google Scholar
  21. James Oxley. Matroid Theory. Oxford University Press, 2011. Google Scholar
  22. Marcin Pilipczuk, Michal Pilipczuk, Piotr Sankowski, and Erik Jan van Leeuwen. Network sparsification for Steiner problems on planar and bounded-genus graphs. In FOCS 2014, pages 276-285. IEEE Computer Society, 2014. URL: http://dx.doi.org/10.1109/FOCS.2014.37.
  23. Jacob T. Schwartz. Fast probabilistic algorithms for verification of polynomial identities. J. ACM, 27(4):701-717, 1980. URL: http://dx.doi.org/10.1145/322217.322225.
  24. Nobuaki Tomizawa and Masao Iri. Algorithm for determining rank of a triple matrix product axb with application to problem of discerning existence of unique solution in a network. Electronics &Communications in Japan, 57(11):50-57, 1974. Google Scholar
  25. Magnus Wahlström. Abusing the Tutte Matrix: An Algebraic Instance Compression for the K-set-cycle Problem. In Natacha Portier and Thomas Wilke, editors, 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013), volume 20 of Leibniz International Proceedings in Informatics (LIPIcs), pages 341-352, Dagstuhl, Germany, 2013. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: http://dx.doi.org/10.4230/LIPIcs.STACS.2013.341.
  26. Dominic JA Welsh. Matroid theory. Courier Corporation, 2010. Google Scholar
  27. Richard Zippel. Probabilistic algorithms for sparse polynomials. In Edward W. Ng, editor, Symbolic and Algebraic Computation, EUROSAM '79, An International Symposiumon Symbolic and Algebraic Computation, Marseille, France, June 1979, Proceedings, volume 72 of Lecture Notes in Computer Science, pages 216-226. Springer, 1979. URL: http://dx.doi.org/10.1007/3-540-09519-5_73.
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