Show simple item record

dc.contributor.author
Ashlagi, Itai
dc.contributor.author
Azar, Yossi
dc.contributor.author
Charikar, Moses
dc.contributor.author
Chiplunkar, Ashish
dc.contributor.author
Geri, Ofir
dc.contributor.author
Kaplan, Haim
dc.contributor.author
Makhijani, Rahul
dc.contributor.author
Wang, Yuyi
dc.contributor.author
Wattenhofer, Roger
dc.contributor.editor
Jansen, Klaus
dc.contributor.editor
Rolim, José D.P.
dc.contributor.editor
Williamson, David
dc.contributor.editor
Vempala, Santosh S.
dc.date.accessioned
2019-08-20T07:07:23Z
dc.date.available
2017-10-06T05:05:09Z
dc.date.available
2017-12-14T11:53:18Z
dc.date.available
2019-08-20T07:07:23Z
dc.date.issued
2017-08
dc.identifier.isbn
978-3-95977-044-6
en_US
dc.identifier.issn
1868-8969
dc.identifier.other
10.4230/LIPIcs.APPROX-RANDOM.2017.1
en_US
dc.identifier.uri
http://hdl.handle.net/20.500.11850/192442
dc.identifier.doi
10.3929/ethz-b-000192442
dc.description.abstract
In the min-cost bipartite perfect matching with delays (MBPMD) problem, requests arrive online at points of a finite metric space. Each request is either positive or negative and has to be matched to a request of opposite polarity. As opposed to traditional online matching problems, the algorithm does not have to serve requests as they arrive, and may choose to match them later at a cost. Our objective is to minimize the sum of the distances between matched pairs of requests (the connection cost) and the sum of the waiting times of the requests (the delay cost). This objective exhibits a natural tradeoff between minimizing the distances and the cost of waiting for better matches. This tradeoff appears in many real-life scenarios, notably, ride-sharing platforms. MBPMD is related to its non-bipartite variant, min-cost perfect matching with delays (MPMD), in which each request can be matched to any other request. MPMD was introduced by Emek et al. (STOC'16), who showed an O(log^2(n)+log(Delta))-competitive randomized algorithm on n-point metric spaces with aspect ratio Delta. Our contribution is threefold. First, we present a new lower bound construction for MPMD and MBPMD. We get a lower bound of Omega(sqrt(log(n)/log(log(n)))) on the competitive ratio of any randomized algorithm for MBPMD. For MPMD, we improve the lower bound from Omega(sqrt(log(n))) (shown by Azar et al., SODA'17) to Omega(log(n)/log(log(n))), thus, almost matching their upper bound of O(log(n)). Second, we adapt the algorithm of Emek et al. to the bipartite case, and provide a simplified analysis that improves the competitive ratio to O(log(n)). The key ingredient of the algorithm is an O(h)-competitive randomized algorithm for MBPMD on weighted trees of height h. Third, we provide an O(h)-competitive deterministic algorithm for MBPMD on weighted trees of height h. This algorithm is obtained by adapting the algorithm for MPMD by Azar et al. to the apparently more complicated bipartite setting.
en_US
dc.format
application/pdf
en_US
dc.language.iso
en
en_US
dc.publisher
Schloss Dagstuhl - Leibniz-Zentrum für Informatik
en_US
dc.rights.uri
http://creativecommons.org/licenses/by/3.0/
dc.subject
Online algorithms with delayed service
en_US
dc.subject
Bipartite matching
en_US
dc.subject
Competitive analysis
en_US
dc.title
Min-Cost Bipartite Perfect Matching with Delays
en_US
dc.type
Conference Paper
dc.rights.license
Creative Commons Attribution 3.0 Unported
ethz.book.title
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)
en_US
ethz.journal.title
Leibniz International Proceedings in Informatics
ethz.journal.volume
81
en_US
ethz.journal.abbreviated
Leibniz int. proc. inform.
ethz.pages.start
1:1
en_US
ethz.pages.end
1:20
en_US
ethz.size
20 p.
en_US
ethz.version.deposit
publishedVersion
en_US
ethz.event
20th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2017), and the 21st International Workshop on Randomization and Computation (RANDOM 2017)
en_US
ethz.event.location
Berkeley, CA, USA
en_US
ethz.event.date
August 16-18, 2017
en_US
ethz.identifier.scopus
ethz.publication.place
Dagstuhl
en_US
ethz.publication.status
published
en_US
ethz.leitzahl
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02140 - Dep. Inf.technologie und Elektrotechnik / Dep. of Inform.Technol. Electrical Eng.::02640 - Inst. f. Technische Informatik und Komm. / Computer Eng. and Networks Lab.::03604 - Wattenhofer, Roger / Wattenhofer, Roger
en_US
ethz.leitzahl
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02140 - Dep. Inf.technologie und Elektrotechnik / Dep. of Inform.Technol. Electrical Eng.::02640 - Inst. f. Technische Informatik und Komm. / Computer Eng. and Networks Lab.::03604 - Wattenhofer, Roger / Wattenhofer, Roger
en_US
ethz.leitzahl.certified
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02140 - Dep. Inf.technologie und Elektrotechnik / Dep. of Inform.Technol. Electrical Eng.::02640 - Inst. f. Technische Informatik und Komm. / Computer Eng. and Networks Lab.::03604 - Wattenhofer, Roger / Wattenhofer, Roger
ethz.leitzahl.certified
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02140 - Dep. Inf.technologie und Elektrotechnik / Dep. of Inform.Technol. Electrical Eng.::02640 - Inst. f. Technische Informatik und Komm. / Computer Eng. and Networks Lab.::03604 - Wattenhofer, Roger / Wattenhofer, Roger
ethz.date.deposited
2017-10-06T05:05:09Z
ethz.source
SCOPUS
ethz.eth
yes
en_US
ethz.availability
Open access
en_US
ethz.rosetta.installDate
2017-12-14T11:53:21Z
ethz.rosetta.lastUpdated
2020-02-15T20:46:18Z
ethz.rosetta.versionExported
true
ethz.COinS
ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.atitle=Min-Cost%20Bipartite%20Perfect%20Matching%20with%20Delays&rft.jtitle=Leibniz%20International%20Proceedings%20in%20Informatics&rft.date=2017-08&rft.volume=81&rft.spage=1:1&rft.epage=1:20&rft.issn=1868-8969&rft.au=Ashlagi,%20Itai&Azar,%20Yossi&Charikar,%20Moses&Chiplunkar,%20Ashish&Geri,%20Ofir&rft.isbn=978-3-95977-044-6&rft.genre=proceeding&rft_id=info:doi/978-3-95977-044-6&rft.btitle=Approximation,%20Randomization,%20and%20Combinatorial%20Optimization.%20Algorithms%20and%20Techniques%20(APPROX/RANDOM%202017)
 Search via SFX

Files in this item

Thumbnail

Publication type

Show simple item record