Search Results

Documents authored by Chawla, Shuchi

Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2024.2
Online Time-Windows TSP with Predictions

Authors: Shuchi Chawla and Dimitris Christou

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

Abstract
In the Time-Windows TSP (TW-TSP) we are given requests at different locations on a network; each request is endowed with a reward and an interval of time; the goal is to find a tour that visits as much reward as possible during the corresponding time window. For the online version of this problem, where each request is revealed at the start of its time window, no finite competitive ratio can be obtained. We consider a version of the problem where the algorithm is presented with predictions of where and when the online requests will appear, without any knowledge of the quality of this side information. Vehicle routing problems such as the TW-TSP can be very sensitive to errors or changes in the input due to the hard time-window constraints, and it is unclear whether imperfect predictions can be used to obtain a finite competitive ratio. We show that good performance can be achieved by explicitly building slack into the solution. Our main result is an online algorithm that achieves a competitive ratio logarithmic in the diameter of the underlying network, matching the performance of the best offline algorithm to within factors that depend on the quality of the provided predictions. The competitive ratio degrades smoothly as a function of the quality and we show that this dependence is tight within constant factors.
Cite as

Shuchi Chawla and Dimitris Christou. Online Time-Windows TSP with Predictions. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 2:1-2:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{chawla_et_al:LIPIcs.APPROX/RANDOM.2024.2,
  author =	{Chawla, Shuchi and Christou, Dimitris},
  title =	{{Online Time-Windows TSP with Predictions}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)},
  pages =	{2:1--2:21},
  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.2},
  URN =		{urn:nbn:de:0030-drops-209954},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2024.2},
  annote =	{Keywords: Travelling Salesman Problem, Predictions, Learning-Augmented Algorithms, Approximation}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2023.26
Approximating Pandora’s Box with Correlations

Authors: Shuchi Chawla, Evangelia Gergatsouli, Jeremy McMahan, and Christos Tzamos

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

Abstract
We revisit the classic Pandora’s Box (PB) problem under correlated distributions on the box values. Recent work of [Shuchi Chawla et al., 2020] obtained constant approximate algorithms for a restricted class of policies for the problem that visit boxes in a fixed order. In this work, we study the complexity of approximating the optimal policy which may adaptively choose which box to visit next based on the values seen so far. Our main result establishes an approximation-preserving equivalence of PB to the well studied Uniform Decision Tree (UDT) problem from stochastic optimization and a variant of the Min-Sum Set Cover (MSSC_f) problem. For distributions of support m, UDT admits a log m approximation, and while a constant factor approximation in polynomial time is a long-standing open problem, constant factor approximations are achievable in subexponential time [Ray Li et al., 2020]. Our main result implies that the same properties hold for PB and MSSC_f. We also study the case where the distribution over values is given more succinctly as a mixture of m product distributions. This problem is again related to a noisy variant of the Optimal Decision Tree which is significantly more challenging. We give a constant-factor approximation that runs in time n^Õ(m²/ε²) when the mixture components on every box are either identical or separated in TV distance by ε.
Cite as

Shuchi Chawla, Evangelia Gergatsouli, Jeremy McMahan, and Christos Tzamos. Approximating Pandora’s Box with Correlations. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 26:1-26:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{chawla_et_al:LIPIcs.APPROX/RANDOM.2023.26,
  author =	{Chawla, Shuchi and Gergatsouli, Evangelia and McMahan, Jeremy and Tzamos, Christos},
  title =	{{Approximating Pandora’s Box with Correlations}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)},
  pages =	{26:1--26:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-296-9},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{275},
  editor =	{Megow, Nicole and Smith, Adam},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.26},
  URN =		{urn:nbn:de:0030-drops-188519},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2023.26},
  annote =	{Keywords: Pandora’s Box, Min Sum Set Cover, stochastic optimization, approximation preserving reduction}
}
Document
DOI: 10.4230/LIPIcs.FORC.2022.4
Individually-Fair Auctions for Multi-Slot Sponsored Search

Authors: Shuchi Chawla, Rojin Rezvan, and Nathaniel Sauerberg

Published in: LIPIcs, Volume 218, 3rd Symposium on Foundations of Responsible Computing (FORC 2022)

Abstract
We design fair sponsored search auctions that achieve a near-optimal tradeoff between fairness and quality. Our work builds upon the model and auction design of Chawla and Jagadeesan [Chawla and Jagadeesan, 2022], who considered the special case of a single slot. We consider sponsored search settings with multiple slots and the standard model of click through rates that are multiplicatively separable into an advertiser-specific component and a slot-specific component. When similar users have similar advertiser-specific click through rates, our auctions achieve the same near-optimal tradeoff between fairness and quality as in [Chawla and Jagadeesan, 2022]. When similar users can have different advertiser-specific preferences, we show that a preference-based fairness guarantee holds. Finally, we provide a computationally efficient algorithm for computing payments for our auctions as well as those in previous work, resolving another open direction from [Chawla and Jagadeesan, 2022].
Cite as

Shuchi Chawla, Rojin Rezvan, and Nathaniel Sauerberg. Individually-Fair Auctions for Multi-Slot Sponsored Search. In 3rd Symposium on Foundations of Responsible Computing (FORC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 218, pp. 4:1-4:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{chawla_et_al:LIPIcs.FORC.2022.4,
  author =	{Chawla, Shuchi and Rezvan, Rojin and Sauerberg, Nathaniel},
  title =	{{Individually-Fair Auctions for Multi-Slot Sponsored Search}},
  booktitle =	{3rd Symposium on Foundations of Responsible Computing (FORC 2022)},
  pages =	{4:1--4:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-226-6},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{218},
  editor =	{Celis, L. Elisa},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FORC.2022.4},
  URN =		{urn:nbn:de:0030-drops-165272},
  doi =		{10.4230/LIPIcs.FORC.2022.4},
  annote =	{Keywords: algorithmic fairness, advertising auctions, and individual fairness}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2022.42
Individual Fairness in Advertising Auctions Through Inverse Proportionality

Authors: Shuchi Chawla and Meena Jagadeesan

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)

Abstract
Recent empirical work demonstrates that online advertisement can exhibit bias in the delivery of ads across users even when all advertisers bid in a non-discriminatory manner. We study the design ad auctions that, given fair bids, are guaranteed to produce fair outcomes. Following the works of Dwork and Ilvento [2019] and Chawla et al. [2020], our goal is to design a truthful auction that satisfies "individual fairness" in its outcomes: informally speaking, users that are similar to each other should obtain similar allocations of ads. Within this framework we quantify the tradeoff between social welfare maximization and fairness. This work makes two conceptual contributions. First, we express the fairness constraint as a kind of stability condition: any two users that are assigned multiplicatively similar values by all the advertisers must receive additively similar allocations for each advertiser. This value stability constraint is expressed as a function that maps the multiplicative distance between value vectors to the maximum allowable 𝓁_{∞} distance between the corresponding allocations. Standard auctions do not satisfy this kind of value stability. Second, we introduce a new class of allocation algorithms called Inverse Proportional Allocation that achieve a near optimal tradeoff between fairness and social welfare for a broad and expressive class of value stability conditions. These allocation algorithms are truthful and prior-free, and achieve a constant factor approximation to the optimal (unconstrained) social welfare. In particular, the approximation ratio is independent of the number of advertisers in the system. In this respect, these allocation algorithms greatly surpass the guarantees achieved in previous work. We also extend our results to broader notions of fairness that we call subset fairness.
Cite as

Shuchi Chawla and Meena Jagadeesan. Individual Fairness in Advertising Auctions Through Inverse Proportionality. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 42:1-42:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{chawla_et_al:LIPIcs.ITCS.2022.42,
  author =	{Chawla, Shuchi and Jagadeesan, Meena},
  title =	{{Individual Fairness in Advertising Auctions Through Inverse Proportionality}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{42:1--42:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.42},
  URN =		{urn:nbn:de:0030-drops-156385},
  doi =		{10.4230/LIPIcs.ITCS.2022.42},
  annote =	{Keywords: Algorithmic fairness, advertising auctions}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2014.48
Network Design with Coverage Costs

Authors: Siddharth Barman, Shuchi Chawla, and Seeun Umboh

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

Abstract
We study network design with a cost structure motivated by redundancy in data traffic. We are given a graph, g groups of terminals, and a universe of data packets. Each group of terminals desires a subset of the packets from its respective source. The cost of routing traffic on any edge in the network is proportional to the total size of the distinct packets that the edge carries. Our goal is to find a minimum cost routing. We focus on two settings. In the first, the collection of packet sets desired by source-sink pairs is laminar. For this setting, we present a primal-dual based 2-approximation, improving upon a logarithmic approximation due to Barman and Chawla (2012){BC12}. In the second setting, packet sets can have non-trivial intersection. We focus on the case where each packet is desired by either a single terminal group or by all of the groups. This setting does not admit an O(log^{{1}/{4} - gamma} g)-approximation for any constant gamma under a standard assumption; we present an O(log g)-approximation when the graph is unweighted. Our approximation for the second setting is based on a novel spanner-type construction in unweighted graphs that, given a collection of g vertex subsets, finds a subgraph of cost only a constant factor more than the minimum spanning tree of the graph, such that every subset in the collection has a Steiner tree in the subgraph of cost at most O(log g) that of its minimum Steiner tree in the original graph. We call such a subgraph a group spanner.
Cite as

Siddharth Barman, Shuchi Chawla, and Seeun Umboh. Network Design with Coverage Costs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 48-63, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{barman_et_al:LIPIcs.APPROX-RANDOM.2014.48,
  author =	{Barman, Siddharth and Chawla, Shuchi and Umboh, Seeun},
  title =	{{Network Design with Coverage Costs}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)},
  pages =	{48--63},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-74-3},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{28},
  editor =	{Jansen, Klaus and Rolim, Jos\'{e} and Devanur, Nikhil R. and Moore, Cristopher},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.48},
  URN =		{urn:nbn:de:0030-drops-46876},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2014.48},
  annote =	{Keywords: Network Design, Spanner, Primal Dual Method, Traffic Redundancy}
}
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