Cover Image

2-Approximation for Prize-Collecting Steiner Forest

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Ahmadi, Ali, Gholami, Iman, Hajiaghayi, MohammadTaghi, Jabbarzade, Peyman, Mahdavi, Mohammad
Format:	Preprint
Published:	2023
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Prize-Collecting Steiner Tree: A 1.79 Approximation
by: Ahmadi, Ali, et al.
Published: (2024)

Prize-Collecting Forest with Submodular Penalties: Improved Approximation
by: Ahmadi, Ali, et al.
Published: (2025)

Breaking a Long-Standing Barrier: 2-$\varepsilon$ Approximation for Steiner Forest
by: Ahmadi, Ali, et al.
Published: (2025)

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

Dynamic Diameter in High-Dimensions against Adaptive Adversary and Beyond
by: Banihashem, Kiarash, et al.
Published: (2025)

Bi-Criteria Metric Distortion
by: Banihashem, Kiarash, et al.
Published: (2024)

Dynamic Dyck and Tree Edit Distance: Decompositions and Reductions to String Edit Distance
by: Das, Debarati, et al.
Published: (2025)

Dynamic Metric Embedding into $\ell_p$ Space
by: Banihashem, Kiarash, et al.
Published: (2024)

Matroid Algorithms Under Size-Sensitive Independence Oracles
by: Banihashem, Kiarash, et al.
Published: (2026)

Replicable Composition
by: Banihashem, Kiarash, et al.
Published: (2026)

Replication-proof Bandit Mechanism Design with Bayesian Agents
by: Shin, Suho, et al.
Published: (2023)

Optimal Contest Beyond Convexity
by: Golrezaei, Negin, et al.
Published: (2026)

Beating Competitive Ratio 4 for Graphic Matroid Secretary
by: Banihashem, Kiarash, et al.
Published: (2025)

Adversarially Robust Approximate Furthest Neighbor
by: Banihashem, Kiarash, et al.
Published: (2026)

Pandora with Inaccurate Priors
by: Banihashem, Kiarash, et al.
Published: (2025)

Fairness and Efficiency in Online Class Matching
by: Hajiaghayi, MohammadTaghi, et al.
Published: (2024)

Bandit Social Learning: Exploration under Myopic Behavior
by: Banihashem, Kiarash, et al.
Published: (2023)

Bicriterial Approximation for the Incremental Prize-Collecting Steiner-Tree Problem
by: Disser, Yann, et al.
Published: (2024)

Active Learning for Decision Trees with Provable Guarantees
by: Moakhar, Arshia Soltani, et al.
Published: (2026)

The General Expiration Streaming Model: Diameter, $k$-Center, Counting, Sampling, and Friends
by: Blank, Lotte, et al.
Published: (2025)

Online Sampling and Decision Making with Low Entropy
by: Hajiaghayi, Mohammad Taghi, et al.
Published: (2021)

Optimal Algorithms for Free Order Multiple-Choice Secretary
by: Hajiaghayi, Mohammad Taghi, et al.
Published: (2022)

Sublinear Metric Steiner Forest via Maximal Independent Set
by: Mahabadi, Sepideh, et al.
Published: (2025)

Approximating Prize-Collecting Variants of TSP
by: Alimi, Morteza, et al.
Published: (2024)

Steiner Forest: A Simplified Better-Than-2 Approximation
by: Gupta, Anupam, et al.
Published: (2025)

A Polylogarithmic Approximation for Directed Steiner Forest in Planar Digraphs
by: Chekuri, Chandra, et al.
Published: (2024)

Delegation with Costly Inspection
by: Hajiaghayi, Mohammad T., et al.
Published: (2025)

A Better-Than-1.6-Approximation for Prize-Collecting TSP
by: Blauth, Jannis, et al.
Published: (2023)

Online Steiner Forest with Recourse
by: Long, Yaowei, et al.
Published: (2026)

Sublinear Metric Steiner Tree via Improved Bounds for Set Cover
by: Mahabadi, Sepideh, et al.
Published: (2024)

Streaming Algorithms for Geometric Steiner Forest
by: Czumaj, Artur, et al.
Published: (2020)

3/2-Approximation for the Forest Augmentation Problem
by: Çivril, Ali
Published: (2024)

Approximation Algorithms for Steiner Connectivity Augmentation
by: Hathcock, Daniel, et al.
Published: (2023)

Parameterized Algorithms for Steiner Forest in Bounded Width Graphs
by: Feldmann, Andreas Emil, et al.
Published: (2024)

Improved Approximation for Ranking on General Graphs
by: Derakhshan, Mahsa, et al.
Published: (2025)

On the Bidirected Cut Relaxation for Steiner Forest
by: Byrka, Jarosław, et al.
Published: (2024)

Algorithmic Delegated Choice: An Annotated Reading List
by: Hajiaghayi, Mohammad T., et al.
Published: (2025)

Approximation Algorithms for $\ell_p$-Shortest Path and $\ell_p$-Group Steiner Tree
by: Makarychev, Yury, et al.
Published: (2024)

Approximation Schemes for Orienteering and Deadline TSP in Doubling Metrics
by: Ren, Kinter, et al.
Published: (2024)

Approximating Maximum Matching Requires Almost Quadratic Time
by: Behnezhad, Soheil, et al.
Published: (2024)