- Rating
- 2
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
This paper studies the online metric transportation problem. There are server locations and servers distributed among these locations. There are requests arriving sequentially, each needed to be matched to an available server immediately and irrevocably. Then cost of a match is measured by the distance. The goal is to design algorithms whose competitive ratio only depends on .
The authors propose the Robustified Greedy (RG) algorithm, which generalizes the Robust Matching (RM) algorithm of (Raghvendra, 2016). They show that RG achieves a competitive ratio at most , improving the previously best-known competitive ratio . Moreover, they show that RG retains the metric-sensitive property of RM so that its competitive ratio adapts to the dimension of the Euclidean space. Finally, they lower bound the total fraction of online cost of RG from greedy assginments (i.e., assigning the arriving request to the nearest-available server) by , where and are tunable parameters of the algorithm. Experiments showcase that RG exhibits excellent empirical performance.
Critical strengths
This paper considers a well-motivated and widely-studied problem. The writing is generally clear, and I appreciate authors' effort on presenting the results. The proofs are correct to the extent that I've checked. The proposed algorithm generalizes an existing algorithm in a natural (albeit less intuitive) way, improving the best competitive-ratio upper bound for this problem. To the best of my knowledge, the guarantee on the fraction of greedy assignments is new to the literature.
Critical weaknesses
The motivating question about greedy assignments is, in my opinion, not very appealing. It's unclear to me why we should caring about the greedy-assignment cost of the algorithm given that it's not related to the competitive ratio. In addition, the non-greedy assignments also affect the server configurations and hence the greedy assignments, making the greedy-assignment cost an algorithm-specific benchmark.
On the technical side, the primal-dual analysis of RG seems to substantially resemble the analysis of RM presented in (Raghvendra, 2016). Although I haven't checked the metric-sensitivity proof, it wouldn't be surprising to me that it follows the same proof template as the prior work. Overall, I don't see much new technical insight coming from the proofs.
There are other minor weakness, including the missing Related Work section and a clear exposition of proof intuition for those who never read (Raghvendra, 2016).
Questions for authors
-
What is the intuition behind reducing the penalty term for direct augmenting paths? Why would it lead to improved competitive ratio?
-
What are the main technical innovations compared to the analysis for RM in previous work?
-
What is the competitive ratio of RG for online metric matching?
3 comments
response request
Thank you again for your review. With the discussion closing tonight, we’d appreciate a brief acknowledgment of our rebuttal and any feedback on whether it addresses your concerns.
Dear authors,
I really appreciate your efforts on addressing my concerns. I'm still not convinced by the value of measuring the contribution of Greedy assignments since the value of Greedy mainly comes from its easy implementation and transparency, yet the proposed algorithm still admits rather complicated form. On the technical side, improving the leading constant seems quite marginal to me. Overall, I'd like to maintain my assessment and score.
We sincerely thank the reviewer for their feedback. We clarify several aspects of our contributions that may not have been sufficiently clear and will revise the paper accordingly.
Response. Greedy assignments are central to achieving RG's improved competitive ratio of 6.6604k−2.89. We explain this connection through our technical contributions below.
Response. RG builds on RM's primal-dual framework. However, our work introduces three new algorithmic and analytical tools:
Response. Greedy assignments have independent practical significance beyond their role in our competitive analysis. We discuss this motivation in our common response.
Response. Choosing α<t discounts direct edges from the arriving request to free servers relative to non-direct augmenting paths. Among all direct paths, the edge to the nearest free server has the lowest net-cost. Thus, whenever RG selects a direct path, it necessarily chooses the nearest available server. This greedy assignment enters both the online and auxiliary matchings and persists in the auxiliary matching until the corresponding server becomes saturated (Lemma 10). Exploiting this persistence enables a tighter analysis, improving the competitive-ratio bound from 11.66k to 6.6604k−2.89.
Response. For the specific setting of online metric matching, a sharper analysis yields a sharper competitive ratio of 1+2(n−1)max{$1,\frac{t}{\alpha+1}$} which matches the tight 2n−1 for α≥t−1.