File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1137/1.9781611975482.178
- Scopus: eid_2-s2.0-85066945429
Supplementary
-
Citations:
- Scopus: 0
- Appears in Collections:
Conference Paper: Tight Competitive Ratios of Classic Matching Algorithms in the Fully Online Model
Title | Tight Competitive Ratios of Classic Matching Algorithms in the Fully Online Model |
---|---|
Authors | |
Issue Date | 2019 |
Publisher | Society for Industrial and Applied Mathematics. |
Citation | Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2019), San Diego, CA, USA, 6-9 January 2019, p. 2875-2886 How to Cite? |
Abstract | Huang et al. (STOC 2018) introduced the fully online matching problem, a generalization of the classic online bipartite matching problem in that it allows all vertices to arrive online and considers general graphs. They showed that the ranking algorithm by Karp et al. (STOC 1990) is strictly better than 0.5-competitive and the problem is strictly harder than the online bipartite matching problem in that no algorithms can be (1 – 1/e)-competitive.
This paper pins down two tight competitive ratios of classic algorithms for the fully online matching problem. For the fractional version of the problem, we show that a natural instantiation of the water-filling algorithm is 2 –√2 ≈ 0.585-competitive, together with a matching hardness result. Interestingly, our hardness result applies to arbitrary algorithms in the edge-arrival models of the online matching problem, improving the state-of-art 1/1+1n2≈0.5906 upper bound. For integral algorithms, we show a tight competitive ratio of ≈ 0.567 for the ranking algorithm on bipartite graphs, matching a hardness result by Huang et al. (STOC 2018). Read More: https://epubs.siam.org/doi/10.1137/1.9781611975482.178 |
Persistent Identifier | http://hdl.handle.net/10722/273020 |
ISBN |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Huang, Z | - |
dc.contributor.author | Peng, B | - |
dc.contributor.author | Tang, Z | - |
dc.contributor.author | Tao, R | - |
dc.contributor.author | Wu, X | - |
dc.contributor.author | Zhang, Y | - |
dc.date.accessioned | 2019-08-06T09:21:02Z | - |
dc.date.available | 2019-08-06T09:21:02Z | - |
dc.date.issued | 2019 | - |
dc.identifier.citation | Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2019), San Diego, CA, USA, 6-9 January 2019, p. 2875-2886 | - |
dc.identifier.isbn | 9781611975482 | - |
dc.identifier.uri | http://hdl.handle.net/10722/273020 | - |
dc.description.abstract | Huang et al. (STOC 2018) introduced the fully online matching problem, a generalization of the classic online bipartite matching problem in that it allows all vertices to arrive online and considers general graphs. They showed that the ranking algorithm by Karp et al. (STOC 1990) is strictly better than 0.5-competitive and the problem is strictly harder than the online bipartite matching problem in that no algorithms can be (1 – 1/e)-competitive. This paper pins down two tight competitive ratios of classic algorithms for the fully online matching problem. For the fractional version of the problem, we show that a natural instantiation of the water-filling algorithm is 2 –√2 ≈ 0.585-competitive, together with a matching hardness result. Interestingly, our hardness result applies to arbitrary algorithms in the edge-arrival models of the online matching problem, improving the state-of-art 1/1+1n2≈0.5906 upper bound. For integral algorithms, we show a tight competitive ratio of ≈ 0.567 for the ranking algorithm on bipartite graphs, matching a hardness result by Huang et al. (STOC 2018). Read More: https://epubs.siam.org/doi/10.1137/1.9781611975482.178 | - |
dc.language | eng | - |
dc.publisher | Society for Industrial and Applied Mathematics. | - |
dc.relation.ispartof | Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2019) | - |
dc.rights | Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2019). Copyright © Society for Industrial and Applied Mathematics. | - |
dc.title | Tight Competitive Ratios of Classic Matching Algorithms in the Fully Online Model | - |
dc.type | Conference_Paper | - |
dc.identifier.email | Huang, Z: zhiyi@cs.hku.hk | - |
dc.identifier.authority | Huang, Z=rp01804 | - |
dc.identifier.doi | 10.1137/1.9781611975482.178 | - |
dc.identifier.scopus | eid_2-s2.0-85066945429 | - |
dc.identifier.hkuros | 300034 | - |
dc.identifier.spage | 2875 | - |
dc.identifier.epage | 2886 | - |
dc.publisher.place | Philadelphia, PA | - |