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.2016.71
URN: urn:nbn:de:0030-drops-62133
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6213/
Go to the corresponding LIPIcs Volume Portal

Adjiashvili, David ; Bindewald, Viktor ; Michaels, Dennis

Robust Assignments via Ear Decompositions and Randomized Rounding

pdf-format:
LIPIcs-ICALP-2016-71.pdf (0.5 MB)

Abstract

Many real-life planning problems require making a priori decisions before all parameters of the problem have been revealed. An important special case of such problem arises in scheduling and transshipment problems, where a set of jobs needs to be assigned to the available set of machines or personnel (resources), in a way that all jobs have assigned resources, and no two jobs share the same resource. In its nominal form, the resulting computational problem becomes the assignment problem.

This paper deals with the Robust Assignment Problem (RAP) which models situations in which certain assignments are vulnerable and may become unavailable after the solution has been chosen. The goal is to choose a minimum-cost collection of assignments (edges in the corresponding bipartite graph) so that if any vulnerable edge becomes unavailable, the remaining part of the solution contains an assignment of all jobs.

We develop algorithms and hardness results for RAP and establish several connections to well-known concepts from matching theory, robust optimization, LP-based techniques and combinations
thereof.

BibTeX - Entry

@InProceedings{adjiashvili_et_al:LIPIcs:2016:6213,
  author =	{David Adjiashvili and Viktor Bindewald and Dennis Michaels},
  title =	{{Robust Assignments via Ear Decompositions and Randomized Rounding}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{71:1--71:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-013-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{55},
  editor =	{Ioannis Chatzigiannakis and Michael Mitzenmacher and Yuval Rabani and Davide Sangiorgi},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6213},
  URN =		{urn:nbn:de:0030-drops-62133},
  doi =		{10.4230/LIPIcs.ICALP.2016.71},
  annote =	{Keywords: robust optimization, matching theory, ear decomposition, randomized rounding, approximation algorithm}
}

Keywords: robust optimization, matching theory, ear decomposition, randomized rounding, approximation algorithm
Collection: 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)
Issue Date: 2016
Date of publication: 23.08.2016

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