License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2019.83
URN: urn:nbn:de:0030-drops-106592
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10659/
Go to the corresponding LIPIcs Volume Portal

Merino, Arturo I. ; Soto, José A.

The Minimum Cost Query Problem on Matroids with Uncertainty Areas

pdf-format:
LIPIcs-ICALP-2019-83.pdf (0.5 MB)

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.

BibTeX - Entry

@InProceedings{merino_et_al:LIPIcs:2019:10659,
  author =	{Arturo I. Merino and Jos{\'e} A. Soto},
  title =	{{The Minimum Cost Query Problem on Matroids with Uncertainty Areas}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{83:1--83:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Christel Baier and Ioannis Chatzigiannakis and Paola Flocchini and Stefano Leonardi},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/10659},
  URN =		{urn:nbn:de:0030-drops-106592},
  doi =		{10.4230/LIPIcs.ICALP.2019.83},
  annote =	{Keywords: Minimum spanning tree, matroids, uncertainty, queries}
}

Keywords: Minimum spanning tree, matroids, uncertainty, queries
Collection: 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Issue Date: 2019
Date of publication: 04.07.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI