Cover Image

Prize-Collecting Steiner Tree: A 1.79 Approximation

Fuente: arXiv

Saved in:

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

Similar Items

2-Approximation for Prize-Collecting Steiner Forest
by: Ahmadi, Ali, et al.
Published: (2023)

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)

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

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)

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)

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

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

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

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

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

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

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

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

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

From Directed Steiner Tree to Directed Polymatroid Steiner Tree in Planar Graphs
by: Chekuri, Chandra, et al.
Published: (2024)

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

Multi-Level Steiner Trees
by: Ahmed, Reyan, et al.
Published: (2018)

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

A 0.51-Approximation of Maximum Matching in Sublinear $n^{1.5}$ Time
by: Mahabadi, Sepideh, et al.
Published: (2025)

The Steiner Shortest Path Tree Problem
by: Asher, Omer, et al.
Published: (2025)

Approximation Algorithms for Connected Maximum Coverage, Minimum Connected Set Cover, and Node-Weighted Group Steiner Tree
by: D'Angelo, Gianlorenzo, et al.
Published: (2025)

Query Complexity of the Metric Steiner Tree Problem
by: Chen, Yu, et al.
Published: (2022)

Approximation Schemes for Subset TSP and Steiner Tree on Geometric Intersection Graphs
by: Kisfaludi-Bak, Sándor, et al.
Published: (2026)