License:
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2017.10
URN: urn:nbn:de:0030-drops-75596
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7559/
Harris, David G. ;
Pensyl, Thomas ;
Srinivasan, Aravind ;
Trinh, Khoa
A Lottery Model for Center-Type Problems with Outliers
Abstract
In this paper, 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 is allowed to submit a parameter indicating the lower-bound on the probability that it should be covered and we look for a random solution that satisfies all the given requests. Out 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.
BibTeX - Entry
@InProceedings{harris_et_al:LIPIcs:2017:7559,
author = {David G. Harris and Thomas Pensyl and Aravind Srinivasan and Khoa Trinh},
title = {{A Lottery Model for Center-Type Problems with Outliers}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)},
pages = {10:1--10:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-044-6},
ISSN = {1868-8969},
year = {2017},
volume = {81},
editor = {Klaus Jansen and Jos{\'e} D. P. Rolim and David Williamson and Santosh S. Vempala},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7559},
URN = {urn:nbn:de:0030-drops-75596},
doi = {10.4230/LIPIcs.APPROX-RANDOM.2017.10},
annote = {Keywords: approximation algorithms, randomized rounding, clustering problems}
}
Keywords: |
|
approximation algorithms, randomized rounding, clustering problems |
Collection: |
|
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017) |
Issue Date: |
|
2017 |
Date of publication: |
|
11.08.2017 |