Cover Image

An ETH-Tight FPT Algorithm for Rejection-Proof Set Packing with Applications to Kidney Exchange

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Jansen, Bart M. P., Lamme, Jeroen S. K., Verhaegh, Ruben F. A.
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

ETH-Tight FPT Algorithm for Makespan Minimization on Uniform Machines
by: Rohwedder, Lars
Published: (2025)

Search-Space Reduction Via Essential Vertices Revisited: Vertex Multicut and Cograph Deletion
by: Jansen, Bart M. P., et al.
Published: (2024)

ETH-Tight Algorithm for Cycle Packing on Unit Disk Graphs
by: An, Shinwoo, et al.
Published: (2024)

Search-space Reduction for Boolean MinCSPs via Essential Constraints
by: Jansen, Bart M. P., et al.
Published: (2026)

Tight (S)ETH-based Lower Bounds for Pseudopolynomial Algorithms for Bin Packing and Multi-Machine Scheduling
by: Bringmann, Karl, et al.
Published: (2026)

Preprocessing to Reduce the Search Space for Odd Cycle Transversal
by: Jansen, Bart M. P., et al.
Published: (2024)

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

Single-Source Shortest Paths and Almost Exact Diameter in Pseudodisk Graphs
by: de Berg, Mark, et al.
Published: (2026)

Hardness and Tight Approximations of Demand Strip Packing
by: Jansen, Klaus, et al.
Published: (2024)

FPT Algorithms using Minimal Parameters for a Generalized Version of Maximin Shares
by: Jansen, Klaus, et al.
Published: (2024)

A Faster Deterministic Algorithm for Kidney Exchange via Representative Set
by: Tian, Kangyi, et al.
Published: (2026)

Preprocessing to Reduce the Search Space: Antler Structures for Feedback Vertex Set
by: Donkers, Huib, et al.
Published: (2021)

A Linear Time Gap-ETH-Tight Approximation Scheme for Euclidean TSP
by: Mömke, Tobias, et al.
Published: (2024)

A Tight ($3/2 + \varepsilon$)-Approximation Algorithm for Demand Strip Packing
by: Eberle, Franziska, et al.
Published: (2024)

Pushing the frontiers of subexponential FPT time for Feedback Vertex Set
by: Berthe, Gaétan, et al.
Published: (2025)

Sensitivity, Proximity and FPT Algorithms for Exact Matroid Problems
by: Eisenbrand, Friedrich, et al.
Published: (2024)

An FPT Constant-Factor Approximation Algorithm for Correlation Clustering
by: Zhou, Jianqi, et al.
Published: (2025)

Scalable Algorithms for 2-Packing Sets on Arbitrary Graphs
by: Borowitz, Jannick, et al.
Published: (2023)

A Tight Double-Exponentially Lower Bound for High-Multiplicity Bin Packing
by: Jansen, Klaus, et al.
Published: (2025)

A Single Exponential-Time FPT Algorithm for Cactus Contraction
by: Krithika, R., et al.
Published: (2025)

Optimal FPT-Approximability for Modular Linear Equations
by: Dabrowski, Konrad K., et al.
Published: (2026)

Approximation and FPT Algorithms for Finding DM-Irreducible Spanning Subgraphs
by: Norose, Ryoma, et al.
Published: (2024)

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

The Support of Bin Packing is Exponential
by: Jansen, Klaus, et al.
Published: (2025)

FPT Approximations for Connected Maximum Coverage
by: Inamdar, Tanmay, et al.
Published: (2026)

FPT Approximation for Capacitated Sum of Radii
by: Jaiswal, Ragesh, et al.
Published: (2024)

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

FPT Constant Approximation Algorithms for Colorful Sum of Radii
by: Liu, Shuilian, et al.
Published: (2025)

FPT approximations for Capacitated Sum of Radii and Diameters
by: Filtser, Arnold, et al.
Published: (2024)

An FPT algorithm for Matching Cut and d-cut
by: Aravind, N R, et al.
Published: (2021)

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

Near-optimal Algorithms for Stochastic Online Bin Packing
by: Ayyadevara, Nikhil, et al.
Published: (2022)

Deterministic Single Exponential Time Algorithms for Co-Path Packing and Co-Path Set Parameterized by Treewidth
by: Liu, Yuxi, et al.
Published: (2026)

Feedback Vertex Set for pseudo-disk graphs in subexponential FPT time
by: Berthe, Gaétan, et al.
Published: (2024)

FPT Approximations for Fair $k$-Min-Sum-Radii
by: Carta, Lena, et al.
Published: (2024)

FPT algorithms over linear delta-matroids with applications
by: Eiben, Eduard, et al.
Published: (2025)

(Almost-)Optimal FPT Algorithm and Kernel for $T$-Cycle on Planar Graphs
by: Gahlawat, Harmender, et al.
Published: (2025)

Conditionally Tight Algorithms for Maximum k-Coverage and Partial k-Dominating Set via Arity-Reducing Hypercuts
by: Fischer, Nick, et al.
Published: (2026)

Split-or-decompose: Improved FPT branching algorithms for maximum agreement forests
by: Mestel, David, et al.
Published: (2024)

New Algorithm for Combinatorial $n$-folds and Applications
by: Jansen, Klaus, et al.
Published: (2024)