Image de couverture de livre

Maximum Unique Coverage on Streams: Improved FPT Approximation Scheme and Tighter Space Lower Bound

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Cervenjak, Philip, Gan, Junhao, Umboh, Seeun William, Wirth, Anthony
Format:	Preprint
Publié:	2024
Sujets:	Data Structures and Algorithms
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

A Radius-Sensitive Approximation Algorithm for Connected Submodular Maximization
par: Cervenjak, Philip, et autres
Publié: (2026)

Fast Parallel Algorithms for Submodular $p$-Superseparable Maximization
par: Cervenjak, Philip, et autres
Publié: (2023)

Optimal Dynamic Parameterized Subset Sampling
par: Gan, Junhao, et autres
Publié: (2024)

Online Computation of String Net Frequency
par: Guo, Peaker, et autres
Publié: (2024)

FPT Approximations for Connected Maximum Coverage
par: Inamdar, Tanmay, et autres
Publié: (2026)

Online Probabilistic Metric Embedding: A General Framework for Bypassing Inherent Bounds
par: Bartal, Yair, et autres
Publié: (2024)

Improved Online Algorithms for Inventory Management Problems with Holding and Delay Costs: Riding the Wave Makes Things Simpler, Stronger, & More General
par: Shmoys, David, et autres
Publié: (2026)

Optimal bounds on a tree inference algorithm
par: Gardiner, Jack, et autres
Publié: (2024)

Online TCP Acknowledgment under General Delays
par: Bhore, Sujoy, et autres
Publié: (2026)

Learning-Augmented Online Algorithms for Nonclairvoyant Joint Replenishment Problem with Deadlines
par: Dinitz, Michael, et autres
Publié: (2025)

Improved Algorithms for Maximum Coverage in Dynamic and Random Order Streams
par: Chakrabarti, Amit, et autres
Publié: (2024)

Local Computation Algorithms for Knapsack: impossibility results, and how to avoid them
par: Canonne, Clément L., et autres
Publié: (2025)

Lower Bounds for Approximate (& Exact) k-Disjoint-Shortest-Paths
par: Chitnis, Rajesh, et autres
Publié: (2024)

Approximate Graph Propagation Revisited: Dynamic Parameterized Queries, Tighter Bounds and Dynamic Updates
par: Zhao, Zhuowei, et autres
Publié: (2025)

Universal Optimization for Non-Clairvoyant Subadditive Joint Replenishment
par: Ezra, Tomer, et autres
Publié: (2024)

Colorful Vertex Recoloring of Bipartite Graphs
par: Patt-Shamir, Boaz, et autres
Publié: (2025)

Improved FPT Approximation for Non-metric TSP
par: Bampis, Evripidis, et autres
Publié: (2024)

Improved FPT Approximation Scheme and Approximate Kernel for Biclique-Free Max k-Weight SAT: Greedy Strikes Back
par: Manurangsi, Pasin
Publié: (2024)

Linear Space Streaming Lower Bounds for Approximating CSPs
par: Chou, Chi-Ning, et autres
Publié: (2021)

FPT Approximation of Generalised Hypertree Width for Bounded Intersection Hypergraphs
par: Lanzinger, Matthias, et autres
Publié: (2023)

FPT Approximation for Capacitated Sum of Radii
par: Jaiswal, Ragesh, et autres
Publié: (2024)

Maximum Coverage in Turnstile Streams with Applications to Fingerprinting Measures
par: Ene, Alina, et autres
Publié: (2025)

Optimal FPT-Approximability for Modular Linear Equations
par: Dabrowski, Konrad K., et autres
Publié: (2026)

Tight Streaming Lower Bounds for Deterministic Approximate Counting
par: Wang, Yichuan
Publié: (2024)

FPT Approximation Schemes for Min-Sum Radii and Min-Sum Diameters Clustering
par: Grandoni, Fabrizio, et autres
Publié: (2026)

FPT Approximations for Fair $k$-Min-Sum-Radii
par: Carta, Lena, et autres
Publié: (2024)

An FPT Constant-Factor Approximation Algorithm for Correlation Clustering
par: Zhou, Jianqi, et autres
Publié: (2025)

Half-Approximating Maximum Dicut in the Streaming Setting
par: Azarmehr, Amir, et autres
Publié: (2025)

On Tight FPT Time Approximation Algorithms for k-Clustering Problems
par: Dai, Han, et autres
Publié: (2025)

Optimal Single-Pass Streaming Lower Bounds for Approximating CSPs
par: Singer, Noah G., et autres
Publié: (2026)

New Algorithms and Lower Bounds for Streaming Tournaments
par: Ghosh, Prantar, et autres
Publié: (2024)

Near-Optimal Space Lower Bounds for Streaming CSPs
par: Fei, Yumou, et autres
Publié: (2026)

FPT Approximations for Fair Sum of Radii with Outliers and General Norm Objectives
par: Gadekar, Ameet
Publié: (2026)

Kidney Exchange: Faster Parameterized Algorithms and Tighter Lower Bounds
par: Banik, Aritra, et autres
Publié: (2025)

FPT Constant-Approximations for Capacitated Clustering to Minimize the Sum of Cluster Radii
par: Bandyapadhyay, Sayan, et autres
Publié: (2023)

Oblivious Algorithms for Maximum Directed Cut: New Upper and Lower Bounds
par: Hwang, Samuel, et autres
Publié: (2024)

Approximation and FPT Algorithms for Finding DM-Irreducible Spanning Subgraphs
par: Norose, Ryoma, et autres
Publié: (2024)

Improved Approximation Algorithm for Maximum Balanced Biclique
par: Manurangsi, Pasin
Publié: (2026)

Tight Space Lower Bound for Pseudo-Deterministic Approximate Counting
par: Grossman, Ofer, et autres
Publié: (2023)

Tighter Bounds on Non-clairvoyant Parallel Machine Scheduling with Prediction to Minimize Makespan
par: Chen, Tianqi, et autres
Publié: (2025)