Cover Image

A $(5/3+ε)$-Approximation for Tricolored Non-crossing Euclidean TSP

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Baligács, Júlia, Disser, Yann, Feldmann, Andreas Emil, Zych-Pawlewicz, Anna
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

Dynamic Parameterized Feedback Problems in Tournaments
by: Zych-Pawlewicz, Anna, et al.
Published: (2024)

Parameterized dynamic data structure for Split Completion
by: Majewski, Konrad, et al.
Published: (2024)

A Linear Time Gap-ETH-Tight Approximation Scheme for Euclidean TSP
by: Mömke, Tobias, et al.
Published: (2024)

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

Improved FPT Approximation for Non-metric TSP
by: Bampis, Evripidis, et al.
Published: (2024)

Dynamic data structures for twin-ordered matrices
by: Bosek, Bartłomiej, et al.
Published: (2026)

Parameterized Approximation Algorithms for TSP on Non-Metric Graphs
by: Zhao, Jingyang, et al.
Published: (2025)

4/3-Approximation of Graphic TSP
by: Çivril, Ali
Published: (2023)

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

Highway Dimension: a Metric View
by: Feldmann, Andreas Emil, et al.
Published: (2024)

Parameterized Algorithms for Steiner Forest in Bounded Width Graphs
by: Feldmann, Andreas Emil, et al.
Published: (2024)

A Survey of Approximability Results for Traveling Salesman Problems using the TSP-T3CO Definition Scheme
by: Saller, Sophia, et al.
Published: (2023)

Fair Vertex Problems Parameterized by Cluster Vertex Deletion
by: Masařík, Tomáš, et al.
Published: (2025)

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

Generalized $k$-Center: Distinguishing Doubling and Highway Dimension
by: Feldmann, Andreas Emil, et al.
Published: (2022)

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

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

Approximating Asymmetric A Priori TSP beyond the Adaptivity Gap
by: Christalla, Manuel, et al.
Published: (2025)

Approximation Schemes for Orienteering and Deadline TSP in Doubling Metrics
by: Ren, Kinter, et al.
Published: (2024)

Improved Approximation Algorithms for (1,2)-TSP and Max-TSP Using Path Covers in the Semi-Streaming Model
by: Alipour, Sharareh, et al.
Published: (2025)

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

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

A Polylogarithmic Competitive Algorithm for Stochastic Online Sorting and TSP
by: Kalavas, Andreas, et al.
Published: (2025)

A Polylogarithmic Competitive Algorithm for Stochastic Online Sorting and TSP
by: Kalavas, Andreas, et al.
Published: (2025)

A $(\frac32+\frac1{\mathrm{e}})$-Approximation Algorithm for Ordered TSP
by: Armbruster, Susanne, et al.
Published: (2024)

A $(1+ε)$-Approximation for Ultrametric Embedding in Subquadratic Time
by: Bathie, Gabriel, et al.
Published: (2025)

$(1-ε)$-Approximation of Knapsack in Nearly Quadratic Time
by: Mao, Xiao
Published: (2023)

Approximating the Held-Karp Bound for Metric TSP in Nearly Linear Work and Polylogarithmic Depth
by: Koh, Zhuan Khye, et al.
Published: (2024)

Online Metric TSP
by: Bertram, Christian
Published: (2025)

Decremental $(1+ε)$-Approximate Maximum Eigenvector: Dynamic Power Method
by: Adil, Deeksha, et al.
Published: (2024)

Dynamic $(1+ε)$-Approximate Matching Size in Truly Sublinear Update Time
by: Bhattacharya, Sayan, et al.
Published: (2023)

Dual Charging for Half-Integral TSP
by: Klein, Nathan, et al.
Published: (2025)

Sublinear Algorithms for TSP via Path Covers
by: Behnezhad, Soheil, et al.
Published: (2023)

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

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

Dynamic Deterministic Constant-Approximate Distance Oracles with $n^ε$ Worst-Case Update Time
by: Haeupler, Bernhard, et al.
Published: (2024)

Parallel $(1+ε)$-Approximate Multi-Commodity Mincost Flow in Almost Optimal Depth and Work
by: Haeupler, Bernhard, et al.
Published: (2025)

Dynamic $((1+ε)\ln n)$-Approximation Algorithms for Minimum Set Cover and Dominating Set
by: Solomon, Shay, et al.
Published: (2023)

Matroid-Based TSP Rounding for Half-Integral Solutions
by: Gupta, Anupam, et al.
Published: (2021)

Waiting is not easy but worth it: the online TSP on the line revisited
by: Chen, Pei-Chuan, et al.
Published: (2019)