6 papers
Rounding the Ball LP for Fair Max-Min Diversification
Julián Mestre, Lam Khai Trinh, Anthony Wirth
Given points in a metric space, partitioned into groups, , and integer quotas, , summing to , the Fair Max-Min Diversification problem asks for…
A Radius-Sensitive Approximation Algorithm for Connected Submodular Maximization
Philip Cervenjak, Junhao Gan, Naonori Kakimura +2
Connected Submodular Maximization (CSM) is a graph problem with important applications to wireless network deployment, path planning, epidemic outbreaks, and cancer genome studies.…
Optimal Dynamic Parameterized Subset Sampling
Junhao Gan, Seeun William Umboh, Hanzhi Wang +2
In this paper, we study the Dynamic Parameterized Subset Sampling (DPSS) problem in the Word RAM model. In DPSS, the input is a set,~, of~ items, where each item,~, has a…
Maximum Unique Coverage on Streams: Improved FPT Approximation Scheme and Tighter Space Lower Bound
Philip Cervenjak, Junhao Gan, Seeun William Umboh +1
We consider the Max Unique Coverage problem, including applications to the data stream model. The input is a universe of elements, a collection of subsets of this universe,…
Improved Algorithms for Maximum Coverage in Dynamic and Random Order Streams
Amit Chakrabarti, Andrew McGregor, Anthony Wirth
The maximum coverage problem is to select sets from a collection of sets such that the cardinality of the union of the selected sets is maximized. We consider -appro…
Fast Parallel Algorithms for Submodular -Superseparable Maximization
Philip Cervenjak, Junhao Gan, Anthony Wirth
Maximizing a non-negative, monontone, submodular function over elements under a cardinality constraint (SMCC) is a well-studied NP-hard problem. It has important applic…