Show simple item record

dc.contributor.authorBampis, Evripidis
dc.contributor.authorEscoffier, Bruno
dc.contributor.authorLampis, Michael
dc.contributor.authorPaschos, Vangelis
dc.date.accessioned2020-07-22T13:48:34Z
dc.date.available2020-07-22T13:48:34Z
dc.date.issued2018
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/20960
dc.language.isoenen
dc.subjectMatchingen
dc.subjectOver time Optimizationen
dc.subjectMultistage Optimizationen
dc.subject.ddc005en
dc.titleMultistage Matchingsen
dc.typeCommunication / Conférence
dc.description.abstractenWe 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.en
dc.identifier.citationpages7:1--7:13en
dc.relation.ispartoftitle16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)en
dc.relation.ispartofeditorEppstein, David
dc.relation.ispartofpublnameSchloss Dagstuhl--Leibniz-Zentrum fuer Informatiken
dc.subject.ddclabelProgrammation, logiciels, organisation des donnéesen
dc.relation.ispartofisbn978-3-95977-068-2en
dc.relation.conftitle16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)en
dc.relation.confdate2018-06
dc.relation.confcityMalmoen
dc.relation.confcountrySwedenen
dc.relation.forthcomingnonen
dc.identifier.doi10.4230/LIPIcs.SWAT.2018.7en
dc.description.ssrncandidatenonen
dc.description.halcandidatenonen
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.relation.Isversionofjnlpeerreviewednonen
dc.relation.Isversionofjnlpeerreviewednonen
dc.date.updated2020-07-22T13:25:05Z
hal.person.labIds
hal.person.labIds989
hal.person.labIds989
hal.person.labIds989


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record