Buchumschlag

Parsimonious Learning-Augmented Approximations for Dense Instances of $\mathcal{NP}$-hard Problems

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Bampis, Evripidis, Escoffier, Bruno, Xefteris, Michalis
Format:	Preprint
Veröffentlicht:	2024
Schlagworte:	Data Structures and Algorithms
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Polynomial Time Learning-Augmented Algorithms for NP-hard Permutation Problems
von: Bampis, Evripidis, et al.
Veröffentlicht: (2025)

Improved FPT Approximation for Non-metric TSP
von: Bampis, Evripidis, et al.
Veröffentlicht: (2024)

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

Median and Small Parsimony Problems on RNA trees
von: Marchand, Bertrand, et al.
Veröffentlicht: (2024)

Parsimonious Learning-Augmented Online Metric Matching
von: Shin, Yongho, et al.
Veröffentlicht: (2026)

Learning-Augmented Online Scheduling with Parsimonious Preemption
von: Blue, Mugen, et al.
Veröffentlicht: (2026)

NP-hardness and a PTAS for the Euclidean Steiner Line Problem
von: Bartlmae, Simon, et al.
Veröffentlicht: (2024)

3/2-Approximation for the Forest Augmentation Problem
von: Çivril, Ali
Veröffentlicht: (2024)

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

DNA Probe Computing System for Solving NP-Complete Problems
von: Xu, Jin, et al.
Veröffentlicht: (2025)

A Better-Than-2 Approximation for the Directed Tree Augmentation Problem
von: Neuwohner, Meike, et al.
Veröffentlicht: (2025)

The APX-hardness of the Traveling Tournament Problem
von: Zhao, Jingyang, et al.
Veröffentlicht: (2023)

Algorithmic Reductions: Network Flow and NP-Completeness in Real-World Scheduling Problems
von: Sinhal, Anay, et al.
Veröffentlicht: (2026)

Learning-Augmented Online Covering Problems
von: Ameli, Afrouz Jabal, et al.
Veröffentlicht: (2025)

Learning-Augmented Streaming Algorithms for Approximating MAX-CUT
von: Dong, Yinhao, et al.
Veröffentlicht: (2024)

Constant Approximating Disjoint Paths on Acyclic Digraphs is W[1]-hard
von: Włodarczyk, Michał
Veröffentlicht: (2024)

Parallel Minimum Cost Flow in Near-Linear Work and Square Root Depth for Dense Instances
von: Brand, Jan van den, et al.
Veröffentlicht: (2025)

Competitive Query Minimization for Stable Matching with One-Sided Uncertainty
von: Bampis, Evripidis, et al.
Veröffentlicht: (2024)

Effective Traveling for Metric Instances of the Traveling Thief Problem
von: Eube, Jan, et al.
Veröffentlicht: (2026)

Generating Satisfiable Benchmark Instances for Stable Roommates Problems with Optimization
von: Yılmaz, Baturay, et al.
Veröffentlicht: (2025)

Computational-Statistical Tradeoffs from NP-hardness
von: Blanc, Guy, et al.
Veröffentlicht: (2025)

Approximation Algorithms for Steiner Connectivity Augmentation
von: Hathcock, Daniel, et al.
Veröffentlicht: (2023)

NP-Hardness and a PTAS for the Pinwheel Problem
von: Kleinberg, Robert, et al.
Veröffentlicht: (2026)

Min-CSPs on Complete Instances II: Polylogarithmic Approximation for Min-NAE-3-SAT
von: Anand, Aditya, et al.
Veröffentlicht: (2025)

Directed and Undirected Vertex Connectivity Problems are Equivalent for Dense Graphs
von: Fischer, Olivier, et al.
Veröffentlicht: (2025)

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

An Invitation to "Fine-grained Complexity of NP-Complete Problems"
von: Nederlof, Jesper
Veröffentlicht: (2026)

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

Learning-Augmented Online Algorithms for Nonclairvoyant Joint Replenishment Problem with Deadlines
von: Dinitz, Michael, et al.
Veröffentlicht: (2025)

Hardness and Approximation Algorithms for Balanced Districting Problems
von: Dharangutte, Prathamesh, et al.
Veröffentlicht: (2025)

Improved Approximations for Dial-a-Ride Problems
von: Zhao, Jingyang, et al.
Veröffentlicht: (2026)

On the Approximability of the Traveling Salesman Problem with Line Neighborhoods
von: Antoniadis, Antonios, et al.
Veröffentlicht: (2020)

Optimal 4-Approximation for the Correlated Pandora's Problem
von: Bansal, Nikhil, et al.
Veröffentlicht: (2025)

New Approximation Guarantees for The Inventory Staggering Problem
von: Alon, Noga, et al.
Veröffentlicht: (2025)

Approximation Schemes for Planar Graph Connectivity Problems
von: Neuwohner, Meike, et al.
Veröffentlicht: (2025)

A Branch-and-Bound Approach for Maximum Low-Diameter Dense Subgraph Problems
von: Zhou, Yi, et al.
Veröffentlicht: (2025)

An Improved Approximation Algorithm for the Capacitated Arc Routing Problem
von: Zhao, Jingyang, et al.
Veröffentlicht: (2025)

Improved Approximations for the Unsplittable Capacitated Vehicle Routing Problem
von: Zhao, Jingyang, et al.
Veröffentlicht: (2026)

Exponential-Time Approximation (Schemes) for Vertex-Ordering Problems
von: Bentert, Matthias, et al.
Veröffentlicht: (2025)

Complexity and Approximation Algorithms for Fixed Charge Transportation Problems
von: Chen, Yong, et al.
Veröffentlicht: (2025)