2026-07-22T13:00:47Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7559 2024-03-06T10:40:36Z ddc:004 open_access

A Lottery Model for Center-Type Problems with Outliers Harris, David G. Pensyl, Thomas Srinivasan, Aravind Trinh, Khoa approximation algorithms randomized rounding clustering problems 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik David G. Harris and Thomas Pensyl and Aravind Srinivasan and Khoa Trinh 2017 Is Part Of LIPIcs, Volume 81, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX-RANDOM.2017.10 urn:nbn:de:0030-drops-75596 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2017.10 eng https://creativecommons.org/licenses/by/3.0/legalcode