32 Search Results for "Pflug, Georg Ch."


Document
Minorant methods for stochastic global optimization

Authors: Vladimir Norkin and Boris. Onischenko

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


Abstract
We develop numerical methods for solution of stochastic global optimization problems: min$[F(x)=Ef(x,¦Ø)| xin X]$ and $min[F(x)=P{f(x, ¦Ø) ¡Ü0} | xin X]$, where x is a finite dimensional decision vector with possible values in the set X, ¦Ø is a random variable, $f(x,¦Ø)$ is a nonlinear function of variable x, E and P denote mathematical expectation and probability signs respectively. These methods are based on the concept of stochastic tangent minorant, which is a random function $¦Õ(x,y, ¦Ø)$ of two variables x and y with expected value $¦µ(x,y)=E ¦Õ(x,y, ¦Ø)$ satisfying conditions: (i) $¦µ(x,x)=F(x)$, (ii) $¦µ(x,y) ¡ÜF(x)$ for all x,y. Tangent minorant is a source of information on a function global behavior. We develop a calculus of (stochastic) tangent minorants. We develop a stochastic analogue of Pijavski¡¯s global optimization method and a branch and bound method with stochastic minorant bounds. Applications to optimal facility location and network reliability optimization are discussed.

Cite as

Vladimir Norkin and Boris. Onischenko. Minorant methods for stochastic global optimization. In Algorithms for Optimization with Incomplete Information. Dagstuhl Seminar Proceedings, Volume 5031, pp. 1-9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)


Copy BibTex To Clipboard

@InProceedings{norkin_et_al:DagSemProc.05031.14,
  author =	{Norkin, Vladimir and Onischenko, Boris.},
  title =	{{Minorant methods for stochastic global optimization}},
  booktitle =	{Algorithms for Optimization with Incomplete Information},
  pages =	{1--9},
  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.14},
  URN =		{urn:nbn:de:0030-drops-2115},
  doi =		{10.4230/DagSemProc.05031.14},
  annote =	{Keywords: Stochastic global optimization, stochastic tangent minorant, branch and bound method}
}
Document
05031 Abstracts Collection – Algorithms for Optimization with Incomplete Information

Authors: Susanne Albers, Rolf H. Möhring, Georg Ch. Pflug, and Rüdiger Schultz

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


Abstract
From 16.01.05 to 21.01.05, the Dagstuhl Seminar 05031 ``Algorithms for Optimization with Incomplete Information'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.

Cite as

Susanne Albers, Rolf H. Möhring, Georg Ch. Pflug, and Rüdiger Schultz. 05031 Abstracts Collection – Algorithms for Optimization with Incomplete Information. In Algorithms for Optimization with Incomplete Information. Dagstuhl Seminar Proceedings, Volume 5031, pp. 1-25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)


Copy BibTex To Clipboard

@InProceedings{albers_et_al:DagSemProc.05031.1,
  author =	{Albers, Susanne and M\"{o}hring, Rolf H. and Pflug, Georg Ch. and Schultz, R\"{u}diger},
  title =	{{05031 Abstracts Collection  – Algorithms for Optimization with Incomplete Information}},
  booktitle =	{Algorithms for Optimization with Incomplete Information},
  pages =	{1--25},
  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.1},
  URN =		{urn:nbn:de:0030-drops-1948},
  doi =		{10.4230/DagSemProc.05031.1},
  annote =	{Keywords: Online optimization , robust optimization , stochastic programming , stochastic scheduling}
}
Document
Getting rid of stochasticity: applicable sometimes

Authors: Han Hoogeveen and Marjan Van den Akker

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


Abstract
We consider the single-machine scheduling problem of minimizing the number of late jobs. This problem is well-studied and well-understood in case of deterministic processing times. We consider the problem with stochastic processing times, and we show that for a number of probability distributions the problem can be reformulated as a deterministic problem (and solved by the corresponding algorithm) when we use the concept of minimum success probabilities, which is, that we require that the probability that a job complete on time is `big enough'. We further show that we can extend our approach to the case of machines with stochastic output.

Cite as

Han Hoogeveen and Marjan Van den Akker. Getting rid of stochasticity: applicable sometimes. In Algorithms for Optimization with Incomplete Information. Dagstuhl Seminar Proceedings, Volume 5031, pp. 1-4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)


Copy BibTex To Clipboard

@InProceedings{hoogeveen_et_al:DagSemProc.05031.12,
  author =	{Hoogeveen, Han and Van den Akker, Marjan},
  title =	{{Getting rid of stochasticity: applicable sometimes}},
  booktitle =	{Algorithms for Optimization with Incomplete Information},
  pages =	{1--4},
  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.12},
  URN =		{urn:nbn:de:0030-drops-1924},
  doi =		{10.4230/DagSemProc.05031.12},
  annote =	{Keywords: Scheduling , sequencing , single machine , number of late jobs , stochastic processing times , minimum success probability , dynamic programming unreliable machines}
}
Document
New Old Algorithms for Stochastic Scheduling

Authors: Andreas S. Schulz

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


Abstract
We consider the stochastic identical parallel machine scheduling problem and its online extension, when the objective is to minimize the expected total weighted completion time of a set of jobs that are released over time. We give randomized as well as deterministic online and offline algorithms that have the best known performance guarantees in either setting, online or offline and deterministic or randomized. Our analysis is based on a novel linear programming relaxation for stochastic scheduling problems that can be solved online.

Cite as

Andreas S. Schulz. New Old Algorithms for Stochastic Scheduling. In Algorithms for Optimization with Incomplete Information. Dagstuhl Seminar Proceedings, Volume 5031, pp. 1-9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)


Copy BibTex To Clipboard

@InProceedings{schulz:DagSemProc.05031.18,
  author =	{Schulz, Andreas S.},
  title =	{{New Old Algorithms for Stochastic Scheduling}},
  booktitle =	{Algorithms for Optimization with Incomplete Information},
  pages =	{1--9},
  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.18},
  URN =		{urn:nbn:de:0030-drops-1931},
  doi =		{10.4230/DagSemProc.05031.18},
  annote =	{Keywords: stochastic scheduling , online algorithms , competitive analysis , approximation algorithms , linear programming relaxations}
}
Document
Searching with an Autonomous Robot

Authors: Sándor Fekete, Rolf Klein, and Andreas Nüchter

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


Abstract
We discuss online strategies for visibility-based searching for an object hidden behind a corner, using Kurt3D, a real autonomous mobile robot. This task is closely related to a number of well-studied problems. Our robot uses a three-dimensional laser scanner in a stop, scan, plan, go fashion for building a virtual three-dimensional environment. Besides planning trajectories and avoiding obstacles, Kurt3D is capable of identifying objects like a chair. We derive a practically useful and asymptotically optimal strategy that guarantees a competitive ratio of 2, which differs remarkably from the well-studied scenario without the need of stopping for surveying the environment. Our strategy is used by Kurt3D, documented in a separate video.

Cite as

Sándor Fekete, Rolf Klein, and Andreas Nüchter. Searching with an Autonomous Robot. In Algorithms for Optimization with Incomplete Information. Dagstuhl Seminar Proceedings, Volume 5031, pp. 1-2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)


Copy BibTex To Clipboard

@InProceedings{fekete_et_al:DagSemProc.05031.27,
  author =	{Fekete, S\'{a}ndor and Klein, Rolf and N\"{u}chter, Andreas},
  title =	{{Searching with an Autonomous Robot}},
  booktitle =	{Algorithms for Optimization with Incomplete Information},
  pages =	{1--2},
  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.27},
  URN =		{urn:nbn:de:0030-drops-1919},
  doi =		{10.4230/DagSemProc.05031.27},
  annote =	{Keywords: Searching , visibility problems , watchman problems , online searching , competitive strategies , autonomous mobile robots three-dimensional laser scanning , Kurt3D}
}
Document
Facility location with uncertain demand and economies of scale

Authors: Peter Schütz, Leen Stougie, and Asgeir Tomasgard

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


Abstract
This paper adresses facility location under uncertain demand. The problem is to determine the optimal location of facilities and allocation of uncertain customer demand to these facilities. The costs of operating the facilities are subject to economies of scale. The objective is to minimize the total expected costs. These costs can be split into two parts: firstly the costs of investing in a facility as well as maintaining and operating it with strictly diminishing average costs, and secondly linear transportation cost. We formulate the problem as a two-stage stochastic programming model and present a solution method based on Lagrangian Relaxation. We also show some computional results based on data from the Norwegian meat industry regarding the location of slaughterhouses.

Cite as

Peter Schütz, Leen Stougie, and Asgeir Tomasgard. Facility location with uncertain demand and economies of scale. In Algorithms for Optimization with Incomplete Information. Dagstuhl Seminar Proceedings, Volume 5031, pp. 1-11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)


Copy BibTex To Clipboard

@InProceedings{schutz_et_al:DagSemProc.05031.11,
  author =	{Sch\"{u}tz, Peter and Stougie, Leen and Tomasgard, Asgeir},
  title =	{{Facility location with uncertain demand and economies of scale}},
  booktitle =	{Algorithms for Optimization with Incomplete Information},
  pages =	{1--11},
  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.11},
  URN =		{urn:nbn:de:0030-drops-1114},
  doi =		{10.4230/DagSemProc.05031.11},
  annote =	{Keywords: facility location , stochastic , economies of scale}
}
Document
Models and Algorithms for Stochastic Online Scheduling

Authors: Nicole Megow, Marc Uetz, and Tjark Vredeveld

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


Abstract
We introduce a model for non-preemptive scheduling under uncertainty. In this model, we combine the main characteristics of online and stochastic scheduling in a simple and natural way. Job processing times are assumed to be stochastic, but in contrast to the classical stochastic scheduling models, we assume that jobs arrive online over time, and there is no knowledge about the jobs that will arrive in the future. The model incorporates both, stochastic scheduling and online scheduling as a special case. The particular setting we analyze is parallel machine scheduling, with the objective to minimize the total weighted completion times of jobs. We propose simple, combinatorial online scheduling policies for that model, and derive performance guarantees that match the currently best known performance guarantees for stochastic parallel machine scheduling. For processing times that follow NBUE distributions, we improve upon previously best known performance bounds, even though we consider a more general setting.

Cite as

Nicole Megow, Marc Uetz, and Tjark Vredeveld. Models and Algorithms for Stochastic Online Scheduling. In Algorithms for Optimization with Incomplete Information. Dagstuhl Seminar Proceedings, Volume 5031, pp. 1-4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)


Copy BibTex To Clipboard

@InProceedings{megow_et_al:DagSemProc.05031.15,
  author =	{Megow, Nicole and Uetz, Marc and Vredeveld, Tjark},
  title =	{{Models and Algorithms for Stochastic Online Scheduling}},
  booktitle =	{Algorithms for Optimization with Incomplete Information},
  pages =	{1--4},
  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.15},
  URN =		{urn:nbn:de:0030-drops-1106},
  doi =		{10.4230/DagSemProc.05031.15},
  annote =	{Keywords: stochastic scheduling , online optimization , weighted completion time}
}
Document
Note on Negative Probabilities and Observable Processes

Authors: Ulrich Faigle and Alexander Schoenhuth

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


Abstract
A mathematical framework for observable processes is introduced via the model of systems whose states may be time dependent and described by possibly "negative probabilities". The model generalizes and includes the linearly dependent models or observable operator models for classical discrete stochastic processes. Within this model a general convergence result for finite-dimensional processes, which generalize finite state (hidden) Markov models, is derived. On the philosophical side, the model furthermore offers an explanation for Bell's inequality in quantum mechanics.

Cite as

Ulrich Faigle and Alexander Schoenhuth. Note on Negative Probabilities and Observable Processes. In Algorithms for Optimization with Incomplete Information. Dagstuhl Seminar Proceedings, Volume 5031, pp. 1-14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)


Copy BibTex To Clipboard

@InProceedings{faigle_et_al:DagSemProc.05031.19,
  author =	{Faigle, Ulrich and Schoenhuth, Alexander},
  title =	{{Note on Negative Probabilities and Observable Processes}},
  booktitle =	{Algorithms for Optimization with Incomplete Information},
  pages =	{1--14},
  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.19},
  URN =		{urn:nbn:de:0030-drops-1087},
  doi =		{10.4230/DagSemProc.05031.19},
  annote =	{Keywords: Negative Probability , Observable Process , Markov Chain , Stochastic Process , Bell\~{A}¢\^{a}‚¬\^{a}„¢s Inequality , HHM , LDP , OOM}
}
Document
Properties and Calculation of Singular Normal Distributions

Authors: René Henrion and Tamas Szantai

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


Abstract
The need for calculating and characterizing singular normal distributions arises in a natural way when considering chance constraints of the type P(Az <= b(x) >= p, where A is a rectangular matrix having more rows than columns, b is some function and z is a random vector having some nondegenerate multivariate normal distribution. Such situation is typical, for instance, in stochastic networks, where a comparatively small random vector may induce a possibly large number of linear inequality constraints. Passing to the transformed random variable q:=Az, the constraint can be equivalently rewritten as F(b(x))>= p, where F is the distribution function of q. In contrast to the original random vector z, the transformed vector q has a singular normal distribution. The talk demonstrates how to get back from here to (a sum of) regular normal distributions under a full rank regularity condition. This allows for an efficient calculation of singular normal distributions and provides a numerical method which outperforms competing procedures in moderate dimensions. Computational results for test examples are provided for the sake of comparison. In general, if the mentioned regularity condition is violated, then the singular normal distribution function F may even lack continuity. The talk provides an equivalent criterion for Lipschitz continuity of F and characterizes differentiability and subdifferentiability of F.

Cite as

René Henrion and Tamas Szantai. Properties and Calculation of Singular Normal Distributions. In Algorithms for Optimization with Incomplete Information. Dagstuhl Seminar Proceedings, Volume 5031, pp. 1-2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)


Copy BibTex To Clipboard

@InProceedings{henrion_et_al:DagSemProc.05031.24,
  author =	{Henrion, Ren\'{e} and Szantai, Tamas},
  title =	{{Properties and Calculation of Singular Normal Distributions}},
  booktitle =	{Algorithms for Optimization with Incomplete Information},
  pages =	{1--2},
  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.24},
  URN =		{urn:nbn:de:0030-drops-1097},
  doi =		{10.4230/DagSemProc.05031.24},
  annote =	{Keywords: singular normal distribution , chance constraints , normal probability of polyhedra}
}
Document
An improved algorithm for CIOQ switches

Authors: Yossi Azar and Yossi Richter

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


Abstract
The problem of maximizing the weighted throughput in various switching settings has been intensively studied recently through competitive analysis. To date, the most general model that has been investigated is the standard CIOQ (Combined Input and Output Queued) switch architecture with internal fabric speedup $S \geq 1$. CIOQ switches, that comprise the backbone of packet routing networks, are $N \times N$ switches controlled by a switching policy that incorporates two components: Admission control and scheduling. An admission control strategy is essential to determine the packets stored in the FIFO queues in input and output ports, while the scheduling policy conducts the transfer of packets through the internal fabric, from input ports to output ports. The online problem of maximizing the total weighted throughput of CIOQ switches was recently investigated by Kesselman and Ros\'{e}n [SPAA03]. They presented two different online algorithms for the general problem that achieve non-constant competitive ratios (linear in either the speedup or the number of distinct values, or logarithmic in the value range). We introduce the first constant-competitive algorithm for the general case of the problem, with arbitrary speedup and packet values. Specifically, our algorithm is $8$-competitive, and is also simple and easy to implement.

Cite as

Yossi Azar and Yossi Richter. An improved algorithm for CIOQ switches. In Algorithms for Optimization with Incomplete Information. Dagstuhl Seminar Proceedings, Volume 5031, pp. 1-4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)


Copy BibTex To Clipboard

@InProceedings{azar_et_al:DagSemProc.05031.4,
  author =	{Azar, Yossi and Richter, Yossi},
  title =	{{An improved algorithm for CIOQ switches}},
  booktitle =	{Algorithms for Optimization with Incomplete Information},
  pages =	{1--4},
  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.4},
  URN =		{urn:nbn:de:0030-drops-670},
  doi =		{10.4230/DagSemProc.05031.4},
  annote =	{Keywords: On-line algorithms, Competitive ratio, CIOQ Switch, Packet Switching, Buffer Management, Quality of Service.}
}
Document
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
Assessing Solution Quality in Stochastic Programs

Authors: David P. Morton and Guzin Bayraksan

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


Abstract
Assessing whether a solution is of high quality (optimal or near optimal) is a fundamental question in optimization. We develop Monte Carlo sampling-based procedures for assessing solution quality in stochastic programs. Quality is defined via the optimality gap and our procedures' output is a confidence interval on this gap. We review a multiple-replications procedure and then present a result that justifies a computationally simplified single-replication procedure. Even though the single replication procedure is computationally significantly less demanding, the resulting confidence interval may have low coverage for small sample sizes on some problems. We provide variants of this procedure and provide preliminary guidelines for selecting a candidate solution. Both are designed to improve the basic procedure's performance.

Cite as

David P. Morton and Guzin Bayraksan. Assessing Solution Quality in Stochastic Programs. In Algorithms for Optimization with Incomplete Information. Dagstuhl Seminar Proceedings, Volume 5031, pp. 1-3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)


Copy BibTex To Clipboard

@InProceedings{morton_et_al:DagSemProc.05031.6,
  author =	{Morton, David P. and Bayraksan, Guzin},
  title =	{{Assessing Solution Quality in Stochastic Programs}},
  booktitle =	{Algorithms for Optimization with Incomplete Information},
  pages =	{1--3},
  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.6},
  URN =		{urn:nbn:de:0030-drops-638},
  doi =		{10.4230/DagSemProc.05031.6},
  annote =	{Keywords: stochastic programming , Monte Carlo simulation}
}
Document
Average Case and Smoothed Competitive Analysis of the Multi-Level Feedback Algorithm

Authors: Luca Becchetti, Stefano Leonardi, Alberto Marchetti-Spaccamela, Guidouca Schaefer, and Tjark Vredeveld

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


Abstract
In this paper we introduce the notion of smoothed competitive analysis of online algorithms. Smoothed analysis has been proposed by Spielman and Teng to explain the behaviour of algorithms that work well in practice while performing very poorly from a worst case analysis point of view. We apply this notion to analyze the Multi-Level Feedback (MLF) algorithm to minimize the total flow time on a sequence of jobs released over time when the processing time of a job is only known at time of completion. The initial processing times are integers in the range $[1,2^K]$. We use a partial bit randomization model, i.e., the initial processing times are smoothed by changing the $k$ least significant bits under a quite general class of probability distributions. We show that MLF admits a smoothed competitive ratio of $O((2^k/\psigma)^3 + (2^k/\psigma)^2 2^{K-k}})$, where $\sigma$ denotes the standard deviation of the distribution. In particular, we obtain a competitive ratio of $O(2^{K-k})$ if $\sigma = \Theta(2^k)$. We also prove an $\Omega(2^{K-k})$ lower bound for any deterministic algorithm that is run on processing times smoothed according to the partial bit randomization model. For various other smoothing models, including the additive symmetric smoothing one, which is a variant of the model used by Spielman and Teng, we give a higher lower bound of $\Omega(2^K)$. A direct consequence of our result is also the first average case analysis of MLF. We show a constant expected ratio of the total flow time of MLF to the optimum under several distributions including the uniform one.

Cite as

Luca Becchetti, Stefano Leonardi, Alberto Marchetti-Spaccamela, Guidouca Schaefer, and Tjark Vredeveld. Average Case and Smoothed Competitive Analysis of the Multi-Level Feedback Algorithm. In Algorithms for Optimization with Incomplete Information. Dagstuhl Seminar Proceedings, Volume 5031, pp. 5-28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)


Copy BibTex To Clipboard

@InProceedings{becchetti_et_al:DagSemProc.05031.7,
  author =	{Becchetti, Luca and Leonardi, Stefano and Marchetti-Spaccamela, Alberto and Schaefer, Guidouca and Vredeveld, Tjark},
  title =	{{Average Case and Smoothed Competitive Analysis of the Multi-Level Feedback Algorithm}},
  booktitle =	{Algorithms for Optimization with Incomplete Information},
  pages =	{5--28},
  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.7},
  URN =		{urn:nbn:de:0030-drops-752},
  doi =		{10.4230/DagSemProc.05031.7},
  annote =	{Keywords: Competitive analysis , average case analysis , smoothed analysis , scheduling}
}
Document
Average-Case Competitive Analyses for Ski-Rental Problems

Authors: Hiroshi Fujiwara and Kazuo Iwama

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


Abstract
Let $s$ be the ratio of the cost for purchasing skis over the cost for renting them. Then the famous result for the ski-rental problem shows that skiers should buy their skis after renting them $(s-1)$ times, which gives us an optimal competitive ratio of $2-\frac{1}{s}$. In practice, however, it appears that many skiers buy their skis before this optimal point of time and also many skiers keep renting them forever. In this paper we show that these behaviors of skiers are quite reasonable by using an {\em average-case competitive ratio}. For an exponential input distribution $f(t) = \lambda e^{-\lambda t}$, optimal strategies are (i) if $\frac{1}{\lambda} \leq s$, then skiers should rent their skis forever and (ii) otherwise should purchase them after renting approximately $s^2\lambda \;\;(

Cite as

Hiroshi Fujiwara and Kazuo Iwama. Average-Case Competitive Analyses for Ski-Rental Problems. In Algorithms for Optimization with Incomplete Information. Dagstuhl Seminar Proceedings, Volume 5031, pp. 1-3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)


Copy BibTex To Clipboard

@InProceedings{fujiwara_et_al:DagSemProc.05031.8,
  author =	{Fujiwara, Hiroshi and Iwama, Kazuo},
  title =	{{Average-Case Competitive Analyses for Ski-Rental Problems}},
  booktitle =	{Algorithms for Optimization with Incomplete Information},
  pages =	{1--3},
  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.8},
  URN =		{urn:nbn:de:0030-drops-606},
  doi =		{10.4230/DagSemProc.05031.8},
  annote =	{Keywords: online algorithm , competitive analysis}
}
Document
Deferment Control for Reoptimization – How to Find Fair Reoptimized Dispatches

Authors: Jörg Rambau

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


Abstract
The german automobile association ADAC maintains a fleet of 1700 vehicles and has agreements with around 5000 service contractors. With these ressources, they help people whose cars have broken down on the road. Those people can call an ADAC help center, and within 10 seconds, an assignment of a service ressource to their request is made. At the same time, for all service vehicles, tours through the assigned requests have to be planned so as to minimize a certain (complicated) cost function for this so-called dispatch. No usefule knowledge about future requests is available at the time being. Therefore, the current policy of the automated system, developed in joint work with Sven O. Krumke, is to reoptimize the whole dispatch upon the occurrence of each relevant event, like the arrival of a new request. A similar online-optimization problem appears in the pallet elevator group control in a large distribution center of Herlitz PBS AG in Falkensee near Berlin. The problem with reoptimization policies in general is that, depending on the reoptimization objective, an arbitrarily large deferment of individual requests can be observed. In a way, individual requests are sacrificed in favor of a good performance according to the reoptimization objective. Nevertheless, w.r.t. the reoptimization objective, the reoptimization policies in the long run usually perform much better than the currently known policies that can not cause infinite deferment. Therefore, the goal is to modify reoptimization policies so as to prevent deferment. Sometimes deferment can be almost eliminated by enhancing the reoptimization objective with some terms that penalize waiting, but service in a fixed time can still not be guaranteed, and this kind of objective function engineering is a very time consuming tuning issue, interfering with the orgininal management objective. In this talk, the new policy of flow and makespan constrained reoptimization with reoptimization admission control is introduced. The main result is that, under d-reasonable load, for any reoptimization model, this policy yields a maximal flow time that is bounded by a constant 2d, depending only on the system load parameter d, not on the instance. In simulation experiments for the elevator group control problem we still obtain a very satisfactory average performance w.r.t. the reoptimization objective.

Cite as

Jörg Rambau. Deferment Control for Reoptimization – How to Find Fair Reoptimized Dispatches. In Algorithms for Optimization with Incomplete Information. Dagstuhl Seminar Proceedings, Volume 5031, pp. 1-4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)


Copy BibTex To Clipboard

@InProceedings{rambau:DagSemProc.05031.9,
  author =	{Rambau, J\"{o}rg},
  title =	{{Deferment Control for Reoptimization – How to Find Fair Reoptimized Dispatches}},
  booktitle =	{Algorithms for Optimization with Incomplete Information},
  pages =	{1--4},
  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.9},
  URN =		{urn:nbn:de:0030-drops-668},
  doi =		{10.4230/DagSemProc.05031.9},
  annote =	{Keywords: online optimization , dynamic vehicle dispatching , reoptimization , integer linear program , dynamic column generation , infinite deferment ,}
}
  • Refine by Author
  • 2 Albers, Susanne
  • 2 Epstein, Leah
  • 2 Möhring, Rolf H.
  • 2 Pflug, Georg Ch.
  • 2 Schultz, Rüdiger
  • Show More...

  • Refine by Classification

  • Refine by Keyword
  • 4 stochastic scheduling
  • 3 online algorithm
  • 3 scheduling
  • 3 stochastic programming
  • 2 Stochastic Programming
  • Show More...

  • Refine by Type
  • 32 document

  • Refine by Publication Year
  • 32 2005

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