research-article

Public Access

A Lottery Model for Center-Type Problems With Outliers

Authors:

David G. Harris,

Aravind Srinivasan,

Khoa TrinhAuthors Info & Claims

ACM Transactions on Algorithms (TALG), Volume 15, Issue 3

Article No.: 36, Pages 1 - 25

https://doi.org/10.1145/3311953

Published: 12 June 2019 Publication History

All formats PDF

Abstract

In this article, we give tight approximation algorithms for the k-center and matroid center problems with outliers. Unfairness arises naturally in this setting: certain clients could always be considered as outliers. To address this issue, we introduce a lottery model in which each client j is allowed to submit a parameter p_j ∈ [0,1] and we look for a random solution that covers every client j with probability at least p_j. Our techniques include a randomized rounding procedure to round a point inside a matroid intersection polytope to a basis plus at most one extra item such that all marginal probabilities are preserved and such that a certain linear function of the variables does not decrease in the process with probability one.

References

[1]

Sara Ahmadian, Ashkan Norouzi-Fard, Ola Svensson, and Justin Ward. 2016. Better guarantees for k-means and Euclidean k-median by primal-dual algorithms. CoRR abs/1612.07925. http://arxiv.org/abs/1612.07925

[2]

Jaroslaw Byrka, Thomas Pensyl, Bartosz Rybicki, Aravind Srinivasan, and Khoa Trinh. 2015. An improved approximation for k-median, and positive correlation in budgeted optimization. In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’15). 737--756.

[3]

Deeparnab Chakrabarty, Prachi Goyal, and Ravishankar Krishnaswamy. 2016. The non-uniform k-center problem. In Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP’16), Vol. 55. 67:1--67:15.

[4]

Moses Charikar, Samir Khuller, David M. Mount, and Giri Narasimhan. 2001. Algorithms for facility location problems with outliers. In Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’01). Society for Industrial and Applied Mathematics, Philadelphia, PA, 642--651. http://dl.acm.org/citation.cfm?id=365411.365555

Digital Library

[5]

Danny Z. Chen, Jian Li, Hongyu Liang, and Haitao Wang. 2013. Matroid and knapsack center problems. Proceedings of the 16th International Conference on Integer Programming and Combinatorial Optimization (IPCO’13), 110--122.

Digital Library

[6]

I. M. Gel’fand and V. V. Serganova. 1987. Combinatorial geometries and torus strata on homogeneous compact manifolds. Russian Mathematical Surveys 42, 2 (1987), 133. http://stacks.iop.org/0036-0279/42/i=2/a=R03

[7]

David G. Harris, Thomas Pensyl, Aravind Srinivasan, and Khoa Trinh. 2017. Symmetric randomized dependent rounding. CoRR abs/1709.06995.

[8]

Dorit S. Hochbaum and David B. Shmoys. 1986. A unified approach to approximation algorithms for bottleneck problems. Journal of the ACM 33, 3 (May 1986), 533--550.

Digital Library

[9]

Wen-Lian Hsu and George L. Nemhauser. 1979. Easy and hard bottleneck location problems. Discrete Applied Mathematics 1, 3 (1979), 209--215.

[10]

Tapas Kanungo, David M. Mount, Nathan S. Netanyahu, Christine D. Piatko, Ruth Silverman, and Angela Y. Wu. 2004. A local search approximation algorithm for k-means clustering. Computational Geometry 28, 2--3 (2004), 89--112.

Digital Library

[11]

Ravishankar Krishnaswamy, Amit Kumar, Viswanath Nagarajan, Yogish Sabharwal, and Barna Saha. 2011. The matroid median problem. In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’11). SIAM, 1117--1130.

[12]

Lap-Chi Lau, R. Ravi, and Mohit Singh. 2011. Iterative Methods in Combinatorial Optimization (1st ed.). Cambridge University Press, New York, NY.

[13]

Shi Li and Ola Svensson. 2013. Approximating k-median via pseudo-approximation. In Proceedings of STOC. 901--910.

Digital Library

[14]

Alexander Schrijver. 2003. Combinatorial Optimization: Polyhedra and Efficiency. Vol. 24. Springer Science 8 Business Media.

[15]

Chaitanya Swamy. 2014. Improved approximation algorithms for matroid and knapsack median problems and applications. In APPROX/RANDOM 2014, Vol. 28. 403--418.

[16]

David P. Williamson and David B. Shmoys. 2011. The Design of Approximation Algorithms. Cambridge University Press. I--XI, 1--504 pages.

Digital Library

Cited By

Wu XFeng QXu JWang J(2024)New Algorithms for Fair k-Center Problem with Outliers and Capacity ConstraintsTheoretical Computer Science10.1016/j.tcs.2024.114515(114515)Online publication date: Mar-2024
https://doi.org/10.1016/j.tcs.2024.114515
Bandyapadhyay SFomin FGolovach PLochet WPurohit NSimonov K(2023)How to find a good explanation for clustering?Artificial Intelligence10.1016/j.artint.2023.103948322(103948)Online publication date: Sep-2023
https://doi.org/10.1016/j.artint.2023.103948
Pellizzoni PPietracaprina APucci G(2023)Fully Dynamic Clustering and Diversity Maximization in Doubling MetricsAlgorithms and Data Structures10.1007/978-3-031-38906-1_41(620-636)Online publication date: 28-Jul-2023
https://doi.org/10.1007/978-3-031-38906-1_41
Show More Cited By

Index Terms

A Lottery Model for Center-Type Problems With Outliers
1. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
      1. Facility location and clustering
      2. Rounding techniques

Recommendations

Packing items into several bins facilitates approximating the separable assignment problem

( ( 1 - 1 e k ) β ) -approximation for k-SAP if the single bin problem admits a β-approximation. ( 1 - 1 e k ) -approximation for k-SAP if the single bin problem admits an FPTAS.For k 2 , our algorithm beats the upper bound of ( 1 - 1 e ) known for other ...
Lottery Pricing Equilibria
EC '16: Proceedings of the 2016 ACM Conference on Economics and Computation

We extend the notion of Combinatorial Walrasian Equilibrium, as defined by \citet{FGL13}, to settings with budgets. When agents have budgets, the maximum social welfare as traditionally defined is not a suitable benchmark since it is overly optimistic. ...
On Maximizing Welfare When Utility Functions Are Subadditive

We consider the problem of maximizing welfare when allocating $m$ items to $n$ players with subadditive utility functions. Our main result is a way of rounding any fractional solution to a linear programming relaxation to this problem so as to give a ...

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Algorithms

ACM Transactions on Algorithms Volume 15, Issue 3

July 2019

392 pages

ISSN:1549-6325

EISSN:1549-6333

DOI:10.1145/3331056

Editor:
Aravind Srinivasan
University of Maryland, USA

Issue’s Table of Contents

Copyright © 2019 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 12 June 2019

Accepted: 01 February 2019

Revised: 01 December 2018

Received: 01 October 2017

Published in TALG Volume 15, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Google LLC
National Science Foundation
Adobe Inc

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

12
Total Citations
View Citations
815
Total Downloads

Downloads (Last 12 months)236
Downloads (Last 6 weeks)14

Reflects downloads up to 10 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Wu XFeng QXu JWang J(2024)New Algorithms for Fair k-Center Problem with Outliers and Capacity ConstraintsTheoretical Computer Science10.1016/j.tcs.2024.114515(114515)Online publication date: Mar-2024
https://doi.org/10.1016/j.tcs.2024.114515
Bandyapadhyay SFomin FGolovach PLochet WPurohit NSimonov K(2023)How to find a good explanation for clustering?Artificial Intelligence10.1016/j.artint.2023.103948322(103948)Online publication date: Sep-2023
https://doi.org/10.1016/j.artint.2023.103948
Pellizzoni PPietracaprina APucci G(2023)Fully Dynamic Clustering and Diversity Maximization in Doubling MetricsAlgorithms and Data Structures10.1007/978-3-031-38906-1_41(620-636)Online publication date: 28-Jul-2023
https://doi.org/10.1007/978-3-031-38906-1_41
Pellizzoni PPietracaprina APucci G(2022)k-Center Clustering with Outliers in Sliding WindowsAlgorithms10.3390/a1502005215:2(52)Online publication date: 31-Jan-2022
https://doi.org/10.3390/a15020052
Almanza MEpasto APanconesi ARe GSelcuk Candan KLiu HAkoglu LLuna Dong XTang J(2022)k-Clustering with Fair OutliersProceedings of the Fifteenth ACM International Conference on Web Search and Data Mining10.1145/3488560.3498485(5-15)Online publication date: 11-Feb-2022
https://dl.acm.org/doi/10.1145/3488560.3498485
Deng SLi JRabani Y(2022)Approximation algorithms for clustering with dynamic pointsJournal of Computer and System Sciences10.1016/j.jcss.2022.07.001130:C(43-70)Online publication date: 1-Dec-2022
https://dl.acm.org/doi/10.1016/j.jcss.2022.07.001
Jia XSheth KSvensson O(2022)Fair colorful k-center clusteringMathematical Programming: Series A and B10.1007/s10107-021-01674-7192:1-2(339-360)Online publication date: 1-Mar-2022
https://dl.acm.org/doi/10.1007/s10107-021-01674-7
Anegg GAngelidakis HKurpisz AZenklusen R(2022)A technique for obtaining true approximations for k-center with covering constraintsMathematical Programming: Series A and B10.1007/s10107-021-01645-y192:1-2(3-27)Online publication date: 1-Mar-2022
https://dl.acm.org/doi/10.1007/s10107-021-01645-y
Chan TLattanzi SSozio MWang B(2022)Fully Dynamic k-Center Clustering with OutliersComputing and Combinatorics10.1007/978-3-031-22105-7_14(150-161)Online publication date: 22-Oct-2022
https://dl.acm.org/doi/10.1007/978-3-031-22105-7_14
Feldmann AVu T(2022)Generalized -Center: Distinguishing Doubling and Highway DimensionGraph-Theoretic Concepts in Computer Science10.1007/978-3-031-15914-5_16(215-229)Online publication date: 22-Jun-2022
https://dl.acm.org/doi/10.1007/978-3-031-15914-5_16
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

HTML Format

View this article in HTML Format.

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents