Cover Image

Approximation and Hardness of Polychromatic TSP

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Schibler, Thomas, Suri, Subhash, Xue, Jie
Format:	Preprint
Published:	2025
Subjects:	Computational Geometry
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Embedding Graphs as Euclidean kNN-Graphs
by: Schibler, T., et al.
Published: (2025)

Approximating Convex Hulls via Range Queries
by: Schibler, T., et al.
Published: (2026)

Parameterized Approximation of Rectangle Stabbing
by: Chu, Huairui, et al.
Published: (2026)

Polychromatic Coloring of Tuples in Hypergraphs
by: Biniaz, Ahmad, et al.
Published: (2025)

Faster Approximation Scheme for Euclidean $k$-TSP
by: van Wijland, Ernest, et al.
Published: (2023)

A Gap-ETH-Tight Approximation Scheme for Euclidean TSP
by: Kisfaludi-Bak, Sándor, et al.
Published: (2020)

Euclidean TSP in Narrow Strips
by: Alkema, Henk, et al.
Published: (2020)

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

Bollobás-Meir TSP Conjecture Holds Asymptotically
by: Gordeev, Alexey
Published: (2026)

Hardness and Approximation Schemes for Discrete Packing and Domination
by: Madireddy, Raghunath Reddy, et al.
Published: (2025)

Balanced TSP partitioning
by: Berendsohn, Benjamin Aram, et al.
Published: (2025)

Gap-ETH-Tight Algorithms for Hyperbolic TSP and Steiner Tree
by: Kisfaludi-Bak, Sándor, et al.
Published: (2026)

Improved Hardness of Approximation for Geometric Bin Packing
by: Ray, Arka, et al.
Published: (2023)

An $O(n \log n)$-Time Approximation Scheme for Geometric Many-to-Many Matching
by: Bandyapadhyay, Sayan, et al.
Published: (2024)

Online sorting and online TSP: randomized, stochastic, and high-dimensional
by: Abrahamsen, Mikkel, et al.
Published: (2024)

Bipartizing (Pseudo-)Disk Graphs: Approximation with a Ratio Better than 3
by: Lokshtanov, Daniel, et al.
Published: (2024)

An Improved Upper Bound for the Euclidean TSP Constant Using Band Crossovers
by: Gaudio, Julia, et al.
Published: (2026)

Who Needs Crossings?: Noncrossing Linkages are Universal, and Deciding (Global) Rigidity is Hard
by: Abel, Zachary, et al.
Published: (2025)

Generating Diverse TSP Tours via a Combination of Graph Pointer Network and Dispersion
by: Yang, Hao-Tsung, et al.
Published: (2026)

Near-Linear and Parameterized Approximations for Maximum Cliques in Disk Graphs
by: Gao, Jie, et al.
Published: (2025)

Approximating Gromov-Hausdorff Distance in Euclidean Space
by: Majhi, Sushovan, et al.
Published: (2019)

Flipping Matchings is Hard
by: Binucci, Carla, et al.
Published: (2025)

Hardness of Packing, Covering and Partitioning Simple Polygons with Unit Squares
by: Abrahamsen, Mikkel, et al.
Published: (2024)

Hard diagrams of split links
by: Lunel, Corentin, et al.
Published: (2024)

Optimal Algorithm for the Planar Two-Center Problem
by: Cho, Kyungjin, et al.
Published: (2020)

Stability and Approximations for Decorated Reeb Spaces
by: Curry, Justin, et al.
Published: (2023)

Approximating the Directed Hausdorff Distance
by: Chubet, Oliver A., et al.
Published: (2025)

Proof of Dudley's Convex Approximation
by: Har-Peled, Sariel, et al.
Published: (2019)

Approximation Depth of Convex Polytopes
by: Bakaev, Egor, et al.
Published: (2025)

Lower bounds for the universal TSP on the plane
by: Kravaris, Cosmas
Published: (2024)

On Approximation Schemes for Stabbing Rectilinear Polygons
by: Khan, Arindam, et al.
Published: (2024)

Approximation Algorithms for Anchored Multiwatchman Routes
by: Mitchell, Joseph S. B., et al.
Published: (2024)

Closed curve covering and multiagent TSP ratios
by: Dillon, Travis, et al.
Published: (2025)

Algorithms for Halfplane Coverage and Related Problems
by: Wang, Haitao, et al.
Published: (2024)

Polygon Containment and Translational Min-Hausdorff-Distance between Segment Sets are 3SUM-Hard
by: Barequet, Gill, et al.
Published: (2025)

Optimal Area-Sensitive Bounds for Polytope Approximation
by: Arya, Sunil, et al.
Published: (2023)

Approximating Densest Subgraph in Geometric Intersection Graphs
by: Har-Peled, Sariel, et al.
Published: (2024)

Fast Approximation Algorithms for Piercing Boxes by Points
by: Agarwal, Pankaj K., et al.
Published: (2023)

On Stable Approximation Algorithms for Geometric Coverage Problems
by: de Berg, Mark, et al.
Published: (2024)

Optimal Volume-Sensitive Bounds for Polytope Approximation
by: Arya, Sunil, et al.
Published: (2023)