Buchumschlag

Efficient parameterized approximation

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Kratsch, Stefan, Kunz, Pascal
Format:	Preprint
Veröffentlicht:	2025
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

A faster polynomial-space algorithm for Hamiltonian cycle parameterized by treedepth
von: Kratsch, Stefan
Veröffentlicht: (2026)

A tight Monte-Carlo algorithm for Steiner Tree parameterized by clique-width
von: Bojikian, Narek, et al.
Veröffentlicht: (2023)

Boundaried Kernelization via Representative Sets
von: Antipov, Leonid, et al.
Veröffentlicht: (2025)

Boundaried Kernelization
von: Antipov, Leonid, et al.
Veröffentlicht: (2025)

Flow-augmentation III: Complexity dichotomy for Boolean CSPs parameterized by the number of unsatisfied constraints
von: Kim, Eun Jung, et al.
Veröffentlicht: (2022)

On polynomial kernelization for Stable Cutset
von: Kratsch, Stefan, et al.
Veröffentlicht: (2024)

Tight Bounds for some W[1]-hard Problems Parameterized by Multi-clique-width
von: Bergougnoux, Benjamin, et al.
Veröffentlicht: (2026)

Tight Bounds for Feedback Vertex Set Parameterized by Clique-width
von: Bojikian, Narek, et al.
Veröffentlicht: (2025)

Tight Algorithm for Connected Odd Cycle Transversal Parameterized by Clique-width
von: Bojikian, Narek, et al.
Veröffentlicht: (2024)

Faster parameterized algorithm for 3-Hitting Set
von: Tsur, Dekel
Veröffentlicht: (2025)

Tight Bounds for some Classical Problems Parameterized by Cutwidth
von: Bojikian, Narek, et al.
Veröffentlicht: (2025)

Minimum sum vertex cover: kernelization and parameterized algorithms
von: Cao, Yixin, et al.
Veröffentlicht: (2024)

Approximation and parameterized algorithms for covering disjointness-compliable set families
von: Nutov, Zeev, et al.
Veröffentlicht: (2025)

On Computing Optimal Tree Ensembles
von: Komusiewicz, Christian, et al.
Veröffentlicht: (2023)

A faster algorithm for Vertex Cover parameterized by solution size
von: Harris, David G., et al.
Veröffentlicht: (2022)

Witty: An Efficient Solver for Computing Minimum-Size Decision Trees
von: Staus, Luca Pascal, et al.
Veröffentlicht: (2024)

Fixed-parameter tractability of Directed Multicut with three terminal pairs parameterized by the size of the cutset: twin-width meets flow-augmentation
von: Hatzel, Meike, et al.
Veröffentlicht: (2022)

Dynamic parameterized problems on unit disk graphs
von: An, Shinwoo, et al.
Veröffentlicht: (2024)

On girth and the parameterized complexity of token sliding and token jumping
von: Bartier, Valentin, et al.
Veröffentlicht: (2020)

New approximate distance oracles and their applications
von: Kadria, Avi, et al.
Veröffentlicht: (2025)

Bicriteria approximation for $k$-edge-connectivity
von: Nutov, Zeev, et al.
Veröffentlicht: (2025)

Improved bicriteria approximation for $k$-edge-connectivity
von: Nutov, Zeev
Veröffentlicht: (2025)

Improved girth approximation in weighted undirected graphs
von: Kadria, Avi, et al.
Veröffentlicht: (2025)

Beyond 2-approximation for k-Center in Graphs
von: Jin, Ce, et al.
Veröffentlicht: (2025)

FPT approximations for Capacitated Sum of Radii and Diameters
von: Filtser, Arnold, et al.
Veröffentlicht: (2024)

On the cut-query complexity of approximating max-cut
von: Plevrakis, Orestis, et al.
Veröffentlicht: (2022)

Efficient $\varepsilon$-approximate minimum-entropy couplings
von: Compton, Spencer
Veröffentlicht: (2025)

A simple $(2+ε)$-approximation for knapsack interdiction
von: Weninger, Noah
Veröffentlicht: (2026)

Improved approximation ratio for covering pliable set families
von: Nutov, Zeev
Veröffentlicht: (2024)

A framework for boosting matching approximation: parallel, distributed, and dynamic
von: Mitrović, Slobodan, et al.
Veröffentlicht: (2025)

Conditional lower bounds for sparse parameterized 2-CSP: A streamlined proof
von: S., Karthik C., et al.
Veröffentlicht: (2023)

Testable algorithms for approximately counting edges and triangles in sublinear time and space
von: Eden, Talya, et al.
Veröffentlicht: (2025)

A $(2+\varepsilon)$-approximation algorithm for the general scheduling problem in quasipolynomial time
von: Armbruster, Alexander, et al.
Veröffentlicht: (2025)

Near-optimal streaming approximation for Max-DICUT in sublinear space using two passes
von: Velusamy, Santhoshini
Veröffentlicht: (2025)

A simpler and parallelizable $O(\sqrt{\log n})$-approximation algorithm for Sparsest Cut
von: Kolmogorov, Vladimir
Veröffentlicht: (2023)

Hypergraph dualization with FPT-delay parameterized by the degeneracy and dimension
von: Bartier, Valentin, et al.
Veröffentlicht: (2023)

A tight example for approximation ratio 5 for covering small cuts by the primal-dual method
von: Nutov, Zeev
Veröffentlicht: (2025)

An $2\sqrt{k}$-approximation algorithm for minimum power $k$ edge disjoint $st$ -paths
von: Nutov, Zeev
Veröffentlicht: (2022)

Scalable Distributed String Sorting
von: Kurpicz, Florian, et al.
Veröffentlicht: (2024)

A simple deterministic near-linear time approximation scheme for transshipment with arbitrary positive edge costs
von: Fox, Emily
Veröffentlicht: (2023)