46 citations · 60 across the 27 of their papers we have counts for
8 papers · 1 filter
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…
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…
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…
How to assign volunteers to tasks compatibly ? A graph theoretic and parameterized approach
Sushmita Gupta, Pallavi Jain, Saket Saurabh
In this paper we study a resource allocation problem that encodes correlation between items in terms of \conflict and maximizes the minimum utility of the agents under a conflict f…
Gerrymandering on graphs: Computational complexity and parameterized algorithms
Sushmita Gupta, Pallavi Jain, Fahad Panolan +2
Partitioning a region into districts to favor a particular candidate or a party is commonly known as gerrymandering. In this paper, we investigate the gerrymandering problem in gra…
On the Parameterized Approximability of Contraction to Classes of Chordal Graphs
Spoorthy Gunda, Pallavi Jain, Daniel Lokshtanov +2
A graph operation that {\em contracts edges} is one of the fundamental operations in the theory of graph minors. Parameterized Complexity of editing to a family of graphs by contra…
Polynomial Time Efficient Construction Heuristics for Vertex Separation Minimization Problem
Pallavi Jain, Gur Saran, Kamal Srivastava
Vertex Separation Minimization Problem (VSMP) consists of finding a layout of a graph G = (V,E) which minimizes the maximum vertex cut or separation of a layout. It is an NP-comple…