Pallavi Jain
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Pallavi Jain has a total of 30 co-authors. Here are the top co-authors by number of shared publications:
- Sushmita Gupta
The Institute of Mathematical Sciences, HBNI
10 shared publications - Saket Saurabh
Institute of Mathematical Sciences
8 shared publications - Fahad Panolan
School of Computer Science, University of Leeds, Leeds, UK
3 shared publications - Lawqueen Kanesh
Indian Institute of Technology Jodhpur
3 shared publications - Nimrod Talmon
Ben-Gurion University of the Negev
3 shared publications - Sanjay Seetharaman
The Institute of Mathematical Sciences HBNI Chennai
3 shared publications
Latest Publications
- Open Access
Robust Value Maximization in Challenge the Champ Tournaments with Probabilistic Outcomes
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 AccessRobust Value Maximization in Challenge the Champ Tournaments with Probabilistic Outcomes
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
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 AccessWhen agents choose bundles autonomously: guarantees beyond discrepancy
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
- 7 October 2025
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Algorithms
- Vol. 22 (1) , 1-30
Parameterized Approximation Schemes for Biclique-Free Max k -Weight SAT and Max Coverage
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.- 7 October 2025
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Algorithms
- Vol. 22 (1) , 1-30
Open AccessParameterized Approximation Schemes for Biclique-Free Max k -Weight SAT and Max Coverage
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
- 1 September 2025
- Published by International Joint Conferences on Artificial Intelligence
- Vol. 5, 3916-3924
Efficient Algorithms for Electing Successive Committees
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.
- 1 September 2025
- Published by International Joint Conferences on Artificial Intelligence
- Vol. 5, 3916-3924
Open AccessEfficient Algorithms for Electing Successive Committees
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
- 28 August 2025
- Published by Elsevier in Journal of Computer and System Sciences
- Vol. 156
Participatory budgeting with project groups
- 28 August 2025
- Published by Elsevier in Journal of Computer and System Sciences
- Vol. 156
Open AccessParticipatory budgeting with project groups
- Open Access
Efficient Algorithms for Electing Successive Committees
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.
Open AccessEfficient Algorithms for Electing Successive Committees
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.
- 18 May 2025
- Published by Springer Nature
- p. 233-248
Parameterized Complexity of Disconnected Matchings
- Open Access
Fairness and Efficiency in Two-Sided Matching Markets
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 AccessFairness and Efficiency in Two-Sided Matching Markets
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
- 25 January 2025
- Published by Springer Nature in Theory of Computing Systems
- Vol. 69 (1) , 1-29
Exact and Approximate Digraph Bandwidth
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}$$ and an ordering $$\varvec{\sigma }$$ of its vertices, the digraph bandwidth of $$\varvec{\sigma }$$ with respect to $$\varvec{D}$$ is equal to the maximum value of $$\varvec{\sigma (v)}-\varvec{\sigma (u)}$$ over all arcs $$\varvec{(u,v)}$$ of $$\varvec{D}$$ going forward along $$\varvec{\sigma }$$ (that is, when $$\varvec{\sigma (u)} < \varvec{\sigma (v)}$$ ). The Digraph Bandwidth problem takes as input a digraph $$\varvec{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!)}$$ 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)}}$$ . In particular, we obtain the following results. Here, $$\varvec{n}$$ and $$\varvec{m}$$ denote the number of vertices and arcs of the input digraph $$\varvec{D}$$ , respectively. Digraph Bandwidth can be solved in $$\varvec{\mathcal {O}}^\star (\varvec{3}^{\varvec{n}} \cdot \varvec{2}^{\varvec{m}})$$ time. This result implies a $$\varvec{2}^{\varvec{\mathcal {O}}(\varvec{n})}$$ time algorithm on sparse graphs, such as graphs of bounded average degree (planar graphs). Let $$\varvec{G}$$ be the underlying undirected graph of the input digraph. If the treewidth of $$\varvec{G}$$ is at most $$\varvec{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}})$$ . This result implies a $$\varvec{2}^{\varvec{n}+\varvec{\mathcal {O}}(\sqrt{\varvec{n}}\, \varvec{\log }\, \varvec{n})}$$ algorithm, for directed planar graphs and, in general, for the class of digraphs whose underlying undirected graph excludes some fixed graph $$\varvec{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}})\}$$ time, where $$\varvec{b}$$ denotes the optimal digraph bandwidth of $$\varvec{D}$$ . This allow us to deduce a $$\varvec{2}^{\varvec{\mathcal {O}}(\varvec{n})}$$ algorithm in many cases, for example when $$\varvec{b} \le \frac{\varvec{n}}{\varvec{\log }^{\varvec{2}}\,\varvec{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}$$ , we can find an ordering whose digraph bandwidth is at most $$(\varvec{1}+\varvec{\epsilon })$$ times the optimal digraph bandwidth, in time $$\varvec{\mathcal {O}}^{{\star }}(\varvec{4}^{\varvec{n}} \cdot (\lceil \varvec{4}/{\varvec{\epsilon }} \rceil )^n)$$- 25 January 2025
- Published by Springer Nature in Theory of Computing Systems
- Vol. 69 (1) , 1-29
Open AccessExact and Approximate Digraph Bandwidth
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}$$ and an ordering $$\varvec{\sigma }$$ of its vertices, the digraph bandwidth of $$\varvec{\sigma }$$ with respect to $$\varvec{D}$$ is equal to the maximum value of $$\varvec{\sigma (v)}-\varvec{\sigma (u)}$$ over all arcs $$\varvec{(u,v)}$$ of $$\varvec{D}$$ going forward along $$\varvec{\sigma }$$ (that is, when $$\varvec{\sigma (u)} < \varvec{\sigma (v)}$$ ). The Digraph Bandwidth problem takes as input a digraph $$\varvec{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!)}$$ 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)}}$$ . In particular, we obtain the following results. Here, $$\varvec{n}$$ and $$\varvec{m}$$ denote the number of vertices and arcs of the input digraph $$\varvec{D}$$ , respectively. Digraph Bandwidth can be solved in $$\varvec{\mathcal {O}}^\star (\varvec{3}^{\varvec{n}} \cdot \varvec{2}^{\varvec{m}})$$ time. This result implies a $$\varvec{2}^{\varvec{\mathcal {O}}(\varvec{n})}$$ time algorithm on sparse graphs, such as graphs of bounded average degree (planar graphs). Let $$\varvec{G}$$ be the underlying undirected graph of the input digraph. If the treewidth of $$\varvec{G}$$ is at most $$\varvec{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}})$$ . This result implies a $$\varvec{2}^{\varvec{n}+\varvec{\mathcal {O}}(\sqrt{\varvec{n}}\, \varvec{\log }\, \varvec{n})}$$ algorithm, for directed planar graphs and, in general, for the class of digraphs whose underlying undirected graph excludes some fixed graph $$\varvec{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}})\}$$ time, where $$\varvec{b}$$ denotes the optimal digraph bandwidth of $$\varvec{D}$$ . This allow us to deduce a $$\varvec{2}^{\varvec{\mathcal {O}}(\varvec{n})}$$ algorithm in many cases, for example when $$\varvec{b} \le \frac{\varvec{n}}{\varvec{\log }^{\varvec{2}}\,\varvec{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}$$ , we can find an ordering whose digraph bandwidth is at most $$(\varvec{1}+\varvec{\epsilon })$$ times the optimal digraph bandwidth, in time $$\varvec{\mathcal {O}}^{{\star }}(\varvec{4}^{\varvec{n}} \cdot (\lceil \varvec{4}/{\varvec{\epsilon }} \rceil )^n)$$ - Open Access
- 11 January 2025
- Published by Springer Nature in Autonomous Agents and Multi-Agent Systems
- Vol. 39 (1) , 1-29
Budget-feasible egalitarian allocation of conflicting jobs
- 11 January 2025
- Published by Springer Nature in Autonomous Agents and Multi-Agent Systems
- Vol. 39 (1) , 1-29
Open AccessBudget-feasible egalitarian allocation of conflicting jobs