Mathematics > Optimization and Control
[Submitted on 11 Dec 2018 (v1), last revised 13 Dec 2018 (this version, v2)]
Title:Robust Multicovers with Budgeted Uncertainty
View PDFAbstract:The Min-$q$-Multiset Multicover problem presented in this paper is a special version of the Multiset Multicover problem. For a fixed positive integer $q$, we are given a finite ground set $J$, an integral demand for each element in $J$ and a collection of subsets of $J$. The task is to choose sets of the collection (multiple choices are allowed) such that each element in $J$ is covered at least as many times as specified by the demand of the element. In contrast to Multiset Multicover, in Min-$q$-Multiset Multicover each of the chosen subsets may only cover up to $q$ of its elements with multiple choices being allowed. Our main focus is a robust version of Min-$q$-Multiset Multicover, called Robust Min-$q$-Multiset Multicover, in which the demand of each element in $J$ may vary in a given interval with an additional budget constraint bounding the sum of the demands. Again, the task is to find a selection of subsets which is feasible for all admissible demands. We show that the non-robust version is NP-complete for $q$ greater than two, whereas the robust version is strongly NP-hard for any positive $q$. Furthermore, we present two solution approaches based on constraint generation and investigate the corresponding separation problems. We present computational results using randomly generated instances as well as instances emerging from the problem of locating emergency doctors.
Submission history
From: Manuel Streicher [view email][v1] Tue, 11 Dec 2018 14:06:09 UTC (1,062 KB)
[v2] Thu, 13 Dec 2018 09:15:51 UTC (1,062 KB)
Current browse context:
math.OC
References & Citations
Bibliographic and Citation Tools
Bibliographic Explorer (What is the Explorer?)
Connected Papers (What is Connected Papers?)
Litmaps (What is Litmaps?)
scite Smart Citations (What are Smart Citations?)
Code, Data and Media Associated with this Article
alphaXiv (What is alphaXiv?)
CatalyzeX Code Finder for Papers (What is CatalyzeX?)
DagsHub (What is DagsHub?)
Gotit.pub (What is GotitPub?)
Hugging Face (What is Huggingface?)
Papers with Code (What is Papers with Code?)
ScienceCast (What is ScienceCast?)
Demos
Recommenders and Search Tools
Influence Flower (What are Influence Flowers?)
CORE Recommender (What is CORE?)
arXivLabs: experimental projects with community collaborators
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.