DROPS

Document

DOI: 10.4230/LIPIcs.ITCS.2021.8

Pipeline Interventions

Authors: Eshwar Ram Arunachaleswaran, Sampath Kannan, Aaron Roth, and Juba Ziani

Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)

Abstract

We introduce the pipeline intervention problem, defined by a layered directed acyclic graph and a set of stochastic matrices governing transitions between successive layers. The graph is a stylized model for how people from different populations are presented opportunities, eventually leading to some reward. In our model, individuals are born into an initial position (i.e. some node in the first layer of the graph) according to a fixed probability distribution, and then stochastically progress through the graph according to the transition matrices, until they reach a node in the final layer of the graph; each node in the final layer has a reward associated with it. The pipeline intervention problem asks how to best make costly changes to the transition matrices governing people’s stochastic transitions through the graph, subject to a budget constraint. We consider two objectives: social welfare maximization, and a fairness-motivated maximin objective that seeks to maximize the value to the population (starting node) with the least expected value. We consider two variants of the maximin objective that turn out to be distinct, depending on whether we demand a deterministic solution or allow randomization. For each objective, we give an efficient approximation algorithm (an additive FPTAS) for constant width networks. We also tightly characterize the "price of fairness" in our setting: the ratio between the highest achievable social welfare and the social welfare consistent with a maximin optimal solution. Finally we show that for polynomial width networks, even approximating the maximin objective to any constant factor is NP hard, even for networks with constant depth. This shows that the restriction on the width in our positive results is essential.

Cite as

Eshwar Ram Arunachaleswaran, Sampath Kannan, Aaron Roth, and Juba Ziani. Pipeline Interventions. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 8:1-8:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{arunachaleswaran_et_al:LIPIcs.ITCS.2021.8,
  author =	{Arunachaleswaran, Eshwar Ram and Kannan, Sampath and Roth, Aaron and Ziani, Juba},
  title =	{{Pipeline Interventions}},
  booktitle =	{12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
  pages =	{8:1--8:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-177-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{185},
  editor =	{Lee, James R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.8},
  URN =		{urn:nbn:de:0030-drops-135478},
  doi =		{10.4230/LIPIcs.ITCS.2021.8},
  annote =	{Keywords: Interventions for fairness, fairness in navigating life paths, social welfare, maximin welfare, budget-constrained optimization, hardness of approximation}
}

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2020.30

Sublinear Algorithms and Lower Bounds for Metric TSP Cost Estimation

Authors: Yu Chen, Sampath Kannan, and Sanjeev Khanna

Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

Abstract

We consider the problem of designing sublinear time algorithms for estimating the cost of minimum metric traveling salesman (TSP) tour. Specifically, given access to a n × n distance matrix D that specifies pairwise distances between n points, the goal is to estimate the TSP cost by performing only sublinear (in the size of D) queries. For the closely related problem of estimating the weight of a metric minimum spanning tree (MST), it is known that for any ε > 0, there exists an Õ(n/ε^O(1)) time algorithm that returns a (1 + ε)-approximate estimate of the MST cost. This result immediately implies an Õ(n/ε^O(1)) time algorithm to estimate the TSP cost to within a (2 + ε) factor for any ε > 0. However, no o(n²) time algorithms are known to approximate metric TSP to a factor that is strictly better than 2. On the other hand, there were also no known barriers that rule out existence of (1 + ε)-approximate estimation algorithms for metric TSP with Õ(n) time for any fixed ε > 0. In this paper, we make progress on both algorithms and lower bounds for estimating metric TSP cost. On the algorithmic side, we first consider the graphic TSP problem where the metric D corresponds to shortest path distances in a connected unweighted undirected graph. We show that there exists an Õ(n) time algorithm that estimates the cost of graphic TSP to within a factor of (2-ε₀) for some ε₀ > 0. This is the first sublinear cost estimation algorithm for graphic TSP that achieves an approximation factor less than 2. We also consider another well-studied special case of metric TSP, namely, (1,2)-TSP where all distances are either 1 or 2, and give an Õ(n^1.5) time algorithm to estimate optimal cost to within a factor of 1.625. Our estimation algorithms for graphic TSP as well as for (1,2)-TSP naturally lend themselves to Õ(n) space streaming algorithms that give an 11/6-approximation for graphic TSP and a 1.625-approximation for (1,2)-TSP. These results motivate the natural question if analogously to metric MST, for any ε > 0, (1 + ε)-approximate estimates can be obtained for graphic TSP and (1,2)-TSP using Õ(n) queries. We answer this question in the negative - there exists an ε₀ > 0, such that any algorithm that estimates the cost of graphic TSP ((1,2)-TSP) to within a (1 + ε₀)-factor, necessarily requires Ω(n²) queries. This lower bound result highlights a sharp separation between the metric MST and metric TSP problems. Similarly to many classical approximation algorithms for TSP, our sublinear time estimation algorithms utilize subroutines for estimating the size of a maximum matching in the underlying graph. We show that this is not merely an artifact of our approach, and that for any ε > 0, any algorithm that estimates the cost of graphic TSP or (1,2)-TSP to within a (1 + ε)-factor, can also be used to estimate the size of a maximum matching in a bipartite graph to within an ε n additive error. This connection allows us to translate known lower bounds for matching size estimation in various models to similar lower bounds for metric TSP cost estimation.

Cite as

Yu Chen, Sampath Kannan, and Sanjeev Khanna. Sublinear Algorithms and Lower Bounds for Metric TSP Cost Estimation. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 30:1-30:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.ICALP.2020.30,
  author =	{Chen, Yu and Kannan, Sampath and Khanna, Sanjeev},
  title =	{{Sublinear Algorithms and Lower Bounds for Metric TSP Cost Estimation}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{30:1--30:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.30},
  URN =		{urn:nbn:de:0030-drops-124372},
  doi =		{10.4230/LIPIcs.ICALP.2020.30},
  annote =	{Keywords: sublinear algorithms, TSP, streaming algorithms, query complexity}
}

Document

DOI: 10.4230/LIPIcs.FORC.2020.5

Service in Your Neighborhood: Fairness in Center Location

Authors: Christopher Jung, Sampath Kannan, and Neil Lutz

Published in: LIPIcs, Volume 156, 1st Symposium on Foundations of Responsible Computing (FORC 2020)

Abstract

When selecting locations for a set of centers, standard clustering algorithms may place unfair burden on some individuals and neighborhoods. We formulate a fairness concept that takes local population densities into account. In particular, given k centers to locate and a population of size n, we define the "neighborhood radius" of an individual i as the minimum radius of a ball centered at i that contains at least n/k individuals. Our objective is to ensure that each individual has a center that is within at most a small constant factor of her neighborhood radius. We present several theoretical results: We show that optimizing this factor is NP-hard; we give an approximation algorithm that guarantees a factor of at most 2 in all metric spaces; and we prove matching lower bounds in some metric spaces. We apply a variant of this algorithm to real-world address data, showing that it is quite different from standard clustering algorithms and outperforms them on our objective function and balances the load between centers more evenly.

Cite as

Christopher Jung, Sampath Kannan, and Neil Lutz. Service in Your Neighborhood: Fairness in Center Location. In 1st Symposium on Foundations of Responsible Computing (FORC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 156, pp. 5:1-5:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{jung_et_al:LIPIcs.FORC.2020.5,
  author =	{Jung, Christopher and Kannan, Sampath and Lutz, Neil},
  title =	{{Service in Your Neighborhood: Fairness in Center Location}},
  booktitle =	{1st Symposium on Foundations of Responsible Computing (FORC 2020)},
  pages =	{5:1--5:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-142-9},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{156},
  editor =	{Roth, Aaron},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FORC.2020.5},
  URN =		{urn:nbn:de:0030-drops-120215},
  doi =		{10.4230/LIPIcs.FORC.2020.5},
  annote =	{Keywords: Fairness, Clustering, Facility Location}
}

Document

DOI: 10.4230/LIPIcs.CCC.2018.8

Linear Sketching over F_2

Authors: Sampath Kannan, Elchanan Mossel, Swagato Sanyal, and Grigory Yaroslavtsev

Published in: LIPIcs, Volume 102, 33rd Computational Complexity Conference (CCC 2018)

Abstract

We initiate a systematic study of linear sketching over F_2. For a given Boolean function treated as f : F_2^n -> F_2 a randomized F_2-sketch is a distribution M over d x n matrices with elements over F_2 such that Mx suffices for computing f(x) with high probability. Such sketches for d << n can be used to design small-space distributed and streaming algorithms. Motivated by these applications we study a connection between F_2-sketching and a two-player one-way communication game for the corresponding XOR-function. We conjecture that F_2-sketching is optimal for this communication game. Our results confirm this conjecture for multiple important classes of functions: 1) low-degree F_2-polynomials, 2) functions with sparse Fourier spectrum, 3) most symmetric functions, 4) recursive majority function. These results rely on a new structural theorem that shows that F_2-sketching is optimal (up to constant factors) for uniformly distributed inputs. Furthermore, we show that (non-uniform) streaming algorithms that have to process random updates over F_2 can be constructed as F_2-sketches for the uniform distribution. In contrast with the previous work of Li, Nguyen and Woodruff (STOC'14) who show an analogous result for linear sketches over integers in the adversarial setting our result does not require the stream length to be triply exponential in n and holds for streams of length O(n) constructed through uniformly random updates.

Cite as

Sampath Kannan, Elchanan Mossel, Swagato Sanyal, and Grigory Yaroslavtsev. Linear Sketching over F_2. In 33rd Computational Complexity Conference (CCC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 102, pp. 8:1-8:37, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{kannan_et_al:LIPIcs.CCC.2018.8,
  author =	{Kannan, Sampath and Mossel, Elchanan and Sanyal, Swagato and Yaroslavtsev, Grigory},
  title =	{{Linear Sketching over F\underline2}},
  booktitle =	{33rd Computational Complexity Conference (CCC 2018)},
  pages =	{8:1--8:37},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-069-9},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{102},
  editor =	{Servedio, Rocco A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2018.8},
  URN =		{urn:nbn:de:0030-drops-88819},
  doi =		{10.4230/LIPIcs.CCC.2018.8},
  annote =	{Keywords: Linear sketch, Streaming algorithms, XOR-functions, Communication complexity}
}

Document

DOI: 10.4230/DagRep.7.3.27

Game Theory in AI, Logic, and Algorithms (Dagstuhl Seminar 17111)

Authors: Swarat Chaudhuri, Sampath Kannan, Rupak Majumdar, and Michael J. Wooldridge

Published in: Dagstuhl Reports, Volume 7, Issue 3 (2017)

Abstract

This report documents the program and the outcomes of Dagstuhl Seminar 17111 "Game Theory in AI, Logic, and Algorithms".

Cite as

Swarat Chaudhuri, Sampath Kannan, Rupak Majumdar, and Michael J. Wooldridge. Game Theory in AI, Logic, and Algorithms (Dagstuhl Seminar 17111). In Dagstuhl Reports, Volume 7, Issue 3, pp. 27-32, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@Article{chaudhuri_et_al:DagRep.7.3.27,
  author =	{Chaudhuri, Swarat and Kannan, Sampath and Majumdar, Rupak and Wooldridge, Michael J.},
  title =	{{Game Theory in AI, Logic, and Algorithms (Dagstuhl Seminar 17111)}},
  pages =	{27--32},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2017},
  volume =	{7},
  number =	{3},
  editor =	{Chaudhuri, Swarat and Kannan, Sampath and Majumdar, Rupak and Wooldridge, Michael J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.7.3.27},
  URN =		{urn:nbn:de:0030-drops-79609},
  doi =		{10.4230/DagRep.7.3.27},
  annote =	{Keywords: game theory, formal methods, logic, algorithms, equilibria, multiagent systems}
}

Document

DOI: 10.4230/LIPIcs.CSL.2016.29

Hedging Bets in Markov Decision Processes

Authors: Rajeev Alur, Marco Faella, Sampath Kannan, and Nimit Singhania

Published in: LIPIcs, Volume 62, 25th EACSL Annual Conference on Computer Science Logic (CSL 2016)

Abstract

The classical model of Markov decision processes with costs or rewards, while widely used to formalize optimal decision making, cannot capture scenarios where there are multiple objectives for the agent during the system evolution, but only one of these objectives gets actualized upon termination. We introduce the model of Markov decision processes with alternative objectives (MDPAO) for formalizing optimization in such scenarios. To compute the strategy to optimize the expected cost/reward upon termination, we need to figure out how to balance the values of the alternative objectives. This requires analysis of the underlying infinite-state process that tracks the accumulated values of all the objectives. While the decidability of the problem of computing the exact optimal strategy for the general model remains open, we present the following results. First, for a Markov chain with alternative objectives, the optimal expected cost/reward can be computed in polynomial-time. Second, for a single-state process with two actions and multiple objectives we show how to compute the optimal decision strategy. Third, for a process with only two alternative objectives, we present a reduction to the minimum expected accumulated reward problem for one-counter MDPs, and this leads to decidability for this case under some technical restrictions. Finally, we show that optimal cost/reward can be approximated up to a constant additive factor for the general problem.

Cite as

Rajeev Alur, Marco Faella, Sampath Kannan, and Nimit Singhania. Hedging Bets in Markov Decision Processes. In 25th EACSL Annual Conference on Computer Science Logic (CSL 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 62, pp. 29:1-29:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{alur_et_al:LIPIcs.CSL.2016.29,
  author =	{Alur, Rajeev and Faella, Marco and Kannan, Sampath and Singhania, Nimit},
  title =	{{Hedging Bets in Markov Decision Processes}},
  booktitle =	{25th EACSL Annual Conference on Computer Science Logic (CSL 2016)},
  pages =	{29:1--29:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-022-4},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{62},
  editor =	{Talbot, Jean-Marc and Regnier, Laurent},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2016.29},
  URN =		{urn:nbn:de:0030-drops-65698},
  doi =		{10.4230/LIPIcs.CSL.2016.29},
  annote =	{Keywords: Markov decision processes, Infinite state systems, Multi-objective optimization}
}

Document

DOI: 10.4230/LIPIcs.FSTTCS.2008.1758

STCON in Directed Unique-Path Graphs

Authors: Sampath Kannan, Sanjeev Khanna, and Sudeepa Roy

Published in: LIPIcs, Volume 2, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2008)

Abstract

We study the problem of space-efficient polynomial-time algorithms for {\em directed st-connectivity} (STCON). Given a directed graph $G$, and a pair of vertices $s, t$, the STCON problem is to decide if there exists a path from $s$ to $t$ in $G$. For general graphs, the best polynomial-time algorithm for STCON uses space that is only slightly sublinear. However, for special classes of directed graphs, polynomial-time poly-logarithmic-space algorithms are known for STCON. In this paper, we continue this thread of research and study a class of graphs called \emph{unique-path graphs with respect to source $s$}, where there is at most one simple path from $s$ to any vertex in the graph. For these graphs, we give a polynomial-time algorithm that uses $\tilde O(n^{\varepsilon})$ space for any constant $\varepsilon \in (0,1]$. We also give a polynomial-time, $\tilde O(n^\varepsilon)$-space algorithm to \emph{recognize} unique-path graphs. Unique-path graphs are related to configuration graphs of unambiguous log-space computations, but they can have some directed cycles. Our results may be viewed along the continuum of sublinear-space polynomial-time algorithms for STCON in different classes of directed graphs - from slightly sublinear-space algorithms for general graphs to $O(\log n)$ space algorithms for trees.

Cite as

Sampath Kannan, Sanjeev Khanna, and Sudeepa Roy. STCON in Directed Unique-Path Graphs. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 2, pp. 256-267, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{kannan_et_al:LIPIcs.FSTTCS.2008.1758,
  author =	{Kannan, Sampath and Khanna, Sanjeev and Roy, Sudeepa},
  title =	{{STCON in Directed Unique-Path Graphs}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science},
  pages =	{256--267},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-08-8},
  ISSN =	{1868-8969},
  year =	{2008},
  volume =	{2},
  editor =	{Hariharan, Ramesh and Mukund, Madhavan and Vinay, V},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2008.1758},
  URN =		{urn:nbn:de:0030-drops-17589},
  doi =		{10.4230/LIPIcs.FSTTCS.2008.1758},
  annote =	{Keywords: Algorithm, complexity, st-connectivity}
}

7 Search Results for "Kannan, Sampath"

Pipeline Interventions

Abstract

Cite as

Sublinear Algorithms and Lower Bounds for Metric TSP Cost Estimation

Abstract

Cite as

Service in Your Neighborhood: Fairness in Center Location

Abstract

Cite as

Linear Sketching over F_2

Abstract

Cite as

Game Theory in AI, Logic, and Algorithms (Dagstuhl Seminar 17111)

Abstract

Cite as

Hedging Bets in Markov Decision Processes

Abstract

Cite as

STCON in Directed Unique-Path Graphs

Abstract

Cite as

Thanks for your feedback!

Could not send message