Search Results

Documents authored by Nagarajan, Viswanath

Document
DOI: 10.4230/LIPIcs.FSTTCS.2017.27
Approximation Algorithms for Stochastic k-TSP

Authors: Alina Ene, Viswanath Nagarajan, and Rishi Saket

Published in: LIPIcs, Volume 93, 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)

Abstract
This paper studies the stochastic variant of the classical k-TSP problem where rewards at the vertices are independent random variables which are instantiated upon the tour's visit. The objective is to minimize the expected length of a tour that collects reward at least k. The solution is a policy describing the tour which may (adaptive) or may not (non-adaptive) depend on the observed rewards. Our work presents an adaptive O(log k)-approximation algorithm for Stochastic k-TSP, along with a non-adaptive O(log^2 k)-approximation algorithm which also upper bounds the adaptivity gap by O(log^2 k). We also show that the adaptivity gap of Stochastic k-TSP is at least e, even in the special case of stochastic knapsack cover.
Cite as

Alina Ene, Viswanath Nagarajan, and Rishi Saket. Approximation Algorithms for Stochastic k-TSP. In 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 93, pp. 27:1-27:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{ene_et_al:LIPIcs.FSTTCS.2017.27,
  author =	{Ene, Alina and Nagarajan, Viswanath and Saket, Rishi},
  title =	{{Approximation Algorithms for Stochastic k-TSP}},
  booktitle =	{37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)},
  pages =	{27:1--27:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-055-2},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{93},
  editor =	{Lokam, Satya and Ramanujam, R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2017.27},
  URN =		{urn:nbn:de:0030-drops-83910},
  doi =		{10.4230/LIPIcs.FSTTCS.2017.27},
  annote =	{Keywords: Stochastic TSP, algorithms, approximation, adaptivity gap}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2017.12
Online Covering with Sum of $ell_q$-Norm Objectives

Authors: Viswanath Nagarajan and Xiangkun Shen

Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)

Abstract
We consider fractional online covering problems with lq-norm objectives. The problem of interest is of the form min{ f(x) : Ax >= 1, x >= 0} where f(x) is the weighted sum of lq-norms and A is a non-negative matrix. The rows of A (i.e. covering constraints) arrive online over time. We provide an online O(log d+log p)-competitive algorithm where p is the maximum to minimum ratio of A and A is the row sparsity of A. This is based on the online primal-dual framework where we use the dual of the above convex program. Our result expands the class of convex objectives that admit good online algorithms: prior results required a monotonicity condition on the objective which is not satisfied here. This result is nearly tight even for the linear special case. As direct applications, we obtain (i) improved online algorithms for non-uniform buy-at-bulk network design and (ii) the first online algorithm for throughput maximization under lq-norm edge capacities.
Cite as

Viswanath Nagarajan and Xiangkun Shen. Online Covering with Sum of $ell_q$-Norm Objectives. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 12:1-12:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{nagarajan_et_al:LIPIcs.ICALP.2017.12,
  author =	{Nagarajan, Viswanath and Shen, Xiangkun},
  title =	{{Online Covering with Sum of \$ell\underlineq\$-Norm Objectives}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{12:1--12:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.12},
  URN =		{urn:nbn:de:0030-drops-73839},
  doi =		{10.4230/LIPIcs.ICALP.2017.12},
  annote =	{Keywords: online algorithm, covering/packing problem, convex, buy-at-bulk, throughput maximization}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2015.416
The Container Selection Problem

Authors: Viswanath Nagarajan, Kanthi K. Sarpatwar, Baruch Schieber, Hadas Shachnai, and Joel L. Wolf

Published in: LIPIcs, Volume 40, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)

Abstract
We introduce and study a network resource management problem that is a special case of non-metric k-median, naturally arising in cross platform scheduling and cloud computing. In the continuous d-dimensional container selection problem, we are given a set C of input points in d-dimensional Euclidean space, for some d >= 2, and a budget k. An input point p can be assigned to a "container point" c only if c dominates p in every dimension. The assignment cost is then equal to the L1-norm of the container point. The goal is to find k container points in the d-dimensional space, such that the total assignment cost for all input points is minimized. The discrete variant of the problem has one key distinction, namely, the container points must be chosen from a given set F of points. For the continuous version, we obtain a polynomial time approximation scheme for any fixed dimension d>= 2. On the negative side, we show that the problem is NP-hard for any d>=3. We further show that the discrete version is significantly harder, as it is NP-hard to approximate without violating the budget k in any dimension d>=3. Thus, we focus on obtaining bi-approximation algorithms. For d=2, the bi-approximation guarantee is (1+epsilon,3), i.e., for any epsilon>0, our scheme outputs a solution of size 3k and cost at most (1+epsilon) times the optimum. For fixed d>2, we present a (1+epsilon,O((1/epsilon)log k)) bi-approximation algorithm.
Cite as

Viswanath Nagarajan, Kanthi K. Sarpatwar, Baruch Schieber, Hadas Shachnai, and Joel L. Wolf. The Container Selection Problem. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 40, pp. 416-434, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{nagarajan_et_al:LIPIcs.APPROX-RANDOM.2015.416,
  author =	{Nagarajan, Viswanath and Sarpatwar, Kanthi K. and Schieber, Baruch and Shachnai, Hadas and Wolf, Joel L.},
  title =	{{The Container Selection Problem}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)},
  pages =	{416--434},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-89-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{40},
  editor =	{Garg, Naveen and Jansen, Klaus and Rao, Anup and Rolim, Jos\'{e} D. P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2015.416},
  URN =		{urn:nbn:de:0030-drops-53153},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2015.416},
  annote =	{Keywords: non-metric k-median, geometric hitting set, approximation algorithms, cloud computing, cross platform scheduling.}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact