Show simple item record

dc.contributor.author
Anegg, Georg
dc.contributor.author
Vargas Koch, Laura
dc.contributor.author
Zenklusen, Rico
dc.contributor.editor
Chechik, Shiri
dc.contributor.editor
Navarro, Gonzalo
dc.contributor.editor
Rotenberg, Eva
dc.contributor.editor
Herman, Grzegorz
dc.date.accessioned
2022-09-22T15:16:53Z
dc.date.available
2022-09-17T09:34:41Z
dc.date.available
2022-09-22T15:16:53Z
dc.date.issued
2022
dc.identifier.isbn
978-3-95977-247-1
en_US
dc.identifier.issn
1868-8969
dc.identifier.other
10.4230/LIPIcs.ESA.2022.7
en_US
dc.identifier.uri
http://hdl.handle.net/20.500.11850/571184
dc.identifier.doi
10.3929/ethz-b-000571184
dc.description.abstract
Fair clustering enjoyed a surge of interest recently. One appealing way of integrating fairness aspects into classical clustering problems is by introducing multiple covering constraints. This is a natural generalization of the robust (or outlier) setting, which has been studied extensively and is amenable to a variety of classic algorithmic techniques. In contrast, for the case of multiple covering constraints (the so-called colorful setting), specialized techniques have only been developed recently for k-Center clustering variants, which is also the focus of this paper. While prior techniques assume covering constraints on the clients, they do not address additional constraints on the facilities, which has been extensively studied in non-colorful settings. In this paper, we present a quite versatile framework to deal with various constraints on the facilities in the colorful setting, by combining ideas from the iterative greedy procedure for Colorful k-Center by Inamdar and Varadarajan with new ingredients. To exemplify our framework, we show how it leads, for a constant number γ of colors, to the first constant-factor approximations for both Colorful Matroid Supplier with respect to a linear matroid and Colorful Knapsack Supplier. In both cases, we readily get an O(2γ)-approximation. Moreover, for Colorful Knapsack Supplier, we show that it is possible to obtain constant approximation guarantees that are independent of the number of colors γ, as long as γ = O(1), which is needed to obtain a polynomial running time. More precisely, we obtain a 7-approximation by extending a technique recently introduced by Jia, Sheth, and Svensson for Colorful k-Center.
en_US
dc.format
application/pdf
en_US
dc.language.iso
en
en_US
dc.publisher
Schloss Dagstuhl - Leibniz-Zentrum für Informatik
dc.rights.uri
http://creativecommons.org/licenses/by/4.0/
dc.subject
Approximation Algorithms
en_US
dc.subject
Fair Clustering
en_US
dc.subject
Colorful k-Center
en_US
dc.title
Techniques for Generalized Colorful k-Center Problems
en_US
dc.type
Conference Paper
dc.rights.license
Creative Commons Attribution 4.0 International
dc.date.published
2022-09-01
ethz.book.title
30th Annual European Symposium on Algorithms (ESA 2022)
en_US
ethz.journal.title
Leibniz International Proceedings in Informatics (LIPIcs)
ethz.journal.volume
244
en_US
ethz.journal.abbreviated
Leibniz Int. Proc. Inform.
ethz.pages.start
7
en_US
ethz.size
14 p.
en_US
ethz.version.deposit
publishedVersion
en_US
ethz.event
30th Annual European Symposium on Algorithms (ESA 2022)
en_US
ethz.event.location
Potsdam, Germany
en_US
ethz.event.date
September 5-9, 2022
en_US
ethz.grant
Toward Stronger Approximation Algorithms for Fundamental Network Design and Optimization Problems
en_US
ethz.grant
Fundamental Problems at the Interface of Combinatorial Optimization with Integer Programming and Online Optimization
en_US
ethz.identifier.scopus
ethz.publication.place
Dagstuhl
en_US
ethz.publication.status
published
en_US
ethz.leitzahl
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02000 - Dep. Mathematik / Dep. of Mathematics::02502 - Institut für Operations Research / Institute for Operations Research::09487 - Zenklusen, Rico / Zenklusen, Rico
ethz.leitzahl.certified
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02000 - Dep. Mathematik / Dep. of Mathematics::02502 - Institut für Operations Research / Institute for Operations Research::09487 - Zenklusen, Rico / Zenklusen, Rico
ethz.grant.agreementno
184622
ethz.grant.agreementno
817750
ethz.grant.fundername
SNF
ethz.grant.fundername
EC
ethz.grant.funderDoi
10.13039/501100001711
ethz.grant.funderDoi
10.13039/501100000780
ethz.grant.program
Projekte MINT
ethz.grant.program
H2020
ethz.date.deposited
2022-09-17T09:34:56Z
ethz.source
SCOPUS
ethz.eth
yes
en_US
ethz.availability
Open access
en_US
ethz.rosetta.installDate
2022-09-22T15:16:54Z
ethz.rosetta.lastUpdated
2024-02-02T18:19:37Z
ethz.rosetta.versionExported
true
ethz.COinS
ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.atitle=Techniques%20for%20Generalized%20Colorful%20k-Center%20Problems&rft.jtitle=Leibniz%20International%20Proceedings%20in%20Informatics%20(LIPIcs)&rft.date=2022&rft.volume=244&rft.spage=7&rft.issn=1868-8969&rft.au=Anegg,%20Georg&Vargas%20Koch,%20Laura&Zenklusen,%20Rico&rft.isbn=978-3-95977-247-1&rft.genre=proceeding&rft_id=info:doi/10.4230/LIPIcs.ESA.2022.7&rft.btitle=30th%20Annual%20European%20Symposium%20on%20Algorithms%20(ESA%202022)
 Search print copy at ETH Library

Files in this item

Thumbnail

Publication type

Show simple item record