Fafianie, Stefan ;
Kratsch, Stefan ;
Anh Quyen, Vuong
Preprocessing Under Uncertainty
Abstract
In this work we study preprocessing for tractable problems when part of the input is unknown or uncertain. This comes up naturally if, e.g., the load of some machines or the congestion of some roads is not known far enough in advance, or if we have to regularly solve a problem over instances that are largely similar, e.g., daily airport scheduling with few charter flights. Unlike robust optimization, which also studies settings like this, our goal lies not in computing solutions that are (approximately) good for every instantiation. Rather, we seek to preprocess the known parts of the input, to speed up finding an optimal solution once the missing data is known.
We present efficient algorithms that given an instance with partially uncertain input generate an instance of size polynomial in the amount of uncertain data that is equivalent for every instantiation of the unknown part. Concretely, we obtain such algorithms for minimum spanning tree, minimum weight matroid basis, and maximum cardinality bipartite matching, where respectively the weight of edges, weight of elements, and the availability of vertices is unknown for part of the input. Furthermore, we show that there are tractable problems, such as small connected vertex cover, for which one cannot hope to obtain similar results.
BibTeX  Entry
@InProceedings{fafianie_et_al:LIPIcs:2016:5734,
author = {Stefan Fafianie and Stefan Kratsch and Vuong Anh Quyen},
title = {{Preprocessing Under Uncertainty}},
booktitle = {33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)},
pages = {33:133:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770019},
ISSN = {18688969},
year = {2016},
volume = {47},
editor = {Nicolas Ollinger and Heribert Vollmer},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/5734},
URN = {urn:nbn:de:0030drops57340},
doi = {10.4230/LIPIcs.STACS.2016.33},
annote = {Keywords: preprocessing, uncertainty, spanning trees, matroids, matchings}
}
2016
Keywords: 

preprocessing, uncertainty, spanning trees, matroids, matchings 
Seminar: 

33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)

Issue date: 

2016 
Date of publication: 

2016 