Image de couverture de livre

Prize-Collecting Forest with Submodular Penalties: Improved Approximation

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Ahmadi, Ali, Gholami, Iman, Hajiaghayi, MohammadTaghi, Jabbarzade, Peyman, Mahdavi, Mohammad
Format:	Preprint
Publié:	2025
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

2-Approximation for Prize-Collecting Steiner Forest
par: Ahmadi, Ali, et autres
Publié: (2023)

Prize-Collecting Steiner Tree: A 1.79 Approximation
par: Ahmadi, Ali, et autres
Publié: (2024)

Breaking a Long-Standing Barrier: 2-$\varepsilon$ Approximation for Steiner Forest
par: Ahmadi, Ali, et autres
Publié: (2025)

A Dynamic Algorithm for Weighted Submodular Cover Problem
par: Banihashem, Kiarash, et autres
Publié: (2024)

Dynamic Diameter in High-Dimensions against Adaptive Adversary and Beyond
par: Banihashem, Kiarash, et autres
Publié: (2025)

Bi-Criteria Metric Distortion
par: Banihashem, Kiarash, et autres
Publié: (2024)

Dynamic Dyck and Tree Edit Distance: Decompositions and Reductions to String Edit Distance
par: Das, Debarati, et autres
Publié: (2025)

Dynamic Metric Embedding into $\ell_p$ Space
par: Banihashem, Kiarash, et autres
Publié: (2024)

Matroid Algorithms Under Size-Sensitive Independence Oracles
par: Banihashem, Kiarash, et autres
Publié: (2026)

Replicable Composition
par: Banihashem, Kiarash, et autres
Publié: (2026)

Replication-proof Bandit Mechanism Design with Bayesian Agents
par: Shin, Suho, et autres
Publié: (2023)

Optimal Contest Beyond Convexity
par: Golrezaei, Negin, et autres
Publié: (2026)

Beating Competitive Ratio 4 for Graphic Matroid Secretary
par: Banihashem, Kiarash, et autres
Publié: (2025)

Adversarially Robust Approximate Furthest Neighbor
par: Banihashem, Kiarash, et autres
Publié: (2026)

Pandora with Inaccurate Priors
par: Banihashem, Kiarash, et autres
Publié: (2025)

Fairness and Efficiency in Online Class Matching
par: Hajiaghayi, MohammadTaghi, et autres
Publié: (2024)

Bandit Social Learning: Exploration under Myopic Behavior
par: Banihashem, Kiarash, et autres
Publié: (2023)

Active Learning for Decision Trees with Provable Guarantees
par: Moakhar, Arshia Soltani, et autres
Publié: (2026)

The General Expiration Streaming Model: Diameter, $k$-Center, Counting, Sampling, and Friends
par: Blank, Lotte, et autres
Publié: (2025)

Online Sampling and Decision Making with Low Entropy
par: Hajiaghayi, Mohammad Taghi, et autres
Publié: (2021)

Optimal Algorithms for Free Order Multiple-Choice Secretary
par: Hajiaghayi, Mohammad Taghi, et autres
Publié: (2022)

Approximating Prize-Collecting Variants of TSP
par: Alimi, Morteza, et autres
Publié: (2024)

Delegation with Costly Inspection
par: Hajiaghayi, Mohammad T., et autres
Publié: (2025)

A Better-Than-1.6-Approximation for Prize-Collecting TSP
par: Blauth, Jannis, et autres
Publié: (2023)

Improved Approximation for Ranking on General Graphs
par: Derakhshan, Mahsa, et autres
Publié: (2025)

Bicriterial Approximation for the Incremental Prize-Collecting Steiner-Tree Problem
par: Disser, Yann, et autres
Publié: (2024)

3/2-Approximation for the Forest Augmentation Problem
par: Çivril, Ali
Publié: (2024)

Sublinear Metric Steiner Forest via Maximal Independent Set
par: Mahabadi, Sepideh, et autres
Publié: (2025)

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

Improved Algorithms for Fair Matroid Submodular Maximization
par: Mahabadi, Sepideh, et autres
Publié: (2026)

Maximization of Approximately Submodular Functions
par: Horel, Thibaut, et autres
Publié: (2024)

Algorithmic Delegated Choice: An Annotated Reading List
par: Hajiaghayi, Mohammad T., et autres
Publié: (2025)

Improved Evolutionary Algorithms for Submodular Maximization with Cost Constraints
par: Zhu, Yanhui, et autres
Publié: (2024)

Scalable Fair Influence Blocking Maximization via Approximately Monotonic Submodular Optimization
par: Fang, Qiangpeng, et autres
Publié: (2026)

Approximating Submodular Matroid-Constrained Partitioning
par: Bérczi, Kristóf, et autres
Publié: (2025)

Chasing Submodular Objectives, and Submodular Maximization via Cutting Planes
par: Buchbinder, Niv, et autres
Publié: (2025)

An Approximation Algorithm for Monotone Submodular Cost Allocation
par: Mizutani, Ryuhei
Publié: (2025)

Approximation Schemes for Orienteering and Deadline TSP in Doubling Metrics
par: Ren, Kinter, et autres
Publié: (2024)

Sublinear Metric Steiner Tree via Improved Bounds for Set Cover
par: Mahabadi, Sepideh, et autres
Publié: (2024)

Breaking Barriers: Combinatorial Algorithms for Non-monotone Submodular Maximization with Sublinear Adaptivity and $1/e$ Approximation
par: Chen, Yixin, et autres
Publié: (2025)