Buchumschlag

NP-hardness and a PTAS for the Euclidean Steiner Line Problem

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Bartlmae, Simon, Jünger, Paul J., Langetepe, Elmar
Format:	Preprint
Veröffentlicht:	2024
Schlagworte:	Computational Geometry Data Structures and Algorithms
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Simple Grid Polygon Online Exploration Revisited
von: Brock, Maximilian, et al.
Veröffentlicht: (2024)

A PTAS for Travelling Salesman Problem with Neighbourhoods Over Parallel Line Segments of Similar Length
von: Ghaseminia, Benyamin, et al.
Veröffentlicht: (2025)

NP-Hardness and a PTAS for the Pinwheel Problem
von: Kleinberg, Robert, et al.
Veröffentlicht: (2026)

Revisiting ILP Models for Exact Crossing Minimization in Storyline Drawings
von: Dobler, Alexander, et al.
Veröffentlicht: (2024)

Spanners in Planar Domains via Steiner Spanners and non-Steiner Tree Covers
von: Bhore, Sujoy, et al.
Veröffentlicht: (2024)

The Complexity of Geodesic Spanners using Steiner Points
von: de Berg, Sarita, et al.
Veröffentlicht: (2024)

Min-1-Planarity is NP-Hard
von: Okada, Yuto
Veröffentlicht: (2026)

On the Line-Separable Unit-Disk Coverage and Related Problems
von: Liu, Gang, et al.
Veröffentlicht: (2023)

On Line-Separable Weighted Unit-Disk Coverage and Related Problems
von: Liu, Gang, et al.
Veröffentlicht: (2024)

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

On Subexponential Parameterized Algorithms for Steiner Tree on Intersection Graphs of Geometric Objects
von: Bhore, Sujoy, et al.
Veröffentlicht: (2025)

Space Complexity of Euclidean Clustering
von: Zhu, Xiaoyi, et al.
Veröffentlicht: (2024)

Parameterized Algorithms for the Drone Delivery Problem
von: Bartlmae, Simon, et al.
Veröffentlicht: (2026)

Unweighted Geometric Hitting Set for Line-Constrained Disks and Related Problems
von: Liu, Gang, et al.
Veröffentlicht: (2024)

Faster Approximation Scheme for Euclidean $k$-TSP
von: van Wijland, Ernest, et al.
Veröffentlicht: (2023)

Euclidean distance compression via deep random features
von: Leroux, Brett, et al.
Veröffentlicht: (2024)

On Optimal Coreset Construction for Euclidean $(k,z)$-Clustering
von: Huang, Lingxiao, et al.
Veröffentlicht: (2022)

On Approximability of Steiner Tree in $\ell_p$-metrics
von: Fleischmann, Henry, et al.
Veröffentlicht: (2023)

Duality between Lines and Points
von: Saxena, Sanjeev
Veröffentlicht: (2025)

A Framework for the Design of Efficient Diversification Algorithms to NP-Hard Problems
von: Gálvez, Waldo, et al.
Veröffentlicht: (2025)

On Planar Straight-Line Dominance Drawings
von: Angelini, Patrizio, et al.
Veröffentlicht: (2025)

PACE Solver Description: Exact Solution of the One-sided Crossing Minimization Problem by the MPPEG Team
von: Jünger, Michael, et al.
Veröffentlicht: (2024)

Flow-weighted Layered Metric Euclidean Capacitated Steiner Tree Problem
von: Bläsius, Thomas, et al.
Veröffentlicht: (2025)

On connections between k-coloring and Euclidean k-means
von: Aman, Enver, et al.
Veröffentlicht: (2024)

Dominance for Containment Problems
von: Akram, Waseem, et al.
Veröffentlicht: (2022)

Fine-Grained Complexity of Continuous Euclidean k-Center
von: Blank, Lotte, et al.
Veröffentlicht: (2026)

Near-Optimal Bounds for Parameterized Euclidean k-means
von: Cohen-Addad, Vincent, et al.
Veröffentlicht: (2026)

Boosting Rectilinear Steiner Minimum Tree Algorithms with Augmented Bounding Volume Hierarchy
von: Yang, Puhan, et al.
Veröffentlicht: (2025)

A Gap-ETH-Tight Approximation Scheme for Euclidean TSP
von: Kisfaludi-Bak, Sándor, et al.
Veröffentlicht: (2020)

Slant/Gokigen Naname is NP-complete, and Some Variations are in P
von: Lynch, Jayson, et al.
Veröffentlicht: (2025)

Algorithms for Halfplane Coverage and Related Problems
von: Wang, Haitao, et al.
Veröffentlicht: (2024)

Range Counting Oracles for Geometric Problems
von: Driemel, Anne, et al.
Veröffentlicht: (2025)

On Approximating the Weighted Region Problem in Square Tessellations
von: Kakimura, Naonori, et al.
Veröffentlicht: (2024)

Improved Algorithms for Distance Selection and Related Problems
von: Wang, Haitao, et al.
Veröffentlicht: (2023)

On the Complexity of the Ordered Covering Problem in Distance Geometry
von: Souza, Michael, et al.
Veröffentlicht: (2025)

Almost-Optimal Upper and Lower Bounds for Clustering in Low Dimensional Euclidean Spaces
von: Cohen-Addad, Vincent, et al.
Veröffentlicht: (2026)

Polynomial Time Learning-Augmented Algorithms for NP-hard Permutation Problems
von: Bampis, Evripidis, et al.
Veröffentlicht: (2025)

Single-Source Shortest Path Problem in Weighted Disk Graphs
von: An, Shinwoo, et al.
Veröffentlicht: (2025)

The Contiguous Art Gallery Problem is in Θ(n log n)
von: de Berg, Sarita, et al.
Veröffentlicht: (2025)

Robust Algorithms for Path and Cycle Problems in Geometric Intersection Graphs
von: Marin, Malory, et al.
Veröffentlicht: (2025)