Copertina

TSP Escapes the $O(2^n n^2)$ Curse

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autore principale:	Stoian, Mihail
Natura:	Preprint
Pubblicazione:	2024
Soggetti:	Data Structures and Algorithms Computational Complexity
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

The Art of Staying Ahead of Deadlines: Improved Algorithms for the Minimum Tardy Processing Time
di: Stoian, Mihail
Pubblicazione: (2024)

Mind the Gap. Doubling Constant Parametrization of Weighted Problems: TSP, Max-Cut, and More
di: Stoian, Mihail
Pubblicazione: (2026)

PCF Learned Sort: a Learning Augmented Sort Algorithm with $O(n \log\log n)$ Expected Complexity
di: Sato, Atsuki, et al.
Pubblicazione: (2024)

An $\widetilde{O} (n^{3/7})$ Round Parallel Algorithm for Matroid Bases
di: Khanna, Sanjeev, et al.
Pubblicazione: (2026)

Randomized $\tilde{O}(m\sqrt{n})$ Bellman-Ford from Fineman and the Boilermakers
di: Rao, Satish
Pubblicazione: (2025)

Counting Locally Optimal Tours in the TSP
di: Manthey, Bodo, et al.
Pubblicazione: (2024)

Vector TSP: A Traveling Salesperson Problem with Racetrack-like Acceleration Constraints
di: Casteigts, Arnaud, et al.
Pubblicazione: (2020)

Did Fourier Really Meet Möbius? Fast Subset Convolution via FFT
di: Stoian, Mihail
Pubblicazione: (2024)

Approximate Min-Sum Subset Convolution
di: Stoian, Mihail
Pubblicazione: (2024)

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

Self-referential instances of the dominating set problem are irreducible
di: Zhou, Guangyan
Pubblicazione: (2026)

An $Ω( (\log n / \log \log n)^2 )$ Cell-Probe Lower Bound for Dynamic Boolean Data Structures
di: Ko, Young Kun
Pubblicazione: (2026)

$O(n +f(k))$: Truly Linear FPT
di: Bumpus, Benjamin Merlin, et al.
Pubblicazione: (2026)

Boolean function monotonicity testing requires (almost) $n^{1/2}$ queries
di: Chen, Mark, et al.
Pubblicazione: (2025)

3-Local Hamiltonian Problem and Constant Relative Error Quantum Partition Function Approximation: $O(2^{\frac{n}{2}})$ Algorithm Is Nearly Optimal under QSETH
di: Chia, Nai-Hui, et al.
Pubblicazione: (2025)

An $\mathcal{O}(n)$ Space Construction of Superpermutations
di: Ajmera, Dhruv
Pubblicazione: (2025)

On the Complexity of 2-club Cluster Editing with Vertex Splitting
di: Abu-Khzam, Faisal N., et al.
Pubblicazione: (2024)

Nemesis, an Escape Game in Graphs
di: Bergé, Pierre, et al.
Pubblicazione: (2026)

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

Conditional lower bounds for sparse parameterized 2-CSP: A streamlined proof
di: S., Karthik C., et al.
Pubblicazione: (2023)

Certifying Euclidean Sections and Finding Planted Sparse Vectors Beyond the $\sqrt{n}$ Dimension Threshold
di: Guruswami, Venkatesan, et al.
Pubblicazione: (2024)

On $[1,2]$-Domination in Interval and Circle Graphs
di: Meybodi, Mohsen Alambardar, et al.
Pubblicazione: (2024)

Can You Link Up With Treewidth?
di: Curticapean, Radu, et al.
Pubblicazione: (2024)

Tight Streaming Lower Bounds for Deterministic Approximate Counting
di: Wang, Yichuan
Pubblicazione: (2024)

Simple approximation algorithms for Polyamorous Scheduling
di: Biktairov, Yuriy, et al.
Pubblicazione: (2024)

Size Minimization For Multi-Output AND-Functions
di: Armbruster, Susanne
Pubblicazione: (2024)

Cluster Editing on Cographs and Related Classes
di: Lafond, Manuel, et al.
Pubblicazione: (2024)

Improved Hardness-of-Approximation for Token Swapping
di: Hiken, Sam, et al.
Pubblicazione: (2024)

Near-Optimal Averaging Samplers and Matrix Samplers
di: Xun, Zhiyang, et al.
Pubblicazione: (2024)

On the complexity and approximability of Bounded access Lempel Ziv coding
di: Cicalese, Ferdinando, et al.
Pubblicazione: (2024)

Parameterized Vertex Integrity Revisited
di: Hanaka, Tesshu, et al.
Pubblicazione: (2024)

On approximability of the Permanent of PSD matrices
di: Ebrahimnejad, Farzam, et al.
Pubblicazione: (2024)

Further Explanations on "SAT Requires Exhaustive Search"
di: Dong, Qingxiu, et al.
Pubblicazione: (2024)

Randomized query composition and product distributions
di: Sanyal, Swagato
Pubblicazione: (2024)

Minimizing the Weighted Number of Tardy Jobs is W[1]-hard
di: Heeger, Klaus, et al.
Pubblicazione: (2024)

On Permutation Selectors and their Applications in Ad-Hoc Radio Networks Protocols
di: Kuschner, Jordan, et al.
Pubblicazione: (2024)

A constant time complexity algorithm for the unbounded knapsack problem with bounded coefficients
di: Yang, Yang
Pubblicazione: (2024)

Towards Deterministic Algorithms for Constant-Depth Factors of Constant-Depth Circuits
di: Kumar, Mrinal, et al.
Pubblicazione: (2024)

Solving Polynomial Equations Over Finite Fields
di: Dell, Holger, et al.
Pubblicazione: (2024)

The Structural Complexity Landscape of Finding Balance-Fair Shortest Paths
di: Bentert, Matthias, et al.
Pubblicazione: (2024)