PJPallavi Jain

Pallavi Jain

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article


Pallavi Jain has a total of 30 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Robust Value Maximization in Challenge the Champ Tournaments with Probabilistic Outcomes

    by Umang Bhaskar, Juhi Chaudhary, Sushmita Gupta, Pallavi Jain, Sanjay Seetharaman

    Challenge the Champ is a simple tournament format, where an ordering of the players -- called a seeding -- is decided. The first player in this order is the initial champ, and faces the next player. The outcome of each match decides the current champion, who faces the next player in the order. Each player also has a popularity, and the value of each match is the popularity of the winner. Value maximization in tournaments has been previously studied when each match has a deterministic outcome. However, match outcomes are often probabilistic, rather than deterministic. We study robust value maximization in Challenge the Champ tournaments, when the winner of a match may be probabilistic. That is, we seek to maximize the total value that is obtained, irrespective of the outcome of probabilistic matches. We show that even in simple binary settings, for non-adaptive algorithms, the optimal robust value -- which we term the \textsc{VnaR}, or the value not at risk -- is hard to approximate. However, if we allow adaptive algorithms that determine the order of challengers based on the outcomes of previous matches, or restrict the matches with probabilistic outcomes, we can obtain good approximations to the optimal \textsc{VnaR}.

  • Open Access

    When agents choose bundles autonomously: guarantees beyond discrepancy

    by Sushmita Gupta, Pallavi Jain, Sanjay Seetharaman, Meirav Zehavi

    We consider the fair division of indivisible items among $n$ agents with additive non-negative normalized valuations, with the goal of obtaining high value guarantees, that is, close to the proportional share for each agent. We prove that partitions where \emph{every} part yields high value for each agent are asymptotically limited by a discrepancy barrier of $Θ(\sqrt{n})$. Guided by this, our main objective is to overcome this barrier and achieve stronger individual guarantees for each agent in polynomial time. Towards this, we are able to exhibit an exponential improvement over the discrepancy barrier. In particular, we can create partitions on-the-go such that when agents arrive sequentially (representing a previously-agreed priority order) and pick a part autonomously and rationally (i.e., one of highest value), then each is guaranteed a part of value at least $\mathsf{PROP} - \mathcal{O}{(\log n)}$. Moreover, we show even better guarantees for three restricted valuation classes such as those defined by: a common ordering on items, a bound on the multiplicity of values, and a hypergraph with a bound on the \emph{influence} of any agent. Specifically, we study instances where: (1) the agents are ``close'' to unanimity in their relative valuation of the items -- a generalization of the ordered additive setting; (2) the valuation functions do not assign the same positive value to more than $t$ items; and (3) the valuation functions respect a hypergraph, a setting introduced by Christodoulou et al. [EC'23], where agents are vertices and items are hyperedges. While the sizes of the hyperedges and neighborhoods can be arbitrary, the influence of any agent $a$, defined as the number of its neighbors who value at least one item positively that $a$ also values positively, is bounded.

  • Open Access

    Parameterized Approximation Schemes for Biclique-Free Max k -Weight SAT and Max Coverage

    by Pallavi Jain, Lawqueen Kanesh, Fahad Panolan, Souvik Saha, Abhishek Sahu, Saket Saurabh, Anannya Upasana

    Max-SAT with cardinality constraint ( CC-Max-Sat ) is one of the classical NP-complete problems, that generalizes Maximum Coverage , Partial Vertex Cover , Max-2-SAT with bisection constraints, and has been extensively studied across all algorithmic paradigms. In this problem, we are given a CNF formula \(\Phi\) , and a positive integer \( k \) , and the goal is to find an assignment \(\beta\) with at most \( k \) variables set to true (also called a \( k \) -weight assignment) such that the number of clauses satisfied by \(\beta\) is maximized. The problem is known to admit an approximation algorithm with factor \(1-\frac{1}{e}\) , which is probably optimal. Furthermore, assuming Gap-Exponential Time Hypothesis (Gap-ETH), for any \(\epsilon > 0\) and any function \( h \) , no \(h(k)(n+m)^{o(k)}\) time algorithm can approximate Maximum Coverage (a monotone version of CC-Max-Sat ) with \( n \) elements and \( m \) sets to within a factor \((1-\frac{1}{e}+\epsilon)\) , even with a promise that there exist \( k \) sets that fully cover the whole universe. In fact, the problem is hard to approximate within 0.929, assuming Unique Games Conjecture, even when the input formula is 2-CNF. These intractable results lead us to explore families of formula, where we can circumvent these barriers. Toward this, we consider \(K_{d,d}\) -free formulas (that is, the clause-variable incidence bipartite graph of the formula excludes \(K_{d,d}\) as an induced subgraph). We show that for every \(\epsilon > 0\) , there exists an algorithm for CC-Max-Sat on \(K_{d,d}\) -free formulas with approximation ratio \((1-\epsilon)\) and running in time \(2^{{\mathcal{O}}((\frac{dk}{\epsilon})^{d})}(n+m)^{{\mathcal{O}}(1)}\) (these algorithms are called FPT-AS). For Maximum Coverage on \(K_{d,d}\) -free set families, we obtain FPT-AS with running time \((\frac{dk}{\epsilon})^{{\mathcal{O}}(dk)}n^{{\mathcal{O}}(1)}\) . Our second result considers “optimizing \( k \) ,” with fixed covering constraint for the Maximum Coverage problem. To explain our result, we first recast the Maximum Coverage problem as the Max Red Blue Dominating Set with Covering Constraint problem. Here, the input is a bipartite graph \(G=(A,B,E)\) , a positive integer \( t \) , and the objective is to find a minimum sized subset \(S\subseteq A\) , such that \(|N(S)|\) (the size of the set of neighbors of \( S \) ) is at least \( t \) . We design an additive approximation algorithm for Max Red Blue Dominating Set with Covering Constraint , on \(K_{d,d}\) -free bipartite graphs, running in FPT time. In particular, if \( k \) denotes the minimum size of \(S\subseteq A\) , such that \(|N(S)|\geq t\) , then our algorithm runs in time \((kd)^{{\mathcal{O}}(kd)}n^{{\mathcal{O}}{(1)}}\) and returns a set \(S^{\prime}\) such that \(|N(S^{\prime})|\geq t\) and \(|S^{\prime}|\leq k+1\) . This is in sharp contrast to the fact that, even a special case of our problem, namely, the Partial Vertex Cover problem (or Max \( k \) -VC ) is W[1]-hard, parameterized by \( k \) . Thus, we get the best possible parameterized approximation algorithm for the Maximum Coverage problem on \(K_{d,d}\) -free bipartite graphs.


  • Open Access

    Efficient Algorithms for Electing Successive Committees

    by Pallavi Jain, Andrzej Kaczmarczyk

    In a recently introduced model of successive committee elections, for a given set of ordinal or approval preferences one aims to find a sequence of a given length of “best” same-size committees such that each candidate is a member of a limited number of consecutive committees. However, the practical usability of this model remains limited, as the described task turns out to be NP-hard for most selection criteria already for seeking committees of size three. Non-trivial or somewhat efficient algorithms for these cases are lacking too. Motivated by a desire to unlock the full potential of the described temporal model of committee elections, we devise (parameterized) algorithms that effectively solve the mentioned hard cases in realistic scenarios of a moderate number of candidates or of a limited time horizon.

  • Open Access

    Participatory budgeting with project groups

    by Pallavi Jain, Krzysztof Sornat, Nimrod Talmon, Meirav Zehavi


  • Open Access

    Efficient Algorithms for Electing Successive Committees

    by Pallavi Jain, Andrzej Kaczmarczyk

    In a recently introduced model of successive committee elections (Bredereck et al., AAAI-20) for a given set of ordinal or approval preferences one aims to find a sequence of a given length of "best" same-size committees such that each candidate is a member of a limited number of consecutive committees. However, the practical usability of this model remains limited, as the described task turns out to be NP-hard for most selection criteria already for seeking committees of size three. Non-trivial or somewhat efficient algorithms for these cases are lacking too. Motivated by a desire to unlock the full potential of the described temporal model of committee elections, we devise (parameterized) algorithms that effectively solve the mentioned hard cases in realistic scenarios of a moderate number of candidates or of a limited time horizon.

  • Parameterized Complexity of Disconnected Matchings

    by Sushmita Gupta, Pallavi Jain, Lawqueen Kanesh, Sounak Modak, Saket Saurabh

  • Open Access

    Fairness and Efficiency in Two-Sided Matching Markets

    by Pallavi Jain, Palash Jha, Shubham Solanki

    We propose a new fairness notion, motivated by the practical challenge of allocating teaching assistants (TAs) to courses in a department. Each course requires a certain number of TAs and each TA has preferences over the courses they want to assist. Similarly, each course instructor has preferences over the TAs who applied for their course. We demand fairness and efficiency for both sides separately, giving rise to the following criteria: (i) every course gets the required number of TAs and the average utility of the assigned TAs meets a threshold; (ii) the allocation of courses to TAs is envy-free, where a TA envies another TA if the former prefers the latter's course and has a higher or equal grade in that course. Note that the definition of envy-freeness here differs from the one in the literature, and we call it merit-based envy-freeness. We show that the problem of finding a merit-based envy-free and efficient matching is NP-hard even for very restricted settings, such as two courses and uniform valuations; constant degree, constant capacity of TAs for every course, valuations in the range {0,1,2,3}, identical valuations from TAs, and even more. To find tractable results, we consider some restricted instances, such as, strict valuation of TAs for courses, the difference between the number of positively valued TAs for a course and the capacity, the number of positively valued TAs/courses, types of valuation functions, and obtained some polynomial-time solvable cases, showing the contrast with intractable results. We further studied the problem in the paradigm of parameterized algorithms and designed some exact and approximation algorithms.

  • Open Access

    Exact and Approximate Digraph Bandwidth

    by Pallavi Jain, Lawqueen Kanesh, Willian Lochet, Saket Saurabh, Roohani Sharma

    In this paper, we introduce a directed variant of the classical Bandwidthproblem and study it from the view-point of moderately exponential time algorithms, both exactly and approximately. Motivated by the definitions of the directed variants of the classical Cutwidth and Pathwidth problems, we define Digraph Bandwidth as follows. Given a digraph $$\varvec{D}$$ D and an ordering $$\varvec{\sigma }$$ σ of its vertices, the digraph bandwidth of $$\varvec{\sigma }$$ σ with respect to $$\varvec{D}$$ D is equal to the maximum value of $$\varvec{\sigma (v)}-\varvec{\sigma (u)}$$ σ ( v ) - σ ( u ) over all arcs $$\varvec{(u,v)}$$ ( u , v ) of $$\varvec{D}$$ D going forward along $$\varvec{\sigma }$$ σ (that is, when $$\varvec{\sigma (u)} < \varvec{\sigma (v)}$$ σ ( u ) < σ ( v ) ). The Digraph Bandwidth problem takes as input a digraph $$\varvec{D}$$ D and asks to output an ordering with the minimum digraph bandwidth. The undirected Bandwidtheasily reduces to Digraph Bandwidth and thus, it immediately implies that Digraph Bandwidth is -hard. While an $$\varvec{\mathcal {O}}^{\star }\varvec{(n!)}$$ O ⋆ ( n ! ) time algorithm for the problem is trivial, the goal of this paper is to design algorithms for Digraph Bandwidth which have running times of the form $$\varvec{2}^{\varvec{\mathcal {O}(n)}}$$ 2 O ( n ) . In particular, we obtain the following results. Here, $$\varvec{n}$$ n and $$\varvec{m}$$ m denote the number of vertices and arcs of the input digraph $$\varvec{D}$$ D , respectively. Digraph Bandwidth can be solved in $$\varvec{\mathcal {O}}^\star (\varvec{3}^{\varvec{n}} \cdot \varvec{2}^{\varvec{m}})$$ O ⋆ ( 3 n · 2 m ) time. This result implies a $$\varvec{2}^{\varvec{\mathcal {O}}(\varvec{n})}$$ 2 O ( n ) time algorithm on sparse graphs, such as graphs of bounded average degree (planar graphs). Let $$\varvec{G}$$ G be the underlying undirected graph of the input digraph. If the treewidth of $$\varvec{G}$$ G is at most $$\varvec{t}$$ t , then Digraph Bandwidth can be solved in time $$\varvec{\mathcal {O}}^\star (\varvec{2}^{\varvec{n} + (\varvec{t}+\varvec{2})\, \varvec{\log }\, \varvec{n}})$$ O ⋆ ( 2 n + ( t + 2 ) log n ) . This result implies a $$\varvec{2}^{\varvec{n}+\varvec{\mathcal {O}}(\sqrt{\varvec{n}}\, \varvec{\log }\, \varvec{n})}$$ 2 n + O ( n log n ) algorithm, for directed planar graphs and, in general, for the class of digraphs whose underlying undirected graph excludes some fixed graph $$\varvec{H}$$ H as a minor. Digraph Bandwidth can be solved in $$\varvec{\min } \{ \varvec{\mathcal {O}}^{\star }(\varvec{4}^{\varvec{n}} \cdot \varvec{b}^{\varvec{n}}), \varvec{\mathcal {O}}^{\star }(\varvec{4}^{\varvec{n}} \cdot \varvec{2}^{\varvec{b}\, \varvec{\log }\, \varvec{b}\, \varvec{\log }\, \varvec{n}})\}$$ min { O ⋆ ( 4 n · b n ) , O ⋆ ( 4 n · 2 b log b log n ) } time, where $$\varvec{b}$$ b denotes the optimal digraph bandwidth of $$\varvec{D}$$ D . This allow us to deduce a $$\varvec{2}^{\varvec{\mathcal {O}}(\varvec{n})}$$ 2 O ( n ) algorithm in many cases, for example when $$\varvec{b} \le \frac{\varvec{n}}{\varvec{\log }^{\varvec{2}}\,\varvec{n}}$$ b ≤ n log 2 n . Finally, we give a (Single) Exponential Time Approximation Scheme for Digraph Bandwidth. In particular, we show that for any fixed real $$\varvec{\epsilon } > \varvec{0}$$ ϵ > 0 , we can find an ordering whose digraph bandwidth is at most $$(\varvec{1}+\varvec{\epsilon })$$ ( 1 + ϵ ) times the optimal digraph bandwidth, in time $$\varvec{\mathcal {O}}^{{\star }}(\varvec{4}^{\varvec{n}} \cdot (\lceil \varvec{4}/{\varvec{\epsilon }} \rceil )^n)$$ O ⋆ ( 4 n · ( ⌈ 4 / ϵ ⌉ ) ...

  • Open Access

    Budget-feasible egalitarian allocation of conflicting jobs

    by Sushmita Gupta, Pallavi Jain, A. Mohanapriya, Vikash Tripathi