Search Results

Documents authored by Vassilvitskii, Sergei

Document
DOI: 10.4230/LIPIcs.ITCS.2025.46
Data-Driven Solution Portfolios

Authors: Marina Drygala, Silvio Lattanzi, Andreas Maggiori, Miltiadis Stouras, Ola Svensson, and Sergei Vassilvitskii

Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)

Abstract
In this paper, we consider a new problem of portfolio optimization using stochastic information. In a setting where there is some uncertainty, we ask how to best select k potential solutions, with the goal of optimizing the value of the best solution. More formally, given a combinatorial problem Π, a set of value functions 𝒱 over the solutions of Π, and a distribution 𝒟 over 𝒱, our goal is to select k solutions of Π that maximize or minimize the expected value of the best of those solutions. For a simple example, consider the classic knapsack problem: given a universe of elements each with unit weight and a positive value, the task is to select r elements maximizing the total value. Now suppose that each element’s weight comes from a (known) distribution. How should we select k different solutions so that one of them is likely to yield a high value? In this work, we tackle this basic problem, and generalize it to the setting where the underlying set system forms a matroid. On the technical side, it is clear that the candidate solutions we select must be diverse and anti-correlated; however, it is not clear how to do so efficiently. Our main result is a polynomial-time algorithm that constructs a portfolio within a constant factor of the optimal.
Cite as

Marina Drygala, Silvio Lattanzi, Andreas Maggiori, Miltiadis Stouras, Ola Svensson, and Sergei Vassilvitskii. Data-Driven Solution Portfolios. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 46:1-46:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{drygala_et_al:LIPIcs.ITCS.2025.46,
  author =	{Drygala, Marina and Lattanzi, Silvio and Maggiori, Andreas and Stouras, Miltiadis and Svensson, Ola and Vassilvitskii, Sergei},
  title =	{{Data-Driven Solution Portfolios}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{46:1--46:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-361-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{325},
  editor =	{Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.46},
  URN =		{urn:nbn:de:0030-drops-226740},
  doi =		{10.4230/LIPIcs.ITCS.2025.46},
  annote =	{Keywords: solution portfolios, data-driven algorithm design, matroids}
}
Document
DOI: 10.4230/DagRep.13.2.1
Scheduling (Dagstuhl Seminar 23061)

Authors: Nicole Megow, Benjamin J. Moseley, David Shmoys, Ola Svensson, Sergei Vassilvitskii, and Jens Schlöter

Published in: Dagstuhl Reports, Volume 13, Issue 2 (2023)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 23061 "Scheduling". The seminar focused on the emerging models for beyond-worst case algorithm design, in particular, recent approaches that incorporate learning. This includes models for the integration of learning into algorithm design that have been proposed recently and that have already demonstrated advances in the state-of-art for various scheduling applications: (i) scheduling with error-prone learned predictions, (ii) data-driven algorithm design, and (iii) stochastic and Bayesian learning in scheduling.
Cite as

Nicole Megow, Benjamin J. Moseley, David Shmoys, Ola Svensson, Sergei Vassilvitskii, and Jens Schlöter. Scheduling (Dagstuhl Seminar 23061). In Dagstuhl Reports, Volume 13, Issue 2, pp. 1-19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@Article{megow_et_al:DagRep.13.2.1,
  author =	{Megow, Nicole and Moseley, Benjamin J. and Shmoys, David and Svensson, Ola and Vassilvitskii, Sergei and Schl\"{o}ter, Jens},
  title =	{{Scheduling (Dagstuhl Seminar 23061)}},
  pages =	{1--19},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2023},
  volume =	{13},
  number =	{2},
  editor =	{Megow, Nicole and Moseley, Benjamin J. and Shmoys, David and Svensson, Ola and Vassilvitskii, Sergei and Schl\"{o}ter, Jens},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.13.2.1},
  URN =		{urn:nbn:de:0030-drops-191789},
  doi =		{10.4230/DagRep.13.2.1},
  annote =	{Keywords: scheduling, mathematical optimization, approximation algorithms, learning methods, uncertainty}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2023.48
Differentially Private Continual Releases of Streaming Frequency Moment Estimations

Authors: Alessandro Epasto, Jieming Mao, Andres Munoz Medina, Vahab Mirrokni, Sergei Vassilvitskii, and Peilin Zhong

Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)

Abstract
The streaming model of computation is a popular approach for working with large-scale data. In this setting, there is a stream of items and the goal is to compute the desired quantities (usually data statistics) while making a single pass through the stream and using as little space as possible. Motivated by the importance of data privacy, we develop differentially private streaming algorithms under the continual release setting, where the union of outputs of the algorithm at every timestamp must be differentially private. Specifically, we study the fundamental 𝓁_p (p ∈ [0,+∞)) frequency moment estimation problem under this setting, and give an ε-DP algorithm that achieves (1+η)-relative approximation (∀ η ∈ (0,1)) with polylog(Tn) additive error and uses polylog(Tn)⋅ max(1, n^{1-2/p}) space, where T is the length of the stream and n is the size of the universe of elements. Our space is near optimal up to poly-logarithmic factors even in the non-private setting. To obtain our results, we first reduce several primitives under the differentially private continual release model, such as counting distinct elements, heavy hitters and counting low frequency elements, to the simpler, counting/summing problems in the same setting. Based on these primitives, we develop a differentially private continual release level set estimation approach to address the 𝓁_p frequency moment estimation problem. We also provide a simple extension of our results to the harder sliding window model, where the statistics must be maintained over the past W data items.
Cite as

Alessandro Epasto, Jieming Mao, Andres Munoz Medina, Vahab Mirrokni, Sergei Vassilvitskii, and Peilin Zhong. Differentially Private Continual Releases of Streaming Frequency Moment Estimations. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 48:1-48:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{epasto_et_al:LIPIcs.ITCS.2023.48,
  author =	{Epasto, Alessandro and Mao, Jieming and Medina, Andres Munoz and Mirrokni, Vahab and Vassilvitskii, Sergei and Zhong, Peilin},
  title =	{{Differentially Private Continual Releases of Streaming Frequency Moment Estimations}},
  booktitle =	{14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  pages =	{48:1--48:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-263-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{251},
  editor =	{Tauman Kalai, Yael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.48},
  URN =		{urn:nbn:de:0030-drops-175513},
  doi =		{10.4230/LIPIcs.ITCS.2023.48},
  annote =	{Keywords: Differential Privacy, Continual Release, Sliding Window, Streaming Algorithms, Distinct Elements, Frequency Moment Estimation}
}
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