Multistage Matchings

Authors Evripidis Bampis, Bruno Escoffier, Michael Lampis, Vangelis Th. Paschos



PDF
Thumbnail PDF

File

LIPIcs.SWAT.2018.7.pdf
  • Filesize: 421 kB
  • 13 pages

Document Identifiers

Author Details

Evripidis Bampis
  • Sorbonne Université, CNRS, Laboratoire d'Informatique de Paris 6, LIP6, Paris, France
Bruno Escoffier
  • Sorbonne Université, CNRS, Laboratoire d'Informatique de Paris 6, LIP6, Paris, France
Michael Lampis
  • Université Paris-Dauphine, PSL Research University, CNRS, LAMSADE, Paris, France
Vangelis Th. Paschos
  • Université Paris-Dauphine, PSL Research University, CNRS, LAMSADE, Paris, France

Cite AsGet BibTex

Evripidis Bampis, Bruno Escoffier, Michael Lampis, and Vangelis Th. Paschos. Multistage Matchings. In 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 101, pp. 7:1-7:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.SWAT.2018.7

Abstract

We consider a multistage version of the Perfect Matching problem which models the scenario where the costs of edges change over time and we seek to obtain a solution that achieves low total cost, while minimizing the number of changes from one instance to the next. Formally, we are given a sequence of edge-weighted graphs on the same set of vertices V, and are asked to produce a perfect matching in each instance so that the total edge cost plus the transition cost (the cost of exchanging edges), is minimized. This model was introduced by Gupta et al. (ICALP 2014), who posed as an open problem its approximability for bipartite instances. We completely resolve this question by showing that Minimum Multistage Perfect Matching (Min-MPM) does not admit an n^{1-epsilon}-approximation, even on bipartite instances with only two time steps. Motivated by this negative result, we go on to consider two variations of the problem. In Metric Minimum Multistage Perfect Matching problem (Metric-Min-MPM) we are promised that edge weights in each time step satisfy the triangle inequality. We show that this problem admits a 3-approximation when the number of time steps is 2 or 3. On the other hand, we show that even the metric case is APX-hard already for 2 time steps. We then consider the complementary maximization version of the problem, Maximum Multistage Perfect Matching problem (Max-MPM), where we seek to maximize the total profit of all selected edges plus the total number of non-exchanged edges. We show that Max-MPM is also APX-hard, but admits a constant factor approximation algorithm for any number of time steps.

Subject Classification

ACM Subject Classification
  • Theory of computation → Approximation algorithms analysis
Keywords
  • Perfect Matching
  • Temporal Optimization
  • Multistage Optimization

Metrics

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

References

  1. Hyung-Chan An, Ashkan Norouzi-Fard, and Ola Svensson. Dynamic facility location via exponential clocks. ACM Trans. Algorithms, 13(2):21:1-21:20, 2017. Google Scholar
  2. Barbara M. Anthony and Anupam Gupta. Infrastructure leasing problems. In IPCO, volume 4513 of Lecture Notes in Computer Science, pages 424-438. Springer, 2007. Google Scholar
  3. Nicolas K. Blanchard and Nicolas Schabanel. Dynamic sum-radii clustering. In WALCOM, volume 10167 of Lecture Notes in Computer Science, pages 30-41. Springer, 2017. Google Scholar
  4. Niv Buchbinder, Shahar Chen, and Joseph Naor. Competitive analysis via regularization. In SODA, pages 436-444. SIAM, 2014. Google Scholar
  5. Niv Buchbinder, Shahar Chen, Joseph Naor, and Ohad Shamir. Unified algorithms for online learning and competitive analysis. Math. Oper. Res., 41(2):612-625, 2016. Google Scholar
  6. Edith Cohen, Graham Cormode, Nick G. Duffield, and Carsten Lund. On the tradeoff between stability and fit. ACM Trans. Algorithms, 13(1):7:1-7:24, 2016. Google Scholar
  7. David Eisenstat, Claire Mathieu, and Nicolas Schabanel. Facility location in evolving metrics. In ICALP (2), volume 8573 of Lecture Notes in Computer Science, pages 459-470. Springer, 2014. Google Scholar
  8. M. R. Garey, David S. Johnson, and Larry J. Stockmeyer. Some simplified NP-complete problems. In STOC, pages 47-63. ACM, 1974. Google Scholar
  9. Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979. Google Scholar
  10. Albert Gu, Anupam Gupta, and Amit Kumar. The power of deferral: Maintaining a constant-competitive steiner tree online. SIAM J. Comput., 45(1):1-28, 2016. Google Scholar
  11. Anupam Gupta, Kunal Talwar, and Udi Wieder. Changing bases: Multistage optimization for matroids and matchings. In ICALP (1), volume 8572 of Lecture Notes in Computer Science, pages 563-575. Springer, 2014. Google Scholar
  12. Viggo Kann. Maximum bounded 3-dimensional matching is MAX SNP-complete. Inf. Process. Lett., 37(1):27-35, 1991. Google Scholar
  13. Nicole Megow, Martin Skutella, José Verschae, and Andreas Wiese. The power of recourse for online MST and TSP. SIAM J. Comput., 45(3):859-880, 2016. Google Scholar
  14. Chandrashekhar Nagarajan and David P. Williamson. Offline and online facility leasing. Discrete Optimization, 10(4):361-370, 2013. Google Scholar
  15. Baruch Schieber, Hadas Shachnai, Gal Tamir, and Tami Tamir. A theory and algorithms for combinatorial reoptimization. Algorithmica, 80(2):576-607, 2018. 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