Buchumschlag

On the Approximability of Train Routing and the Min-Max Disjoint Paths Problem

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Bhaskar, Umang, Eickhoff, Katharina, Kauther, Lennart, Matuschke, Jannik, Peis, Britta, Koch, Laura Vargas
Format:	Preprint
Veröffentlicht:	2025
Schlagworte:	Data Structures and Algorithms Computational Complexity
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Parameterized Maximum Node-Disjoint Paths
von: Lampis, Michael, et al.
Veröffentlicht: (2024)

Parameterized Max Min Feedback Vertex Set
von: Lampis, Michael, et al.
Veröffentlicht: (2023)

When to Identify Is to Control: On the Controllability of Combinatorial Optimization Problems
von: Klimm, Max, et al.
Veröffentlicht: (2026)

Simultaneous Network Design with Restricted Link Usage
von: Kakimura, Naonori, et al.
Veröffentlicht: (2025)

On the Parameterized Complexity of Min-Sum-Radii
von: Kumar, Pankaj, et al.
Veröffentlicht: (2026)

Hardness Results on Characteristics for Elastic-Degenerated Strings
von: Köppl, Dominik, et al.
Veröffentlicht: (2024)

On the (In)Approximability of the Monitoring Edge Geodetic Set Problem
von: Bilò, Davide, et al.
Veröffentlicht: (2025)

Limits of Kernelization and Parametrization for Phylogenetic Diversity with Dependencies
von: Holtgrefe, Niels, et al.
Veröffentlicht: (2026)

A tight quasi-polynomial bound for Global Label Min-Cut
von: Jaffke, Lars, et al.
Veröffentlicht: (2022)

Search-space Reduction for Boolean MinCSPs via Essential Constraints
von: Jansen, Bart M. P., et al.
Veröffentlicht: (2026)

Improved Hardness and Approximations for Cardinality-Based Minimum $s$-$t$ Cuts Problems in Hypergraphs
von: Adriaens, Florian, et al.
Veröffentlicht: (2024)

Fare Zone Assignment on Trees
von: Hoefer, Martin, et al.
Veröffentlicht: (2025)

Multi-Pass Streaming Lower Bounds for Approximating Max-Cut
von: Fei, Yumou, et al.
Veröffentlicht: (2025)

On the (Classical and Quantum) Fine-Grained Complexity of Approximate CVP and Max-Cut
von: Huang, Jeremy Ahrens, et al.
Veröffentlicht: (2024)

Superpolynomial smoothed complexity of 3-FLIP in Local Max-Cut
von: Michel, Lukas, et al.
Veröffentlicht: (2023)

Parameterized Complexity of Vehicle Routing
von: Döring, Michelle, et al.
Veröffentlicht: (2025)

Self-referential instances of the dominating set problem are irreducible
von: Zhou, Guangyan
Veröffentlicht: (2026)

On Approximability of $\ell_2^2$ Min-Sum Clustering
von: S., Karthik C., et al.
Veröffentlicht: (2024)

On Equivalence of Parameterized Inapproximability of k-Median, k-Max-Coverage, and 2-CSP
von: S., Karthik C., et al.
Veröffentlicht: (2024)

Parameterized Restless Temporal Path
von: Cauvi, Justine, et al.
Veröffentlicht: (2025)

Faster Exponential-Time Approximation Algorithms Using Approximate Monotone Local Search
von: Esmer, Barış Can, et al.
Veröffentlicht: (2022)

Maximization of Approximately Submodular Functions
von: Horel, Thibaut, et al.
Veröffentlicht: (2024)

PLS-complete problems with lexicographic cost functions: Max-$k$-SAT and Abelian Permutation Orbit Minimization
von: Scheder, Dominik, et al.
Veröffentlicht: (2025)

Improved Hardness-of-Approximation for Token Swapping
von: Hiken, Sam, et al.
Veröffentlicht: (2024)

On the Hardness of Approximation of the Fair k-Center Problem
von: Thejaswi, Suhas
Veröffentlicht: (2026)

On Approximating the Dynamic and Discrete Network Flow Problem
von: Manna, Bubai, et al.
Veröffentlicht: (2024)

Better Bounds for Semi-Streaming Single-Source Shortest Paths
von: Assadi, Sepehr, et al.
Veröffentlicht: (2025)

The Structural Complexity Landscape of Finding Balance-Fair Shortest Paths
von: Bentert, Matthias, et al.
Veröffentlicht: (2024)

Tight Streaming Lower Bounds for Deterministic Approximate Counting
von: Wang, Yichuan
Veröffentlicht: (2024)

Linear Space Streaming Lower Bounds for Approximating CSPs
von: Chou, Chi-Ning, et al.
Veröffentlicht: (2021)

A Note on Approximability of Densest At-Least-k-Subgraph
von: Laekhanukit, Bundit, et al.
Veröffentlicht: (2026)

Capacitated Fair-Range Clustering: Hardness and Approximation Algorithms
von: Gadekar, Ameet, et al.
Veröffentlicht: (2025)

Sublinear-Time Approximation for Graph Frequency Vectors in Hyperfinite Graphs
von: Moroie, Gregory
Veröffentlicht: (2025)

Optimal Single-Pass Streaming Lower Bounds for Approximating CSPs
von: Singer, Noah G., et al.
Veröffentlicht: (2026)

Settling the Pass Complexity of Approximate Matchings in Dynamic Graph Streams
von: Assadi, Sepehr, et al.
Veröffentlicht: (2024)

Tight Space Lower Bound for Pseudo-Deterministic Approximate Counting
von: Grossman, Ofer, et al.
Veröffentlicht: (2023)

U-Bubble Model for Mixed Unit Interval Graphs and its Applications: The MaxCut Problem Revisited
von: Kratochvíl, Jan, et al.
Veröffentlicht: (2020)

Scheduling Problems with Constrained Rejections
von: Davies, Sami, et al.
Veröffentlicht: (2025)

A Simpler Exponential-Time Approximation Algorithm for MAX-k-SAT
von: Buhrman, Harry, et al.
Veröffentlicht: (2025)

On the Constant-Factor Approximability of Minimum Cost Constraint Satisfaction Problems
von: DeHaan, Ian, et al.
Veröffentlicht: (2025)