4 papers · 1 filter
Connected Dominating Set on Semi-Ladder-Free Graphs
Sobyasachi Chatterjee, Sushmita Gupta, Saket Saurabh +2
We study \textsc{Connected Dominating Set} on graphs whose closed-neighborhood set systems are -semi-ladder-free. This structural condition strictly generalizes the biclique-fre…
A Simple Algorithm for Combinatorial n-Fold ILPs Using the Steinitz Lemma
Sushmita Gupta, Pallavi Jain, Sanjay Seetharaman +1
We present an algorithm for a class of -fold ILPs whose existing algorithms in literature are often either (1) based on the \textit{augmentation framework} where one starts with…
When far is better: The Chamberlin-Courant approach to obnoxious committee selection
Sushmita Gupta, Tanmay Inamdar, Pallavi Jain +3
Classical work on metric space based committee selection problem interprets distance as ``near is better''. In this work, motivated by real-life situations, we interpret distance a…
Budget-feasible Egalitarian Allocation of Conflicting Jobs
Sushmita Gupta, Pallavi Jain, A. Mohanapriya +1
Allocating conflicting jobs among individuals while respecting a budget constraint for each individual is an optimization problem that arises in various real-world scenarios. In th…