Cover Image

Parameterized Approximation for Capacitated $d$-Hitting Set with Hard Capacities

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Lokshtanov, Daniel, Sahu, Abhishek, Saurabh, Saket, Surianarayanan, Vaishali, Xue, Jie
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Subexponential Parameterized Algorithms for Hitting Subgraphs
by: Lokshtanov, Daniel, et al.
Published: (2024)

Efficient Approximation of Fractional Hypertree Width
by: Korchemna, Viktoriia, et al.
Published: (2024)

A Quasi-Polynomial Time Algorithm for 3-Coloring Circle Graphs
by: S, Ajaykrishnan E, et al.
Published: (2025)

Satisfiability to Coverage in Presence of Fairness, Matroid, and Global Constraints
by: Inamdar, Tanmay, et al.
Published: (2024)

Bipartizing (Pseudo-)Disk Graphs: Approximation with a Ratio Better than 3
by: Lokshtanov, Daniel, et al.
Published: (2024)

Parameterized Saga of First-Fit and Last-Fit Coloring
by: Agrawal, Akanksha, et al.
Published: (2024)

Clustering with Set Outliers and Applications in Relational Clustering
by: Surianarayanan, Vaishali, et al.
Published: (2025)

Faster Exact and Parameterized Algorithm for Feedback Vertex Set in Bipartite Tournaments
by: Kumar, Mithilesh, et al.
Published: (2024)

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

Parameterized Approximation of Rectangle Stabbing
by: Chu, Huairui, et al.
Published: (2026)

FPT Constant-Approximations for Capacitated Clustering to Minimize the Sum of Cluster Radii
by: Bandyapadhyay, Sayan, et al.
Published: (2023)

Quick-Sort Style Approximation Algorithms for Generalizations of Feedback Vertex Set in Tournaments
by: Gupta, Sushmita, et al.
Published: (2024)

The Parameterized Complexity Landscape of Two-Sets Cut-Uncut
by: Bentert, Matthias, et al.
Published: (2024)

Fixed-Parameter Tractability of Hedge Cut
by: Fomin, Fedor V., et al.
Published: (2024)

Enumeration of Minimal Hitting Sets Parameterized by Treewidth
by: Kenig, Batya, et al.
Published: (2024)

Path Contraction Faster than $2^n$
by: Agrawal, Akanksha, et al.
Published: (2025)

A Quadratic Vertex Kernel and a Subexponential Algorithm for Subset-FAST
by: Jana, Satyabrata, et al.
Published: (2025)

Faster Parameterized Vertex Multicut
by: Chu, Huairui, et al.
Published: (2026)

A Refined Kernel for $d$-Hitting Set
by: Liu, Yuxi, et al.
Published: (2025)

Exponential-Time Approximation (Schemes) for Vertex-Ordering Problems
by: Bentert, Matthias, et al.
Published: (2025)

Linear Layouts Revisited: Stacks, Queues, and Exact Algorithms
by: Depian, Thomas, et al.
Published: (2025)

Hitting Meets Packing: How Hard Can it Be?
by: Focke, Jacob, et al.
Published: (2024)

Improved Approximation Algorithms for Capacitated Vehicle Routing with Fixed Capacity
by: Zhao, Jingyang, et al.
Published: (2022)

Robust Contraction Decomposition for Minor-Free Graphs and its Applications
by: Bandyapadhyay, Sayan, et al.
Published: (2024)

Dominating Set with Quotas: Balancing Coverage and Constraints
by: Chatterjee, Sobyasachi, et al.
Published: (2026)

Maximum Partial List H-Coloring on P_5-free graphs in polynomial time
by: Lokshtanov, Daniel, et al.
Published: (2024)

Counting hypertriangles through hypergraph orientations
by: Paul-Pena, Daniel, et al.
Published: (2026)

A $2\ell k$ Kernel for $\ell$-Component Order Connectivity
by: Kumar, Mithilesh, et al.
Published: (2016)

Parameterized Geometric Graph Modification with Disk Scaling
by: Fomin, Fedor V., et al.
Published: (2024)

When far is better: The Chamberlin-Courant approach to obnoxious committee selection
by: Gupta, Sushmita, et al.
Published: (2024)

Capacitated Fair-Range Clustering: Hardness and Approximation Algorithms
by: Gadekar, Ameet, et al.
Published: (2025)

Tight Parameterized (In)tractability of Layered Crossing Minimization: Subexponential Algorithms and Kernelization
by: Fomin, Fedor V., et al.
Published: (2025)

Sampling Unlabeled Chordal Graphs in Expected Polynomial Time
by: Hébert-Johnson, Úrsula, et al.
Published: (2025)

On Fair Epsilon Net and Geometric Hitting Set
by: Dehghankar, Mohsen, et al.
Published: (2025)

Faster parameterized algorithm for 3-Hitting Set
by: Tsur, Dekel
Published: (2025)

Finding large sparse induced subgraphs in graphs of small (but not very small) tree-independence number
by: Lokshtanov, Daniel, et al.
Published: (2026)

Efficient and Reliable Hitting-Set Computations for the Implicit Hitting Set Approach
by: Ihalainen, Hannes, et al.
Published: (2025)

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

Parameterized Capacitated Vertex Cover Revisited
by: Lampis, Michael, et al.
Published: (2026)

Hardness and Approximation Algorithms for Balanced Districting Problems
by: Dharangutte, Prathamesh, et al.
Published: (2025)