Cover Image

Polynomial Time Learning-Augmented Algorithms for NP-hard Permutation Problems

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Bampis, Evripidis, Escoffier, Bruno, Fotakis, Dimitris, Patsilinakos, Panagiotis, Xefteris, Michalis
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Parsimonious Learning-Augmented Approximations for Dense Instances of $\mathcal{NP}$-hard Problems
by: Bampis, Evripidis, et al.
Published: (2024)

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

A Competitive Posted-Price Mechanism for Online Budget-Feasible Auctions
by: Charalampopoulos, Andreas, et al.
Published: (2025)

An FPT Algorithm for the Exact Matching Problem and NP-hardness of Related Problems
by: Murakami, Hitoshi, et al.
Published: (2024)

NP-hardness and a PTAS for the Euclidean Steiner Line Problem
by: Bartlmae, Simon, et al.
Published: (2024)

Polynomial-Time Algorithms for Weaver's Discrepancy Problem in a Dense Regime
by: Jourdan, Ben, et al.
Published: (2024)

A Polynomial-Time Deterministic Algorithm for an NP-Complete Problem
by: Jiang, Xinwen, et al.
Published: (2021)

A Query-Driven Approach to Space-Efficient Range Searching
by: Fotakis, Dimitris, et al.
Published: (2025)

Algorithmic Reductions: Network Flow and NP-Completeness in Real-World Scheduling Problems
by: Sinhal, Anay, et al.
Published: (2026)

Repeated Descent: A Framework for Online Budget-Feasible Auctions
by: Charalampopoulos, Andreas, et al.
Published: (2026)

A Polynomial-Time Algorithm for the Next-to-Shortest Path Problem on Positively Weighted Directed Graphs
by: Chen, Kuowen, et al.
Published: (2025)

Improved Bounds for Online Facility Location with Predictions
by: Fotakis, Dimitris, et al.
Published: (2021)

Efficient Parameter Estimation of Truncated Boolean Product Distributions
by: Fotakis, Dimitris, et al.
Published: (2020)

Minimizing the Number of Tardy Jobs and Maximal Tardiness on a Single Machine is NP-hard
by: Heeger, Klaus, et al.
Published: (2024)

Learning-Augmented Online Algorithms for Nonclairvoyant Joint Replenishment Problem with Deadlines
by: Dinitz, Michael, et al.
Published: (2025)

DNA Probe Computing System for Solving NP-Complete Problems
by: Xu, Jin, et al.
Published: (2025)

The APX-hardness of the Traveling Tournament Problem
by: Zhao, Jingyang, et al.
Published: (2023)

Polynomial Time Algorithms for Integer Programming and Unbounded Subset Sum in the Total Regime
by: Aggarwal, Divesh, et al.
Published: (2024)

Learning-Augmented Online Covering Problems
by: Ameli, Afrouz Jabal, et al.
Published: (2025)

Solving NP-hard Problems on \textsc{GaTEx} Graphs: Linear-Time Algorithms for Perfect Orderings, Cliques, Colorings, and Independent Sets
by: Hellmuth, Marc, et al.
Published: (2023)

Competitive Query Minimization for Stable Matching with One-Sided Uncertainty
by: Bampis, Evripidis, et al.
Published: (2024)

Hypergraph Connectivity Augmentation in Strongly Polynomial Time
by: Bérczi, Kristóf, et al.
Published: (2024)

A Fixed Parameter Tractable Approach for Solving the Vertex Cover Problem in Polynomial Time Complexity
by: Tayal, Mumuksh
Published: (2025)

Optimal Learning-Augmented Algorithm for Online Bidding
by: Lee, Changyeol, et al.
Published: (2026)

Improved Algorithm for Permutation Testing
by: Zhang, Xiaojin
Published: (2020)

A Polynomial time Algorithm for 3SAT
by: Du, Lizhi
Published: (2010)

Computational-Statistical Tradeoffs from NP-hardness
by: Blanc, Guy, et al.
Published: (2025)

On Tight FPT Time Approximation Algorithms for k-Clustering Problems
by: Dai, Han, et al.
Published: (2025)

A Polynomial Time Algorithm for Steiner Tree when Terminals Avoid a $K_4$-Minor
by: Groenland, Carla, et al.
Published: (2024)

Learning-Augmented Streaming Algorithms for Approximating MAX-CUT
by: Dong, Yinhao, et al.
Published: (2024)

NP-Hardness and a PTAS for the Pinwheel Problem
by: Kleinberg, Robert, et al.
Published: (2026)

A Fully Polynomial-Time Algorithm for Robustly Learning Halfspaces over the Hypercube
by: Chandrasekaran, Gautam, et al.
Published: (2025)

Hypergraph Unreliability in Quasi-Polynomial Time
by: Cen, Ruoxu, et al.
Published: (2024)

Permutation patterns in streams
by: Berendsohn, Benjamin Aram
Published: (2025)

Split Algorithm in Linear Time for the Vehicle Routing Problem with Simultaneous Pickup and Delivery and Time Windows
by: Gibbons, Ethan, et al.
Published: (2026)

Quantum Speedups for Polynomial-Time Dynamic Programming Algorithms
by: Caroppo, Susanna, et al.
Published: (2025)

Faster Algorithms for Longest Common Substring
by: Charalampopoulos, Panagiotis, et al.
Published: (2021)

An $\mathcal{O}(\log N)$ Time Algorithm for the Generalized Egg Dropping Problem
by: Papadopoulos, Kleitos
Published: (2026)

An Invitation to "Fine-grained Complexity of NP-Complete Problems"
by: Nederlof, Jesper
Published: (2026)

Learning-Augmented Algorithms for the Bahncard Problem
by: Zhao, Hailiang, et al.
Published: (2024)