Show simple item record

dc.contributor.author
Liu, Xingwu
dc.contributor.author
Pan, Zhida
dc.contributor.author
Wang, Yuyi
dc.contributor.author
Wattenhofer, Roger
dc.contributor.editor
Hsu, Wen-Lian
dc.contributor.editor
Lee, Der-Tsai
dc.contributor.editor
Liao, Chung-Shou
dc.date.accessioned
2019-04-09T06:00:55Z
dc.date.available
2019-04-09T06:00:55Z
dc.date.issued
2018
dc.identifier.isbn
978-3-95977-094-1
en_US
dc.identifier.issn
1868-8969
dc.identifier.other
10.4230/LIPIcs.ISAAC.2018.62
en_US
dc.identifier.uri
http://hdl.handle.net/20.500.11850/336832
dc.identifier.doi
10.3929/ethz-b-000292376
dc.description.abstract
We investigate the problem of Min-cost Perfect Matching with Delays (MPMD) in which requests are pairwise matched in an online fashion with the objective to minimize the sum of space cost and time cost. Though linear-MPMD (i.e., time cost is linear in delay) has been thoroughly studied in the literature, it does not well model impatient requests that are common in practice. Thus, we propose convex-MPMD where time cost functions are convex, capturing the situation where time cost increases faster and faster. Since the existing algorithms for linear-MPMD are not competitive any more, we devise a new deterministic algorithm for convex-MPMD problems. For a large class of convex time cost functions, our algorithm achieves a competitive ratio of O(k) on any k-point uniform metric space. Moreover, our deterministic algorithm is asymptotically optimal, which uncover a substantial difference between convex-MPMD and linear-MPMD which allows a deterministic algorithm with constant competitive ratio on any uniform metric space.
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 algorithm
en_US
dc.subject
online matching
en_US
dc.subject
convex function
en_US
dc.subject
competitive analysis
en_US
dc.subject
lower bound
en_US
dc.title
Impatient Online Matching
en_US
dc.type
Conference Paper
dc.rights.license
Creative Commons Attribution 3.0 Unported
ethz.book.title
29th International Symposium on Algorithms and Computation (ISAAC 2018)
en_US
ethz.journal.title
Leibniz International Proceedings in Informatics
ethz.journal.volume
123
en_US
ethz.journal.abbreviated
Leibniz int. proc. inform.
ethz.pages.start
62:1
en_US
ethz.pages.end
62:12
en_US
ethz.version.deposit
publishedVersion
en_US
ethz.event
29th International Symposium on Algorithms and Computation (ISAAC 2018)
en_US
ethz.event.location
Jiaoxi, Taiwan
en_US
ethz.event.date
December 16-19, 2018
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.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
en_US
ethz.date.deposited
2018-09-28T10:00:56Z
ethz.source
FORM
ethz.source
SCOPUS
ethz.eth
yes
en_US
ethz.availability
Open access
en_US
ethz.rosetta.installDate
2019-04-09T06:01:23Z
ethz.rosetta.lastUpdated
2020-02-15T18:21:40Z
ethz.rosetta.versionExported
true
dc.identifier.olduri
http://hdl.handle.net/20.500.11850/292376
dc.identifier.olduri
http://hdl.handle.net/20.500.11850/336641
ethz.COinS
ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.atitle=Impatient%20Online%20Matching&rft.jtitle=Leibniz%20International%20Proceedings%20in%20Informatics&rft.date=2018&rft.volume=123&rft.spage=62:1&rft.epage=62:12&rft.issn=1868-8969&rft.au=Liu,%20Xingwu&Pan,%20Zhida&Wang,%20Yuyi&Wattenhofer,%20Roger&rft.isbn=978-3-95977-094-1&rft.genre=proceeding&rft_id=info:doi/978-3-95977-094-1&rft.btitle=29th%20International%20Symposium%20on%20Algorithms%20and%20Computation%20(ISAAC%202018)
 Search via SFX

Files in this item

Thumbnail

Publication type

Show simple item record