2 Search Results for "Liu, Daogao"

Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2024.29
Approximation Algorithms for Correlated Knapsack Orienteering

Authors: David Alemán Espinosa and Chaitanya Swamy

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

Abstract
We consider the correlated knapsack orienteering (CorrKO) problem: we are given a travel budget B, processing-time budget W, finite metric space (V,d) with root ρ ∈ V, where each vertex is associated with a job with possibly correlated random size and random reward that become known only when the job completes. Random variables are independent across different vertices. The goal is to compute a ρ-rooted path of length at most B, in a possibly adaptive fashion, that maximizes the reward collected from jobs that processed by time W. To our knowledge, CorrKO has not been considered before, though prior work has considered the uncorrelated problem, stochastic knapsack orienteering, and correlated orienteering, which features only one budget constraint on the sum of travel-time and processing-times. Gupta et al. [Gupta et al., 2015] showed that the uncorrelated version of this problem has a constant-factor adaptivity gap. We show that, perhaps surprisingly and in stark contrast to the uncorrelated problem, the adaptivity gap of CorrKO is is at least Ω(max{√log(B),√(log log(W))}). Complementing this result, we devise non-adaptive algorithms that obtain: (a) O(log log W)-approximation in quasi-polytime; and (b) O(log W)-approximation in polytime. This also establishes that the adaptivity gap for CorrKO is at most O(log log W). We obtain similar guarantees for CorrKO with cancellations, wherein a job can be cancelled before its completion time, foregoing its reward. We show that an α-approximation for CorrKO implies an O(α)-approximation for CorrKO with cancellations. We also consider the special case of CorrKO where job sizes are weighted Bernoulli distributions, and more generally where the distributions are supported on at most two points (2CorrKO). Although weighted Bernoulli distributions suffice to yield an Ω(√{log log B}) adaptivity-gap lower bound for (uncorrelated) stochastic orienteering, we show that they are easy instances for CorrKO. We develop non-adaptive algorithms that achieve O(1)-approximation, in polytime for weighted Bernoulli distributions, and in (n+log B)^O(log W)-time for 2CorrKO. (Thus, our adaptivity-gap lower-bound example, which uses distributions of support-size 3, is tight in terms of support-size of the distributions.) Finally, we leverage our techniques to provide a quasi-polynomial time O(log log B) approximation algorithm for correlated orienteering improving upon the approximation guarantee in [Bansal and Nagarajan, 2015].
Cite as

David Alemán Espinosa and Chaitanya Swamy. Approximation Algorithms for Correlated Knapsack Orienteering. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 29:1-29:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{alemanespinosa_et_al:LIPIcs.APPROX/RANDOM.2024.29,
  author =	{Alem\'{a}n Espinosa, David and Swamy, Chaitanya},
  title =	{{Approximation Algorithms for Correlated Knapsack Orienteering}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)},
  pages =	{29:1--29:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-348-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{317},
  editor =	{Kumar, Amit and Ron-Zewi, Noga},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.29},
  URN =		{urn:nbn:de:0030-drops-210224},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2024.29},
  annote =	{Keywords: Approximation algorithms, Stochastic orienteering, Adaptivity gap, Vehicle routing problems, LP rounding algorithms}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2020.45
Algorithms and Adaptivity Gaps for Stochastic k-TSP

Authors: Haotian Jiang, Jian Li, Daogao Liu, and Sahil Singla

Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)

Abstract
Given a metric (V,d) and a root ∈ V, the classic k-TSP problem is to find a tour originating at the root of minimum length that visits at least k nodes in V. In this work, motivated by applications where the input to an optimization problem is uncertain, we study two stochastic versions of k-TSP. In Stoch-Reward k-TSP, originally defined by Ene-Nagarajan-Saket [Ene et al., 2018], each vertex v in the given metric (V,d) contains a stochastic reward R_v. The goal is to adaptively find a tour of minimum expected length that collects at least reward k; here "adaptively" means our next decision may depend on previous outcomes. Ene et al. give an O(log k)-approximation adaptive algorithm for this problem, and left open if there is an O(1)-approximation algorithm. We totally resolve their open question, and even give an O(1)-approximation non-adaptive algorithm for Stoch-Reward k-TSP. We also introduce and obtain similar results for the Stoch-Cost k-TSP problem. In this problem each vertex v has a stochastic cost C_v, and the goal is to visit and select at least k vertices to minimize the expected sum of tour length and cost of selected vertices. Besides being a natural stochastic generalization of k-TSP, this problem is also interesting because it generalizes the Price of Information framework [Singla, 2018] from deterministic probing costs to metric probing costs. Our techniques are based on two crucial ideas: "repetitions" and "critical scaling". In general, replacing a random variable with its expectation leads to very poor results. We show that for our problems, if we truncate the random variables at an ideal threshold, then their expected values form a good surrogate. Here, we rely on running several repetitions of our algorithm with the same threshold, and then argue concentration using Freedman’s and Jogdeo-Samuels' inequalities. Unfortunately, this ideal threshold depends on how far we are from achieving our target k, which a non-adaptive algorithm does not know. To overcome this barrier, we truncate the random variables at various different scales and identify a "critical" scale.
Cite as

Haotian Jiang, Jian Li, Daogao Liu, and Sahil Singla. Algorithms and Adaptivity Gaps for Stochastic k-TSP. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 45:1-45:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{jiang_et_al:LIPIcs.ITCS.2020.45,
  author =	{Jiang, Haotian and Li, Jian and Liu, Daogao and Singla, Sahil},
  title =	{{Algorithms and Adaptivity Gaps for Stochastic k-TSP}},
  booktitle =	{11th Innovations in Theoretical Computer Science Conference (ITCS 2020)},
  pages =	{45:1--45:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-134-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{151},
  editor =	{Vidick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.45},
  URN =		{urn:nbn:de:0030-drops-117308},
  doi =		{10.4230/LIPIcs.ITCS.2020.45},
  annote =	{Keywords: approximation algorithms, stochastic optimization, travelling salesman problem}
}
  • Refine by Author
  • 1 Alemán Espinosa, David
  • 1 Jiang, Haotian
  • 1 Li, Jian
  • 1 Liu, Daogao
  • 1 Singla, Sahil
  • Show More...

  • Refine by Classification
  • 2 Theory of computation → Approximation algorithms analysis
  • 1 Mathematics of computing → Discrete optimization
  • 1 Theory of computation → Stochastic control and optimization

  • Refine by Keyword
  • 1 Adaptivity gap
  • 1 Approximation algorithms
  • 1 LP rounding algorithms
  • 1 Stochastic orienteering
  • 1 Vehicle routing problems
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2020
  • 1 2024

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 Imprint Privacy Contact