LIPIcs.ICALP.2019.83.pdf
- Filesize: 0.49 MB
- 14 pages
Document
The Minimum Cost Query Problem on Matroids with Uncertainty Areas
Authors
Arturo I. Merino 
,
José A. Soto
-
Part of:
Volume:
46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Colloquium on Automata, Languages, and Programming (ICALP) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2019-07-04
File
Document Identifiers
Author Details
- Dept. of Mathematical Engineering and CMM, Universidad de Chile & UMI-CNRS 2807, Santiago, Chile
Cite AsGet BibTex
Arturo I. Merino and José A. Soto. The Minimum Cost Query Problem on Matroids with Uncertainty Areas. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 83:1-83:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ICALP.2019.83
https://doi.org/10.4230/LIPIcs.ICALP.2019.83
Abstract
We study the minimum weight basis problem on matroid when elements' weights are uncertain. For each element we only know a set of possible values (an uncertainty area) that contains its real weight. In some cases there exist bases that are uniformly optimal, that is, they are minimum weight bases for every possible weight function obeying the uncertainty areas. In other cases, computing such a basis is not possible unless we perform some queries for the exact value of some elements.
Our main result is a polynomial time algorithm for the following problem. Given a matroid with uncertainty areas and a query cost function on its elements, find the set of elements of minimum total cost that we need to simultaneously query such that, no matter their revelation, the resulting instance admits a uniformly optimal base. We also provide combinatorial characterizations of all uniformly optimal bases, when one exists; and of all sets of queries that can be performed so that after revealing the corresponding weights the resulting instance admits a uniformly optimal base.
Subject Classification
ACM Subject Classification
- Mathematics of computing → Matroids and greedoids
Keywords
- Minimum spanning tree
- matroids
- uncertainty
- queries
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Richard Bruce, Michael Hoffmann, Danny Krizanc, and Rajeev Raman. Efficient Update Strategies for Geometric Computing with Uncertainty. Theory Comput. Syst., 38(4):411-423, 2005. URL: http://dx.doi.org/10.1007/s00224-004-1180-4.
- George Charalambous and Michael Hoffmann. Verification Problem of Maximal Points under Uncertainty. In Thierry Lecroq and Laurent Mouchard, editors, Combinatorial Algorithms - 24th International Workshop, IWOCA 2013, Rouen, France, July 10-12, 2013, Revised Selected Papers, volume 8288 of Lecture Notes in Computer Science, pages 94-105. Springer, 2013. URL: http://dx.doi.org/10.1007/978-3-642-45278-9_9.
-
Thomas Erlebach and Michael Hoffmann. Query-competitive algorithms for computing with uncertainty. Bulletin of EATCS, 2(116), 2015.
- Thomas Erlebach, Michael Hoffmann, and Frank Kammer. Query-competitive algorithms for cheapest set problems under uncertainty. Theor. Comput. Sci., 613:51-64, 2016. URL: http://dx.doi.org/10.1016/j.tcs.2015.11.025.
- Thomas Erlebach, Michael Hoffmann, Danny Krizanc, Matús Mihal'ák, and Rajeev Raman. Computing Minimum Spanning Trees with Uncertainty. In Susanne Albers and Pascal Weil, editors, 25th International Symposium on Theoretical Aspects of Computer Science, volume 1 of Leibniz International Proceedings in Informatics (LIPIcs), pages 277-288, Dagstuhl, Germany, February 2008. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: http://dx.doi.org/10.4230/LIPIcs.STACS.2008.1358.
- Tomás Feder, Rajeev Motwani, Liadan O'Callaghan, Chris Olston, and Rina Panigrahy. Computing shortest paths with uncertainty. J. Algorithms, 62(1):1-18, 2007. URL: http://dx.doi.org/10.1016/j.jalgor.2004.07.005.
- Tomás Feder, Rajeev Motwani, Rina Panigrahy, Chris Olston, and Jennifer Widom. Computing the Median with Uncertainty. SIAM J. Comput., 32(2):538-547, 2003. URL: http://dx.doi.org/10.1137/S0097539701395668.
- Manoj Gupta, Yogish Sabharwal, and Sandeep Sen. The Update Complexity of Selection and Related Problems. Theory Comput. Syst., 59(1):112-132, 2016. URL: http://dx.doi.org/10.1007/s00224-015-9664-y.
- Simon Kahan. A Model for Data in Motion. In Proceedings of the Twenty-third Annual ACM Symposium on Theory of Computing, STOC '91, pages 265-277, New York, NY, USA, 1991. ACM. URL: http://dx.doi.org/10.1145/103418.103449.
- Adam Kasperski and Pawel Zielinski. An approximation algorithm for interval data minmax regret combinatorial optimization problems. Inf. Process. Lett., 97(5):177-180, 2006. URL: http://dx.doi.org/10.1016/j.ipl.2005.11.001.
- Adam Kasperski and Pawel Zielinski. On combinatorial optimization problems on matroids with uncertain weights. European Journal of Operational Research, 177(2):851-864, 2007. URL: http://dx.doi.org/10.1016/j.ejor.2005.12.033.
- Stein Krogdahl. The dependence graph for bases in matroids. Discrete Mathematics, 19(1):47-59, 1977. URL: http://dx.doi.org/10.1016/0012-365X(77)90118-2.
- Nicole Megow, Julie Meißner, and Martin Skutella. Randomization Helps Computing a Minimum Spanning Tree under Uncertainty. SIAM Journal on Computing, 46(4):1217-1240, January 2017. URL: http://dx.doi.org/10.1137/16M1088375.
-
James G. Oxley. Matroid theory. Oxford University Press, 1992.
-
Alexander Schrijver. Combinatorial optimization: polyhedra and efficiency, volume 24. Springer Science &Business Media, 2003.
- Hande Yaman, Oya Ekin Karasan, and Mustafa Ç. Pinar. The robust spanning tree problem with interval data. Oper. Res. Lett., 29(1):31-40, 2001. URL: http://dx.doi.org/10.1016/S0167-6377(01)00078-5.