Cover Image

Accelerated Relax-and-Round for Concave Coverage Problems

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Fahrbach, Matthew, Liaee, Mehraneh, Zadimoghaddam, Morteza
Format:	Preprint
Published:	2026
Subjects:	Data Structures and Algorithms Machine Learning
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

GIST: Greedy Independent Set Thresholding for Max-Min Diversification with Submodular Utility
by: Fahrbach, Matthew, et al.
Published: (2024)

Deletion Robust Submodular Maximization over Matroids
by: Dütting, Paul, et al.
Published: (2022)

Consistent Submodular Maximization
by: Dütting, Paul, et al.
Published: (2024)

Fully Dynamic Submodular Maximization over Matroids
by: Dütting, Paul, et al.
Published: (2023)

Deletion Robust Non-Monotone Submodular Maximization over Matroids
by: Dütting, Paul, et al.
Published: (2022)

The Cost of Consistency: Submodular Maximization with Constant Recourse
by: Dütting, Paul, et al.
Published: (2024)

Edge-Weighted Online Bipartite Matching
by: Fahrbach, Matthew, et al.
Published: (2020)

A Tight Lower Bound for the Approximation Guarantee of Higher-Order Singular Value Decomposition
by: Fahrbach, Matthew, et al.
Published: (2025)

PriorBoost: An Adaptive Algorithm for Learning from Aggregate Responses
by: Javanmard, Adel, et al.
Published: (2024)

Learning-Augmented Algorithms for Online Concave Packing and Convex Covering Problems
by: Grigorescu, Elena, et al.
Published: (2024)

A Dynamic Algorithm for Weighted Submodular Cover Problem
by: Banihashem, Kiarash, et al.
Published: (2024)

Faster Sampling from Log-Concave Densities over Polytopes via Efficient Linear Solvers
by: Mangoubi, Oren, et al.
Published: (2024)

Faster Graph Embeddings via Coarsening
by: Fahrbach, Matthew, et al.
Published: (2020)

Relax and Merge: A Simple Yet Effective Framework for Solving Fair $k$-Means and $k$-sparse Wasserstein Barycenter Problems
by: Song, Shihong, et al.
Published: (2024)

No-Regret M${}^{\natural}$-Concave Function Maximization: Stochastic Bandit Algorithms and Hardness of Adversarial Full-Information Setting
by: Oki, Taihei, et al.
Published: (2024)

Negative Momentum for Convex-Concave Optimization
by: Shugart, Henry, et al.
Published: (2026)

Approximately Optimal Core Shapes for Tensor Decompositions
by: Ghadiri, Mehrdad, et al.
Published: (2023)

Complexity of Non-Log-Concave Sampling in Fisher Information
by: Chewi, Sinho, et al.
Published: (2026)

A Simple Learning-Augmented Algorithm for Online Packing with Concave Objectives
by: Grigorescu, Elena, et al.
Published: (2024)

Fast Tensor Completion via Approximate Richardson Iteration
by: Ghadiri, Mehrdad, et al.
Published: (2025)

FPTAS for Holant Problems with Log-Concave Signatures
by: He, Kun, et al.
Published: (2024)

Learning Partitions with Optimal Query and Round Complexities
by: Black, Hadley, et al.
Published: (2025)

On the Problem of Best Arm Retention
by: Chen, Houshuang, et al.
Published: (2025)

Accelerating Matroid Optimization through Fast Imprecise Oracles
by: Eberle, Franziska, et al.
Published: (2024)

Scalable Private Partition Selection via Adaptive Weighting
by: Chen, Justin Y., et al.
Published: (2025)

Better Bounds for the Distributed Experts Problem
by: Woodruff, David P., et al.
Published: (2026)

An Efficient Matrix Multiplication Algorithm for Accelerating Inference in Binary and Ternary Neural Networks
by: Dehghankar, Mohsen, et al.
Published: (2024)

Accelerating ERM for data-driven algorithm design using output-sensitive techniques
by: Balcan, Maria-Florina, et al.
Published: (2022)

Improved Approximations for Hard Graph Problems using Predictions
by: Aamand, Anders, et al.
Published: (2025)

Nearly-tight Approximation Guarantees for the Improving Multi-Armed Bandits Problem
by: Blum, Avrim, et al.
Published: (2024)

Learning-augmented Online Algorithm for Two-level Ski-rental Problem
by: Zhang, Keyuan, et al.
Published: (2024)

Capacity Provisioning Motivated Online Non-Convex Optimization Problem with Memory and Switching Cost
by: Vaze, Rahul, et al.
Published: (2024)

Corporate Needs You to Find the Difference: Revisiting Submodular and Supermodular Ratio Optimization Problems
by: Harb, Elfarouk, et al.
Published: (2025)

Bandit Sequential Posted Pricing via Half-Concavity
by: Singla, Sahil, et al.
Published: (2023)

Online Rounding Schemes for $ k $-Rental Problems
by: Nekouyan, Hossein, et al.
Published: (2025)

Cost Preserving Dependent Rounding for Allocation Problems
by: Rohwedder, Lars, et al.
Published: (2025)

Query-Efficient Locally Private Hypothesis Selection via the Scheffe Graph
by: Kamath, Gautam, et al.
Published: (2025)

Online Paging with Heterogeneous Cache Slots
by: Chrobak, Marek, et al.
Published: (2022)

Online Allocation with Concave, Diminishing-Returns Objectives
by: Patton, Kalen
Published: (2025)

Partial Optimality in the Preordering Problem
by: Stein, David, et al.
Published: (2026)