Buchumschlag

Accelerated Relax-and-Round for Concave Coverage Problems

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Fahrbach, Matthew, Liaee, Mehraneh, Zadimoghaddam, Morteza
Format:	Preprint
Veröffentlicht:	2026
Schlagworte:	Data Structures and Algorithms Machine Learning
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

GIST: Greedy Independent Set Thresholding for Max-Min Diversification with Submodular Utility
von: Fahrbach, Matthew, et al.
Veröffentlicht: (2024)

Deletion Robust Submodular Maximization over Matroids
von: Dütting, Paul, et al.
Veröffentlicht: (2022)

Consistent Submodular Maximization
von: Dütting, Paul, et al.
Veröffentlicht: (2024)

Fully Dynamic Submodular Maximization over Matroids
von: Dütting, Paul, et al.
Veröffentlicht: (2023)

Deletion Robust Non-Monotone Submodular Maximization over Matroids
von: Dütting, Paul, et al.
Veröffentlicht: (2022)

The Cost of Consistency: Submodular Maximization with Constant Recourse
von: Dütting, Paul, et al.
Veröffentlicht: (2024)

Edge-Weighted Online Bipartite Matching
von: Fahrbach, Matthew, et al.
Veröffentlicht: (2020)

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

PriorBoost: An Adaptive Algorithm for Learning from Aggregate Responses
von: Javanmard, Adel, et al.
Veröffentlicht: (2024)

Learning-Augmented Algorithms for Online Concave Packing and Convex Covering Problems
von: Grigorescu, Elena, et al.
Veröffentlicht: (2024)

A Dynamic Algorithm for Weighted Submodular Cover Problem
von: Banihashem, Kiarash, et al.
Veröffentlicht: (2024)

Faster Sampling from Log-Concave Densities over Polytopes via Efficient Linear Solvers
von: Mangoubi, Oren, et al.
Veröffentlicht: (2024)

Faster Graph Embeddings via Coarsening
von: Fahrbach, Matthew, et al.
Veröffentlicht: (2020)

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

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

Negative Momentum for Convex-Concave Optimization
von: Shugart, Henry, et al.
Veröffentlicht: (2026)

Approximately Optimal Core Shapes for Tensor Decompositions
von: Ghadiri, Mehrdad, et al.
Veröffentlicht: (2023)

Complexity of Non-Log-Concave Sampling in Fisher Information
von: Chewi, Sinho, et al.
Veröffentlicht: (2026)

A Simple Learning-Augmented Algorithm for Online Packing with Concave Objectives
von: Grigorescu, Elena, et al.
Veröffentlicht: (2024)

Fast Tensor Completion via Approximate Richardson Iteration
von: Ghadiri, Mehrdad, et al.
Veröffentlicht: (2025)

FPTAS for Holant Problems with Log-Concave Signatures
von: He, Kun, et al.
Veröffentlicht: (2024)

Learning Partitions with Optimal Query and Round Complexities
von: Black, Hadley, et al.
Veröffentlicht: (2025)

On the Problem of Best Arm Retention
von: Chen, Houshuang, et al.
Veröffentlicht: (2025)

Accelerating Matroid Optimization through Fast Imprecise Oracles
von: Eberle, Franziska, et al.
Veröffentlicht: (2024)

Scalable Private Partition Selection via Adaptive Weighting
von: Chen, Justin Y., et al.
Veröffentlicht: (2025)

Better Bounds for the Distributed Experts Problem
von: Woodruff, David P., et al.
Veröffentlicht: (2026)

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

Accelerating ERM for data-driven algorithm design using output-sensitive techniques
von: Balcan, Maria-Florina, et al.
Veröffentlicht: (2022)

Improved Approximations for Hard Graph Problems using Predictions
von: Aamand, Anders, et al.
Veröffentlicht: (2025)

Nearly-tight Approximation Guarantees for the Improving Multi-Armed Bandits Problem
von: Blum, Avrim, et al.
Veröffentlicht: (2024)

Learning-augmented Online Algorithm for Two-level Ski-rental Problem
von: Zhang, Keyuan, et al.
Veröffentlicht: (2024)

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

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

Bandit Sequential Posted Pricing via Half-Concavity
von: Singla, Sahil, et al.
Veröffentlicht: (2023)

Online Rounding Schemes for $ k $-Rental Problems
von: Nekouyan, Hossein, et al.
Veröffentlicht: (2025)

Cost Preserving Dependent Rounding for Allocation Problems
von: Rohwedder, Lars, et al.
Veröffentlicht: (2025)

Query-Efficient Locally Private Hypothesis Selection via the Scheffe Graph
von: Kamath, Gautam, et al.
Veröffentlicht: (2025)

Online Paging with Heterogeneous Cache Slots
von: Chrobak, Marek, et al.
Veröffentlicht: (2022)

Online Allocation with Concave, Diminishing-Returns Objectives
von: Patton, Kalen
Veröffentlicht: (2025)

Partial Optimality in the Preordering Problem
von: Stein, David, et al.
Veröffentlicht: (2026)