Buchumschlag

Sensitivity, Proximity and FPT Algorithms for Exact Matroid Problems

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Eisenbrand, Friedrich, Rohwedder, Lars, Węgrzycki, Karol
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

Space-Efficient Algorithm for Integer Programming with Few Constraints
von: Rohwedder, Lars, et al.
Veröffentlicht: (2024)

Fine-Grained Equivalence for Problems Related to Integer Linear Programming
von: Rohwedder, Lars, et al.
Veröffentlicht: (2024)

ETH-Tight FPT Algorithm for Makespan Minimization on Uniform Machines
von: Rohwedder, Lars
Veröffentlicht: (2025)

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

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

Improving Lagarias-Odlyzko Algorithm For Average-Case Subset Sum: Modular Arithmetic Approach
von: Joux, Antoine, et al.
Veröffentlicht: (2024)

The Submodular Santa Claus Problem
von: Bamas, Etienne, et al.
Veröffentlicht: (2024)

Cost Preserving Dependent Rounding for Allocation Problems
von: Rohwedder, Lars, et al.
Veröffentlicht: (2025)

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

Faster algorithms for k-Orthogonal Vectors in low dimension
von: Dürr, Anita, et al.
Veröffentlicht: (2025)

On Tight FPT Time Approximation Algorithms for k-Clustering Problems
von: Dai, Han, et al.
Veröffentlicht: (2025)

Beating Meet-in-the-Middle for Subset Balancing Problems
von: Randolph, Tim, et al.
Veröffentlicht: (2025)

Smoothed Analysis of the k-Swap Neighborhood for Makespan Scheduling
von: Rohwedder, Lars, et al.
Veröffentlicht: (2024)

A k-swap Local Search for Makespan Scheduling
von: Rohwedder, Lars, et al.
Veröffentlicht: (2024)

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

Randomized Rounding over Dynamic Programs
von: Bamas, Etienne, et al.
Veröffentlicht: (2025)

Parameterized Algorithms on Integer Sets with Small Doubling: Integer Programming, Subset Sum and k-SUM
von: Randolph, Tim, et al.
Veröffentlicht: (2024)

3.415-Approximation for Coflow Scheduling via Iterated Rounding
von: Rohwedder, Lars, et al.
Veröffentlicht: (2025)

On Subexponential Parameterized Algorithms for Steiner Tree on Intersection Graphs of Geometric Objects
von: Bhore, Sujoy, et al.
Veröffentlicht: (2025)

Non-Adaptive Evaluation of $k$-of-$n$ Functions: Tight Gap and a Unit-Cost PTAS
von: Nielsen, Mads Anker, et al.
Veröffentlicht: (2025)

An FPT Constant-Factor Approximation Algorithm for Correlation Clustering
von: Zhou, Jianqi, et al.
Veröffentlicht: (2025)

A Single Exponential-Time FPT Algorithm for Cactus Contraction
von: Krithika, R., et al.
Veröffentlicht: (2025)

Matroid Algorithms Under Size-Sensitive Independence Oracles
von: Banihashem, Kiarash, et al.
Veröffentlicht: (2026)

The $k$-Fold Matroid Secretary Problem
von: Gujjar, Rishi, et al.
Veröffentlicht: (2025)

An Exact Algorithm for the Unanimous Vote Problem
von: Keles, Feyza Duman, et al.
Veröffentlicht: (2025)

FPT Algorithms using Minimal Parameters for a Generalized Version of Maximin Shares
von: Jansen, Klaus, et al.
Veröffentlicht: (2024)

Improved Algorithms for Fair Matroid Submodular Maximization
von: Mahabadi, Sepideh, et al.
Veröffentlicht: (2026)

Approximation and FPT Algorithms for Finding DM-Irreducible Spanning Subgraphs
von: Norose, Ryoma, et al.
Veröffentlicht: (2024)

An ETH-Tight FPT Algorithm for Rejection-Proof Set Packing with Applications to Kidney Exchange
von: Jansen, Bart M. P., et al.
Veröffentlicht: (2025)

Hitting Meets Packing: How Hard Can it Be?
von: Focke, Jacob, et al.
Veröffentlicht: (2024)

Nearly-Tight Bounds for Zonotope Containment and Beyond
von: Eisenbrand, Friedrich, et al.
Veröffentlicht: (2026)

FPT Approximation for Capacitated Sum of Radii
von: Jaiswal, Ragesh, et al.
Veröffentlicht: (2024)

FPT Approximations for Connected Maximum Coverage
von: Inamdar, Tanmay, et al.
Veröffentlicht: (2026)

A Gap-ETH-Tight Approximation Scheme for Euclidean TSP
von: Kisfaludi-Bak, Sándor, et al.
Veröffentlicht: (2020)

Dynamic data structures for twin-ordered matrices
von: Bosek, Bartłomiej, et al.
Veröffentlicht: (2026)

FPT Constant Approximation Algorithms for Colorful Sum of Radii
von: Liu, Shuilian, et al.
Veröffentlicht: (2025)

Lower Bounds for Matroid Optimization Problems with a Linear Constraint
von: Doron-Arad, Ilan, et al.
Veröffentlicht: (2023)

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

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

Optimal FPT-Approximability for Modular Linear Equations
von: Dabrowski, Konrad K., et al.
Veröffentlicht: (2026)