DROPS

Document

APPROX

DOI: 10.4230/LIPIcs.APPROX/RANDOM.2022.34

Ordered k-Median with Outliers

Authors: Shichuan Deng and Qianfan Zhang

Published in: LIPIcs, Volume 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)

Abstract

We study a natural generalization of the celebrated ordered k-median problem, named robust ordered k-median, also known as ordered k-median with outliers. We are given facilities ℱ and clients 𝒞 in a metric space (ℱ∪𝒞,d), parameters k,m ∈ ℤ_+ and a non-increasing non-negative vector w ∈ ℝ_+^m. We seek to open k facilities F ⊆ ℱ and serve m clients C ⊆ 𝒞, inducing a service cost vector c = {d(j,F):j ∈ C}; the goal is to minimize the ordered objective w^⊤c^↓, where d(j,F) = min_{i ∈ F}d(j,i) is the minimum distance between client j and facilities in F, and c^↓ ∈ ℝ_+^m is the non-increasingly sorted version of c. Robust ordered k-median captures many interesting clustering problems recently studied in the literature, e.g., robust k-median, ordered k-median, etc. We obtain the first polynomial-time constant-factor approximation algorithm for robust ordered k-median, achieving an approximation guarantee of 127. The main difficulty comes from the presence of outliers, which already causes an unbounded integrality gap in the natural LP relaxation for robust k-median. This appears to invalidate previous methods in approximating the highly non-linear ordered objective. To overcome this issue, we introduce a novel yet very simple reduction framework that enables linear analysis of the non-linear objective. We also devise the first constant-factor approximations for ordered matroid median and ordered knapsack median using the same framework, and the approximation factors are 19.8 and 41.6, respectively.

Cite as

Shichuan Deng and Qianfan Zhang. Ordered k-Median with Outliers. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 34:1-34:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{deng_et_al:LIPIcs.APPROX/RANDOM.2022.34,
  author =	{Deng, Shichuan and Zhang, Qianfan},
  title =	{{Ordered k-Median with Outliers}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)},
  pages =	{34:1--34:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-249-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{245},
  editor =	{Chakrabarti, Amit and Swamy, Chaitanya},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.34},
  URN =		{urn:nbn:de:0030-drops-171560},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2022.34},
  annote =	{Keywords: clustering, approximation algorithm, design and analysis of algorithms}
}

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2021.68

Random Order Vertex Arrival Contention Resolution Schemes for Matching, with Applications

Authors: Hu Fu, Zhihao Gavin Tang, Hongxun Wu, Jinzhao Wu, and Qianfan Zhang

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

Abstract

With a wide range of applications, stochastic matching problems have been studied in different models, including prophet inequality, Query-Commit, and Price-of-Information. While there have been recent breakthroughs in all these settings for bipartite graphs, few non-trivial results are known for general graphs. In this paper, we study the random order vertex arrival contention resolution scheme for matching in general graphs, which is inspired by the recent work of Ezra et al. (EC 2020). We design an 8/15-selectable batched RCRS for matching and apply it to achieve 8/15-competitive/approximate algorithms for all the three models. Our results are the first non-trivial results for random order prophet matching and Price-of-Information matching in general graphs. For the Query-Commit model, our result substantially improves upon the 0.501 approximation ratio by Tang et al. (STOC 2020). We also show that no batched RCRS for matching can be better than 1/2+1/(2e²) ≈ 0.567-selectable.

Cite as

Hu Fu, Zhihao Gavin Tang, Hongxun Wu, Jinzhao Wu, and Qianfan Zhang. Random Order Vertex Arrival Contention Resolution Schemes for Matching, with Applications. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 68:1-68:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{fu_et_al:LIPIcs.ICALP.2021.68,
  author =	{Fu, Hu and Tang, Zhihao Gavin and Wu, Hongxun and Wu, Jinzhao and Zhang, Qianfan},
  title =	{{Random Order Vertex Arrival Contention Resolution Schemes for Matching, with Applications}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{68:1--68:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.68},
  URN =		{urn:nbn:de:0030-drops-141376},
  doi =		{10.4230/LIPIcs.ICALP.2021.68},
  annote =	{Keywords: Matching, Contention Resolution Scheme, Price of Information, Query-Commit}
}

Search Results

Documents authored by Zhang, Qianfan

Ordered k-Median with Outliers

Abstract

Cite as

Random Order Vertex Arrival Contention Resolution Schemes for Matching, with Applications

Abstract

Cite as

Thanks for your feedback!

Could not send message