Cover Image

Bicriterial Approximation for the Incremental Prize-Collecting Steiner-Tree Problem

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Disser, Yann, Griesbach, Svenja M., Klimm, Max, Lutz, Annette
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms Discrete Mathematics
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Incremental-Decremental Maximization
by: Disser, Yann, et al.
Published: (2025)

Maximizing a Submodular Function with Bounded Curvature under an Unknown Knapsack Constraint
by: Klimm, Max, et al.
Published: (2022)

An unconditional lower bound for the active-set method on the hypercube
by: Disser, Yann, et al.
Published: (2025)

An unconditional lower bound for the active-set method in convex quadratic maximization
by: Bach, Eleon, et al.
Published: (2025)

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

Terminal Steiner tree problem : Complexity and Algorithms
by: S, Jyothish, et al.
Published: (2026)

The Bidirected Cut Relaxation for Steiner Tree has Integrality Gap Smaller than 2
by: Byrka, Jarosław, et al.
Published: (2024)

Approximation Algorithm of Minimum All-Ones Problem for Arbitrary Graphs
by: Wang, Chen, et al.
Published: (2024)

Approximation of Spanning Tree Congestion using Hereditary Bisection
by: Kolman, Petr
Published: (2024)

Learning to Prune Instances of Steiner Tree Problem in Graphs
by: Zhang, Jiwei, et al.
Published: (2022)

A Structural Equivalence of Symmetric TSP to a Constrained Group Steiner Tree Problem
by: Arslanoğlu, Yılmaz
Published: (2026)

Approximation Algorithms for Optimal Hopsets
by: Dinitz, Michael, et al.
Published: (2025)

Approximate Realizations for Outerplanaric Degree Sequences
by: Bar-Noy, Amotz, et al.
Published: (2024)

Approximating Submodular Matroid-Constrained Partitioning
by: Bérczi, Kristóf, et al.
Published: (2025)

(Approximate) Matrix Multiplication via Convolutions
by: Uffenheimer, Yahel, et al.
Published: (2025)

An Approximate Generalization of the Okamura-Seymour Theorem
by: Kumar, Nikhil
Published: (2022)

Boosting Rectilinear Steiner Minimum Tree Algorithms with Augmented Bounding Volume Hierarchy
by: Yang, Puhan, et al.
Published: (2025)

An Approximation Algorithm for Monotone Submodular Cost Allocation
by: Mizutani, Ryuhei
Published: (2025)

A Constant-Factor Approximation for Directed Latency
by: Blauth, Jannis, et al.
Published: (2025)

Exponential Time Approximation for Coloring 3-Colorable Graphs
by: Guruswami, Venkatesan, et al.
Published: (2024)

Approximation algorithms for non-sequential star packing problems
by: Hu, Mengyuan, et al.
Published: (2024)

Approximately covering vertices by order-$5$ or longer paths
by: Gong, Mingyang, et al.
Published: (2024)

Approximating Maximum Edge 2-Coloring by Normalizing Graphs
by: Mömke, Tobias, et al.
Published: (2024)

Simultaneously Approximating All $\ell_p$-norms in Correlation Clustering
by: Davies, Sami, et al.
Published: (2023)

A Constant-Approximation Algorithm for Budgeted Sweep Coverage with Mobile Sensors
by: Liang, Wei, et al.
Published: (2024)

Approximation Algorithms for the $b$-Matching and List-Restricted Variants of MaxQAP
by: Nanta, Jiratchaphat, et al.
Published: (2025)

Solving the Multiobjective Quasi-Clique Problem
by: Santos, Daniela Scherer dos, et al.
Published: (2024)

An Exact Solver for Submodular Knapsack Problems
by: Münch, Sabine, et al.
Published: (2025)

The Role of Dimension in the Online Chasing Problem
by: Papazov, Hristo
Published: (2023)

Functional design of efficient and parallelizable combinatorial generators using convolution
by: He, Xi, et al.
Published: (2025)

Partially Ordered Sets Corresponding to the Partition Problem
by: Kubo, Susumu
Published: (2024)

Parameterized Algorithms for Balanced Cluster Edge Modification Problems
by: Madathil, Jayakrishnan, et al.
Published: (2024)

Algorithmic Results for Weak Roman Domination Problem in Graphs
by: Paul, Kaustav, et al.
Published: (2024)

On The Maximum Linear Arrangement Problem for Trees
by: Alemany-Puig, Lluís, et al.
Published: (2023)

A Nearly Optimal Deterministic Algorithm for Online Transportation Problem
by: Harada, Tsubasa, et al.
Published: (2024)

Efficient Online Sensitivity Analysis For The Injective Bottleneck Path Problem
by: Kaymakov, Kirill V., et al.
Published: (2024)

Minsum Problem for Discrete and Weighted Set Flow on Dynamic Path Network
by: Manna, Bubai, et al.
Published: (2024)

Greediness is not always a vice: Efficient Discovery Algorithms for Assignment Problems
by: Duvignau, Romaric, et al.
Published: (2024)

Solving the List Coloring Problem through a Branch-and-Price algorithm
by: Lucci, Mauro, et al.
Published: (2023)

Beware of the Classical Benchmark Instances for the Traveling Salesman Problem with Time Windows
by: Soulignac, Francisco J.
Published: (2025)