File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1145/3406325.3451079
- Scopus: eid_2-s2.0-85108158878
- WOS: WOS:000810492500065
Supplementary
- Citations:
- Appears in Collections:
Conference Paper: Online stochastic matching, poisson arrivals, and the natural linear program
Title | Online stochastic matching, poisson arrivals, and the natural linear program |
---|---|
Authors | |
Issue Date | 2021 |
Publisher | Association for Computing Machinery (ACM). |
Citation | STOC 2021: Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Meeting, Italy, 21-25 June 2021, p. 682-693 How to Cite? |
Abstract | We study the online stochastic matching problem. Consider a bipartite graph with offline vertices on one side, and with i.i.d.online vertices on the other side. The offline vertices and the distribution of online vertices are known to the algorithm beforehand. The realization of the online vertices, however, is revealed one at a time, upon which the algorithm immediately decides how to match it. For maximizing the cardinality of the matching, we give a 0.711-competitive online algorithm, which improves the best previous ratio of 0.706. When the offline vertices are weighted, we introduce a 0.7009-competitive online algorithm for maximizing the total weight of the matched offline vertices, which improves the best previous ratio of 0.662.
Conceptually, we find that the analysis of online algorithms simplifies if the online vertices follow a Poisson process, and establish an approximate equivalence between this Poisson arrival model and online stochstic matching. Technically, we propose a natural linear program for the Poisson arrival model, and demonstrate how to exploit its structure by introducing a converse of Jensen’s inequality. Moreover, we design an algorithmic amortization to replace the analytic one in previous work, and as a result get the first vertex-weighted online stochastic matching algorithm that improves the results in the weaker random arrival model. |
Persistent Identifier | http://hdl.handle.net/10722/301411 |
ISBN | |
ISI Accession Number ID |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Huang, Z | - |
dc.contributor.author | Shu, X | - |
dc.date.accessioned | 2021-07-27T08:10:40Z | - |
dc.date.available | 2021-07-27T08:10:40Z | - |
dc.date.issued | 2021 | - |
dc.identifier.citation | STOC 2021: Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Meeting, Italy, 21-25 June 2021, p. 682-693 | - |
dc.identifier.isbn | 9781450380539 | - |
dc.identifier.uri | http://hdl.handle.net/10722/301411 | - |
dc.description.abstract | We study the online stochastic matching problem. Consider a bipartite graph with offline vertices on one side, and with i.i.d.online vertices on the other side. The offline vertices and the distribution of online vertices are known to the algorithm beforehand. The realization of the online vertices, however, is revealed one at a time, upon which the algorithm immediately decides how to match it. For maximizing the cardinality of the matching, we give a 0.711-competitive online algorithm, which improves the best previous ratio of 0.706. When the offline vertices are weighted, we introduce a 0.7009-competitive online algorithm for maximizing the total weight of the matched offline vertices, which improves the best previous ratio of 0.662. Conceptually, we find that the analysis of online algorithms simplifies if the online vertices follow a Poisson process, and establish an approximate equivalence between this Poisson arrival model and online stochstic matching. Technically, we propose a natural linear program for the Poisson arrival model, and demonstrate how to exploit its structure by introducing a converse of Jensen’s inequality. Moreover, we design an algorithmic amortization to replace the analytic one in previous work, and as a result get the first vertex-weighted online stochastic matching algorithm that improves the results in the weaker random arrival model. | - |
dc.language | eng | - |
dc.publisher | Association for Computing Machinery (ACM). | - |
dc.relation.ispartof | The 53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC) | - |
dc.title | Online stochastic matching, poisson arrivals, and the natural linear program | - |
dc.type | Conference_Paper | - |
dc.identifier.email | Huang, Z: zhiyi@cs.hku.hk | - |
dc.identifier.authority | Huang, Z=rp01804 | - |
dc.description.nature | link_to_subscribed_fulltext | - |
dc.identifier.doi | 10.1145/3406325.3451079 | - |
dc.identifier.scopus | eid_2-s2.0-85108158878 | - |
dc.identifier.hkuros | 323376 | - |
dc.identifier.spage | 682 | - |
dc.identifier.epage | 693 | - |
dc.identifier.isi | WOS:000810492500065 | - |
dc.publisher.place | New York, NY | - |