Cover Image

On the Integrality Gap of Directed Steiner Tree LPs with Relatively Integral Solutions

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Laekhanukit, Bundit
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms Discrete Mathematics 68Q25, 68R10, 90C35 F.2.2; G.2.2
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Interval Graphs are Reconstructible
by: Heinrich, Irene, et al.
Published: (2025)

Simple Combinatorial Construction of the $k^{o(1)}$-Lower Bound for Approximating the Parameterized $k$-Clique
by: Chen, Yijia, et al.
Published: (2023)

Searching in trees with monotonic query times
by: Dereniowski, Dariusz, et al.
Published: (2024)

Pliability and Approximating Max-CSPs
by: Romero, Miguel, et al.
Published: (2019)

A near-complete resolution of the exponential-time complexity of k-opt for the traveling salesman problem
by: Heimann, Sophia, et al.
Published: (2025)

Extending Exact Integrality Gap Computations for the Metric TSP
by: Cook, William, et al.
Published: (2026)

The $k$-Opt algorithm for the Traveling Salesman Problem has exponential running time for $k \ge 5$
by: Heimann, Sophia, et al.
Published: (2024)

The Bottom-Left Algorithm for the Strip Packing Problem
by: Hougardy, Stefan, et al.
Published: (2024)

Almost Tight Approximation Hardness for Single-Source Directed k-Edge-Connectivity
by: Liao, Chao, et al.
Published: (2022)

On the twin-width of near-regular graphs
by: Heinrich, Irene, et al.
Published: (2025)

Fast Shortest Path in Graphs With Sparse Signed Tree Models and Applications
by: Bonnet, Édouard, et al.
Published: (2026)

On the thinness of trees
by: Bonomo-Braberman, Flavia, et al.
Published: (2025)

A Fast 3-Approximation for the Capacitated Tree Cover Problem with Edge Loads
by: Rockel-Wolff, Benjamin
Published: (2024)

Continuous Flattening and Reversing of Convex Polyhedral Linkages
by: Demaine, Erik D., et al.
Published: (2024)

Fully Dynamic Breadth First Search and Spanning Trees in Directed Graphs
by: Morse, Gregory, et al.
Published: (2026)

Answering Related Questions
by: Bonnet, Édouard
Published: (2025)

A Constant Factor Approximation for Directed Feedback Vertex Set in Graphs of Bounded Genus
by: Sun, Hao
Published: (2023)

A 13/6-Approximation for Strip Packing via the Bottom-Left Algorithm
by: Hougardy, Stefan, et al.
Published: (2025)

Submodular Maximization over a Matroid $k$-Intersection: Multiplicative Improvement over Greedy
by: Feldman, Moran, et al.
Published: (2026)

Competitive Query Minimization for Stable Matching with One-Sided Uncertainty
by: Bampis, Evripidis, et al.
Published: (2024)

Bicriteria Submodular Maximization
by: Feldman, Moran, et al.
Published: (2025)

Experimental algorithms for the dualization problem
by: Mezzini, Mauro, et al.
Published: (2025)

Coloring Hardness on Low Twin-Width Graphs
by: Bonnet, Édouard
Published: (2025)

An Explicit and Efficient $O(n^2)$-Time Algorithm for Sorting Sumsets
by: Mundhra, S.
Published: (2025)

Boltzmann sampling and optimal exact-size sampling for directed acyclic graphs
by: Gabryelski, Wojciech, et al.
Published: (2026)

Revisiting Chazelle's Implementation of the Bottom-Left Heuristic: A Corrected and Rigorous Analysis
by: Michel, Stefan
Published: (2025)

Adjacency Labeling Schemes for Small Classes
by: Bonnet, Édouard, et al.
Published: (2024)

Loop unrolling of UCA models: distance labeling
by: Soulignac, Francisco J, et al.
Published: (2022)

Extending the Extension: Deterministic Algorithm for Non-monotone Submodular Maximization
by: Buchbinder, Niv, et al.
Published: (2024)

Star-Struck by Fixed Embeddings: Modern Crossing Number Heuristics
by: Chimani, Markus, et al.
Published: (2021)

Tighter Approximation for the Uniform Cost-Distance Steiner Tree Problem
by: Foos, Josefine, et al.
Published: (2023)

On the PLS-Completeness of $k$-Opt Local Search for the Traveling Salesman Problem
by: Heimann, Sophia, et al.
Published: (2026)

Optimized Degree Realization: Minimum Dominating Set & Maximum Matching
by: Bar-Noy, Amotz, et al.
Published: (2025)

Directed Capacity-Preserving Subgraphs: Hardness and Exact Polynomial Algorithms
by: Chimani, Markus, et al.
Published: (2023)

Simple Approximations for General Spanner Problems
by: Bökler, Fritz, et al.
Published: (2025)

Exact Minimum Weight Spanners via Column Generation
by: Bökler, Fritz, et al.
Published: (2024)

Deterministic Minimum Steiner Cut in Maximum Flow Time
by: Ding, Matthew, et al.
Published: (2023)

On the Approximation Ratio of the $k$-Opt and Lin-Kernighan Algorithm
by: Zhong, Xianghui
Published: (2019)

Temporalizing digraphs via linear-size balanced bi-trees
by: Bessy, Stéphane, et al.
Published: (2023)

Highly Connected Steiner Subgraph -- Parameterized Algorithms and Applications to Hitting Set Problems
by: Eiben, Eduard, et al.
Published: (2023)