5 papers
Parameterized Approximation for Capacitated -Hitting Set with Hard Capacities
Daniel Lokshtanov, Abhishek Sahu, Saket Saurabh +2
The \textsc{Capacitated -Hitting Set} problem involves a universe with a capacity function and a collection of subsets…
Satisfiability to Coverage in Presence of Fairness, Matroid, and Global Constraints
Tanmay Inamdar, Pallavi Jain, Daniel Lokshtanov +3
In MaxSAT with Cardinality Constraint problem (CC-MaxSAT), we are given a CNF-formula , and , and the goal is to find an assignment with at most variables set t…
Conflict and Fairness in Resource Allocation
Susobhan Bandopadhyay, Aritra Banik, Sushmita Gupta +4
In the standard model of fair allocation of resources to agents, every agent has some utility for every resource, and the goal is to assign resources to agents so that the agents'…
A Polynomial Kernel for Proper Helly Circular-arc Vertex Deletion
Akanksha Agrawal, Satyabrata Jana, Abhishek Sahu
A proper Helly circular-arc graph is an intersection graph of a set of arcs on a circle such that none of the arcs properly contains any other arc and every set of pairwise interse…
An Improved Exact Algorithm for Knot-Free Vertex Deletion
Ajaykrishnan E S, Soumen Maity, Abhishek Sahu +1
A knot in a directed graph is a strongly connected component of size at least two such that there is no arc with and . Given a directed g…