7 Search Results for "Shmoys, David"

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-dev.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
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2021.109
The Greedy Algorithm Is not Optimal for On-Line Edge Coloring

Authors: Amin Saberi and David Wajc

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

Abstract
Nearly three decades ago, Bar-Noy, Motwani and Naor showed that no online edge-coloring algorithm can edge color a graph optimally. Indeed, their work, titled "the greedy algorithm is optimal for on-line edge coloring", shows that the competitive ratio of 2 of the naïve greedy algorithm is best possible online. However, their lower bound required bounded-degree graphs, of maximum degree Δ = O(log n), which prompted them to conjecture that better bounds are possible for higher-degree graphs. While progress has been made towards resolving this conjecture for restricted inputs and arrivals or for random arrival orders, an answer for fully general adversarial arrivals remained elusive. We resolve this thirty-year-old conjecture in the affirmative, presenting a (1.9+o(1))-competitive online edge coloring algorithm for general graphs of degree Δ = ω(log n) under vertex arrivals. At the core of our results, and of possible independent interest, is a new online algorithm which rounds a fractional bipartite matching x online under vertex arrivals, guaranteeing that each edge e is matched with probability (1/2+c)⋅ x_e, for a constant c > 0.027.
Cite as

Amin Saberi and David Wajc. The Greedy Algorithm Is not Optimal for On-Line Edge Coloring. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 109:1-109:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{saberi_et_al:LIPIcs.ICALP.2021.109,
  author =	{Saberi, Amin and Wajc, David},
  title =	{{The Greedy Algorithm Is not Optimal for On-Line Edge Coloring}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{109:1--109:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.109},
  URN =		{urn:nbn:de:0030-drops-141786},
  doi =		{10.4230/LIPIcs.ICALP.2021.109},
  annote =	{Keywords: Online algorithms, edge coloring, greedy, online matching}
}
Document
DOI: 10.4230/DagRep.10.2.50
Scheduling (Dagstuhl Seminar 20081)

Authors: Nicole Megow, David Shmoys, and Ola Svensson

Published in: Dagstuhl Reports, Volume 10, Issue 2 (2020)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 20081 "Scheduling". The seminar focused on the interplay between scheduling problems and problems that arise in the management of transportation and traffic. Important aspects at the intersection of these two research directions include data-driven approaches in dynamic decision-making, scheduling in combination with routing, shared mobility, and coordination versus competition.
Cite as

Nicole Megow, David Shmoys, and Ola Svensson. Scheduling (Dagstuhl Seminar 20081). In Dagstuhl Reports, Volume 10, Issue 2, pp. 50-75, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@Article{megow_et_al:DagRep.10.2.50,
  author =	{Megow, Nicole and Shmoys, David and Svensson, Ola},
  title =	{{Scheduling (Dagstuhl Seminar 20081)}},
  pages =	{50--75},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2020},
  volume =	{10},
  number =	{2},
  editor =	{Megow, Nicole and Shmoys, David and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.10.2.50},
  URN =		{urn:nbn:de:0030-drops-130590},
  doi =		{10.4230/DagRep.10.2.50},
  annote =	{Keywords: scheduling, optimization, approximation algorithms, routing, transportation, mechanism design}
}
Document
DOI: 10.4230/LIPIcs.ESA.2017.62
Prize-Collecting TSP with a Budget Constraint

Authors: Alice Paul, Daniel Freund, Aaron Ferber, David B. Shmoys, and David P. Williamson

Published in: LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017)

Abstract
We consider constrained versions of the prize-collecting traveling salesman and the minimum spanning tree problems. The goal is to maximize the number of vertices in the returned tour/tree subject to a bound on the tour/tree cost. We present a 2-approximation algorithm for these problems based on a primal-dual approach. The algorithm relies on finding a threshold value for the dual variable corresponding to the budget constraint in the primal and then carefully constructing a tour/tree that is just within budget. Thereby, we improve the best-known guarantees from 3+epsilon and 2+epsilon for the tree and the tour version, respectively. Our analysis extends to the setting with weighted vertices, in which we want to maximize the total weight of vertices in the tour/tree subject to the same budget constraint.
Cite as

Alice Paul, Daniel Freund, Aaron Ferber, David B. Shmoys, and David P. Williamson. Prize-Collecting TSP with a Budget Constraint. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 62:1-62:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{paul_et_al:LIPIcs.ESA.2017.62,
  author =	{Paul, Alice and Freund, Daniel and Ferber, Aaron and Shmoys, David B. and Williamson, David P.},
  title =	{{Prize-Collecting TSP with a Budget Constraint}},
  booktitle =	{25th Annual European Symposium on Algorithms (ESA 2017)},
  pages =	{62:1--62:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-049-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{87},
  editor =	{Pruhs, Kirk and Sohler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.62},
  URN =		{urn:nbn:de:0030-drops-78375},
  doi =		{10.4230/LIPIcs.ESA.2017.62},
  annote =	{Keywords: approximation algorithms, traveling salesman problem}
}
Document
DOI: 10.4230/DagSemProc.07391.2
Sampling-based Approximation Algorithms for Multi-stage Stochastic Optimization

Authors: Chaitanya Swamy and David Shmoys

Published in: Dagstuhl Seminar Proceedings, Volume 7391, Probabilistic Methods in the Design and Analysis of Algorithms (2007)

Abstract
Stochastic optimization problems provide a means to model uncertainty in the input data where the uncertainty is modeled by a probability distribution over the possible realizations of the data. We consider a broad class of these problems, called {it multi-stage stochastic programming problems with recourse}, where the uncertainty evolves through a series of stages and one take decisions in each stage in response to the new information learned. These problems are often computationally quite difficult with even very specialized (sub)problems being $#P$-complete. We obtain the first fully polynomial randomized approximation scheme (FPRAS) for a broad class of multi-stage stochastic linear programming problems with any constant number of stages, without placing any restrictions on the underlying probability distribution or on the cost structure of the input. For any fixed $k$, for a rich class of $k$-stage stochastic linear programs (LPs), we show that, for any probability distribution, for any $epsilon>0$, one can compute, with high probability, a solution with expected cost at most $(1+e)$ times the optimal expected cost, in time polynomial in the input size, $frac{1}{epsilon}$, and a parameter $lambda$ that is an upper bound on the cost-inflation over successive stages. Moreover, the algorithm analyzed is a simple and intuitive algorithm that is often used in practice, the {it sample average approximation} (SAA) method. In this method, one draws certain samples from the underlying distribution, constructs an approximate distribution from these samples, and solves the stochastic problem given by this approximate distribution. This is the first result establishing that the SAA method yields near-optimal solutions for (a class of) multi-stage programs with a polynomial number of samples. As a corollary of this FPRAS, by adapting a generic rounding technique of Shmoys and Swamy, we also obtain the first approximation algorithms for the analogous class of multi-stage stochastic integer programs, which includes the multi-stage versions of the set cover, vertex cover, multicut on trees, facility location, and multicommodity flow problems.
Cite as

Chaitanya Swamy and David Shmoys. Sampling-based Approximation Algorithms for Multi-stage Stochastic Optimization. In Probabilistic Methods in the Design and Analysis of Algorithms. Dagstuhl Seminar Proceedings, Volume 7391, pp. 1-24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{swamy_et_al:DagSemProc.07391.2,
  author =	{Swamy, Chaitanya and Shmoys, David},
  title =	{{Sampling-based Approximation Algorithms for Multi-stage Stochastic Optimization}},
  booktitle =	{Probabilistic Methods in the Design and Analysis of Algorithms},
  pages =	{1--24},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{7391},
  editor =	{Martin Dietzfelbinger and Shang-Hua Teng and Eli Upfal and Berthold V\"{o}cking},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.07391.2},
  URN =		{urn:nbn:de:0030-drops-12906},
  doi =		{10.4230/DagSemProc.07391.2},
  annote =	{Keywords: Stochastic optimization, approximation algorithms, randomized algorithms, linear programming}
}
Document
DOI: 10.4230/DagSemProc.05031.5
Approximation Algorithms for 2-stage and Multi-stage Stochastic Optimization

Authors: Chaitanya Swamy and David Shmoys

Published in: Dagstuhl Seminar Proceedings, Volume 5031, Algorithms for Optimization with Incomplete Information (2005)

Abstract
Stochastic optimization problems attempt to model uncertainty in the data by assuming that (part of) the input is specified by a probability distribution. We consider the well-studied paradigm of stochastic recourse models, where the uncertainty evolves through a series of stages and one can take decisions in each stage in response to the new information learned. We obtain the first approximation algorithms for a variety of 2-stage and k-stage stochastic integer optimization problems where the underlying random data is given by a "black box" and no restrictions are placed on the costs of the two stages: one can merely sample data from this distribution, but no direct information about the distributions is given. Our results are based on two principal components. First, we show that for a broad class of 2-stage and k-stage linear programs, where k is not part of the input, given only a "black box" to draw independent samples from the distribution, one can, for any \epsilon>0, compute a solution of cost guaranteed to be within a (1+\epsilon) factor of the optimum, in time polynomial in 1/\epsilon, the size of the input, and a parameter \lambda that is the ratio of the cost of the same action in successive stages which is a lower bound on the sample complexity in the "black-box" model. This is based on reformulating the stochastic linear program, which has both an exponential number of variables and an exponential number of constraints, as a compact convex program, and adapting tools from convex optimization to solve the resulting program to near optimality. In doing so, a significant difficulty that we must overcome is that even evaluating the objective function of this convex program at a given point may be quite difficult and provably hard. To the best of our knowledge, this is the first such result for multi-stage stochastic programs. Second, we give a rounding approach for stochastic integer programs that shows that approximation algorithms for a deterministic analogue yields, with a small constant-factor loss, provably near-optimal solutions for the stochastic generalization. Thus we obtain approximation algorithms for several stochastic problems, including the stochastic versions of the set cover, vertex cover, facility location, multicut (on trees) and multicommodity flow problems.
Cite as

Chaitanya Swamy and David Shmoys. Approximation Algorithms for 2-stage and Multi-stage Stochastic Optimization. In Algorithms for Optimization with Incomplete Information. Dagstuhl Seminar Proceedings, Volume 5031, pp. 1-5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{swamy_et_al:DagSemProc.05031.5,
  author =	{Swamy, Chaitanya and Shmoys, David},
  title =	{{Approximation Algorithms for 2-stage and Multi-stage Stochastic Optimization}},
  booktitle =	{Algorithms for Optimization with Incomplete Information},
  pages =	{1--5},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{5031},
  editor =	{Susanne Albers and Rolf H. M\"{o}hring and Georg Ch. Pflug and R\"{u}diger Schultz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.05031.5},
  URN =		{urn:nbn:de:0030-drops-723},
  doi =		{10.4230/DagSemProc.05031.5},
  annote =	{Keywords: Algorithms, Approximation Algorithms, Optimization, Convex Optimization, Stochastic Optimization}
}
Document
DOI: 10.4230/DagSemRep.187
Combinatorial Approximation Algorithms (Dagstuhl Seminar 9734)

Authors: Yuval Rabani, David Shmoys, and Gerhard Woeginger

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Yuval Rabani, David Shmoys, and Gerhard Woeginger. Combinatorial Approximation Algorithms (Dagstuhl Seminar 9734). Dagstuhl Seminar Report 187, pp. 1-33, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (1998)

Copy BibTex To Clipboard

@TechReport{rabani_et_al:DagSemRep.187,
  author =	{Rabani, Yuval and Shmoys, David and Woeginger, Gerhard},
  title =	{{Combinatorial Approximation Algorithms (Dagstuhl Seminar 9734)}},
  pages =	{1--33},
  ISSN =	{1619-0203},
  year =	{1998},
  type = 	{Dagstuhl Seminar Report},
  number =	{187},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemRep.187},
  URN =		{urn:nbn:de:0030-drops-150746},
  doi =		{10.4230/DagSemRep.187},
}
  • Refine by Author
  • 5 Shmoys, David
  • 2 Megow, Nicole
  • 2 Svensson, Ola
  • 2 Swamy, Chaitanya
  • 1 Ferber, Aaron
  • Show More...

  • Refine by Classification
  • 2 Mathematics of computing → Combinatorial optimization
  • 2 Theory of computation → Approximation algorithms analysis
  • 1 Applied computing → Transportation
  • 1 Theory of computation → Online algorithms

  • Refine by Keyword
  • 4 approximation algorithms
  • 2 scheduling
  • 1 Algorithms
  • 1 Approximation Algorithms
  • 1 Convex Optimization
  • Show More...

  • Refine by Type
  • 7 document

  • Refine by Publication Year
  • 1 1998
  • 1 2005
  • 1 2007
  • 1 2017
  • 1 2020
  • Show More...

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