Document Open Access Logo

Robust Assignments via Ear Decompositions and Randomized Rounding

Authors David Adjiashvili, Viktor Bindewald, Dennis Michaels

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2016.71.pdf
  • Filesize: 471 kB
  • 14 pages

Document Identifiers

Author Details

David Adjiashvili
Viktor Bindewald
Dennis Michaels

Cite As Get BibTex

David Adjiashvili, Viktor Bindewald, and Dennis Michaels. Robust Assignments via Ear Decompositions and Randomized Rounding. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 71:1-71:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ICALP.2016.71

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.

Subject Classification

Keywords
  • robust optimization
  • matching theory
  • ear decomposition
  • randomized rounding
  • approximation algorithm

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. D. Adjiashvili. Non-uniform robust network design in planar graphs. In Proc. of APPROX, pages 61-77, 2015. Google Scholar
  2. D. Adjiashvili, S. Stiller, and R. Zenklusen. Bulk-robust combinatorial optimization. Math Program, 149(1-2):361-390, 2014. Google Scholar
  3. H. Aissi, C. Bazgan, and D. Vanderpooten. Complexity of the min-max and min-max regret assignment problems. Oper Res Lett, 33(6):634-640, 2005. Google Scholar
  4. H. Aissi, C. Bazgan, and D. Vanderpooten. Min–max and min–max regret versions of combinatorial optimization problems: A survey. Eur J Oper Res, 197(2):427-438, 2009. Google Scholar
  5. D. Bertsimas, D.B. Brown, and C. Caramanis. Theory and applications of robust optimization. SIAM review, 53:464-501, 2011. Google Scholar
  6. R.C. Brigham, F. Harary, E.C. Violin, and J. Yellen. Perfect-matching preclusion. Congressus Numerantium, 174:185-192, 2005. 00042. Google Scholar
  7. G. Carello and E. Lanzarone. A cardinality-constrained robust model for the assignment problem in Home Care services. Eur J Oper Res, 236(2):748-762, 2014. Google Scholar
  8. S. Chechik, M. Langberg, D. Peleg, and L. Roditty. Fault-tolerant spanners for general graphs. In Proc. of STOC, pages 435-444, 2009. Google Scholar
  9. S. Chechik and D. Peleg. Robust fault tolerant uncapacitated facility location. In Proc. of STACS, pages 191-202, 2010. Google Scholar
  10. C. Chekuri. Routing and network design with robustness to changing or uncertain traffic demands. ACM SIGACT News, 38(3):106-129, 2007. Google Scholar
  11. E. Cheng, L. Lesniak, M.J. Lipman, and L. Liptak. Conditional matching preclusion sets. Information Sciences, 179(8):1092-1101, 2009. 00039. Google Scholar
  12. J. Cheriyan, A. Sebo, and Z. Szigeti. Improving on the 1.5-Approximation of a Smallest 2-Edge Connected Spanning Subgraph. SIAM J Discrete Math, 14(2):170-180, 2001. Google Scholar
  13. M.H. de Carvalho and J. Cheriyan. An O(VE) algorithm for ear decompositions of matching-covered graphs. In Proc. of SODA, pages 415-423, 2005. Google Scholar
  14. V.G. Deineko and G.J. Woeginger. On the robust assignment problem under a fixed number of cost scenarios. Oper Res Lett, 34(2):175-179, 2006. Google Scholar
  15. M. Dinitz and R. Krauthgamer. Fault-tolerant spanners: better and simpler. In Proc. of PODC, pages 169-178. ACM, 2011. Google Scholar
  16. M.C. Dourado, D. Meierling, L.D. Penso, D. Rautenbach, F. Protti, and A.R. de Almeida. Robust recoverable perfect matchings. Networks, 66(3):210-213, 2015. Google Scholar
  17. R. Fujita, Y. Kobayashi, and K. Makino. Robust matchings and matroid intersections. In Proc. of ESA, pages 123-134. Springer, 2010. Google Scholar
  18. H. N. Gabow, M. X. Goemans, É. Tardos, and D. P. Williamson. Approximating the smallest k-edge connected spanning subgraph by LP-rounding. In Proc. of SODA, pages 562-571, 2005. Google Scholar
  19. F. Grandoni, R. Ravi, M. Singh, and R. Zenklusen. New approaches to multi-objective optimization. Math Program, 146(1-2):525-554, 2014. Google Scholar
  20. M. Grötschel, L. Lovasz, and A. Schrijver. Geometric Algorithms and Combinatorial Optimization. Algorithms and Combinatorics. Springer Berlin Heidelberg, 1993. Google Scholar
  21. M. Hajiaghayi, N. Immorlica, and V.S. Mirrokni. Power optimization in fault-tolerant topology control algorithms for wireless multi-hop networks. In Proc. of MobiCom, pages 300-312. ACM, 2003. Google Scholar
  22. R. Hassin and S. Rubinstein. Robust matchings. SIAM J Discrete Math, 15(4):530-537, 2002. Google Scholar
  23. W. Herroelen and R. Leus. Project scheduling under uncertainty: Survey and research potentials. Eur J Oper Res, 165(2):289-306, 2005. Google Scholar
  24. K. Jain. A factor 2 approximation algorithm for the generalized steiner network problem. Combinatorica, 21:39-60, 2001. Google Scholar
  25. K. Jain and V.V. Vazirani. An approximation algorithm for the fault tolerant metric facility location problem. In Proc. of APPROX, pages 177-183, 2000. Google Scholar
  26. P. Kouvelis and G. Yu. Robust discrete optimization and its applications, volume 14. Springer Science &Business Media, 1997. Google Scholar
  27. P. Laroche, F. Marchetti, S. Martin, and Z. Roka. Bipartite complete matching vertex interdiction problem: Application to robust nurse assignment. In Proc. of CoDIT, pages 182-187, 2014. Google Scholar
  28. L. Lovász and M.D. Plummer. Matching theory. North-Holland, Amsterdam, 1986. Google Scholar
  29. J. Plesník. Connectivity of regular graphs and the existence of 1-factors. Matematickỳ časopis, 22(4):310-318, 1972. Google Scholar
  30. A. Sebő and J. Vygen. Shorter tours by nicer ears: 7/5-approximation for the graph-tsp, 3/2 for the path version, and 4/3 for two-edge-connected subgraphs. Combinatorica, 5(34):597-629, 2014. Google Scholar
  31. C. Swamy and D. B. Shmoys. Fault-tolerant facility location. In Proc. of SODA, pages 735-736, 2003. Google Scholar
  32. C.S. Tang. Robust strategies for mitigating supply chain disruptions. International Journal of Logistics: Research and Applications, 9(1):33-45, 2006. Google Scholar
  33. G. Yu and J. Yang. On the robust shortest path problem. Computers & Operations Research, 25(6):457-468, 1998. Google Scholar
  34. R. Zenklusen. Matching interdiction. Discrete Appl Math, 158(15):1676-1690, 2010. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact