Volume

Dagstuhl Seminar Proceedings, Volume 5031

Publication Details

  • published at: 2005-05-27
  • Publisher: Schloss Dagstuhl – Leibniz-Zentrum für Informatik

Access Numbers

Documents

No documents found matching your filter selection.
Document
DOI: 10.4230/DagSemProc.05031.1
05031 Abstracts Collection – Algorithms for Optimization with Incomplete Information

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

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.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
DOI: 10.4230/DagSemProc.05031.2
05031 Summary – Algorithms for Optimization with Incomplete Information

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

Abstract
This paper summarizes the objectives and structure of a seminar with the same title, held from January 16th to 21th 2005 at Schloss Dagstuhl, Germany
Cite as

Susanne Albers, Rolf H. Möhring, Georg Ch. Pflug, and Rüdiger Schultz. 05031 Summary – Algorithms for Optimization with Incomplete Information. 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{albers_et_al:DagSemProc.05031.2,
  author =	{Albers, Susanne and M\"{o}hring, Rolf H. and Pflug, Georg Ch. and Schultz, R\"{u}diger},
  title =	{{05031 Summary – Algorithms for Optimization with Incomplete Information}},
  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.dagstuhl.de/entities/document/10.4230/DagSemProc.05031.2},
  URN =		{urn:nbn:de:0030-drops-1138},
  doi =		{10.4230/DagSemProc.05031.2},
  annote =	{Keywords: Online Optimization , Robust Optimization , Stochastic Programming , Stochastic Scheduling}
}
Document
DOI: 10.4230/DagSemProc.05031.3
An adaptive trust-region approach for nonlinear stochastic optimisation with an application in discrete choice theory

Authors: Fabian Bastin

Abstract
We consider stochastic nonlinear programs, restricting ourself to differentiable, but possibly non-convex, problems. The non-convexity leads us to consider non-linear approaches, designed to find second-order critical solutions. We focus here on the use of trust-region approaches when solving a sample average approximation, and adapt the technique to only use sub-samples when possible, adjusting the sample size at each iteration. We show that under reasonable assumptions, we solve the original SAA problem. We also consider an extension to the estimation of mixed logit models, that are popular in discrete choice theory when the population heterogeneity is taken into account. We present numerical experimentations underlining the practical interest of the method. We finally examine some avenues and preliminary experimentations for future research.
Cite as

Fabian Bastin. An adaptive trust-region approach for nonlinear stochastic optimisation with an application in discrete choice theory. 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{bastin:DagSemProc.05031.3,
  author =	{Bastin, Fabian},
  title =	{{An adaptive trust-region approach for nonlinear stochastic optimisation with an application in discrete choice theory}},
  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.dagstuhl.de/entities/document/10.4230/DagSemProc.05031.3},
  URN =		{urn:nbn:de:0030-drops-559},
  doi =		{10.4230/DagSemProc.05031.3},
  annote =	{Keywords: Nonlinear Stochastic Programming , Monte-Carlo , Mixed Logit , Discrete Choice , Trust-Region}
}
Document
DOI: 10.4230/DagSemProc.05031.4
An improved algorithm for CIOQ switches

Authors: Yossi Azar and Yossi Richter

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.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
DOI: 10.4230/DagSemProc.05031.5
Approximation Algorithms for 2-stage and Multi-stage Stochastic Optimization

Authors: Chaitanya Swamy and David Shmoys

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.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/DagSemProc.05031.6
Assessing Solution Quality in Stochastic Programs

Authors: David P. Morton and Guzin Bayraksan

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.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
DOI: 10.4230/DagSemProc.05031.7
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

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.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
DOI: 10.4230/DagSemProc.05031.8
Average-Case Competitive Analyses for Ski-Rental Problems

Authors: Hiroshi Fujiwara and Kazuo Iwama

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.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
DOI: 10.4230/DagSemProc.05031.9
Deferment Control for Reoptimization – How to Find Fair Reoptimized Dispatches

Authors: Jörg Rambau

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.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 ,}
}
Document
DOI: 10.4230/DagSemProc.05031.10
Disruption Management and Planning with Uncertainties in Aircraft Planning

Authors: Jan Ehrhoff, Sven Grothklags, and Ulf Lorenz

Abstract
An important insufficiency of modern industrial plans still is their lack of robustness. Disruptions prevent companies from operating as planned before and induce high costs for trouble shooting. The main reason for the severe impact of disruptions stems from the fact that planners do traditionally consider deterministic input data to be available at planning time. In practice, there are often only distributions over the possible input data available. The Repair Game is a formalization of a planning task, which brings two branches of computer science --- game tree search and logistic planning optimization with OR tools --- together. Playing it performs disruption management and generates robust plans with the help of game tree search. Our method significantly outperformed the traditional one by means of simulations.
Cite as

Jan Ehrhoff, Sven Grothklags, and Ulf Lorenz. Disruption Management and Planning with Uncertainties in Aircraft Planning. 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{ehrhoff_et_al:DagSemProc.05031.10,
  author =	{Ehrhoff, Jan and Grothklags, Sven and Lorenz, Ulf},
  title =	{{Disruption Management and Planning with Uncertainties in Aircraft Planning}},
  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.dagstuhl.de/entities/document/10.4230/DagSemProc.05031.10},
  URN =		{urn:nbn:de:0030-drops-620},
  doi =		{10.4230/DagSemProc.05031.10},
  annote =	{Keywords: uncertainty, planning, game playing, aviation application}
}
Document
DOI: 10.4230/DagSemProc.05031.11
Facility location with uncertain demand and economies of scale

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

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.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
DOI: 10.4230/DagSemProc.05031.12
Getting rid of stochasticity: applicable sometimes

Authors: Han Hoogeveen and Marjan Van den Akker

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.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
DOI: 10.4230/DagSemProc.05031.13
Marginal productivity index policies for scheduling restless bandits with switching penalties

Authors: José Niño-Mora

Abstract
We address the problem of designing a tractable, well-grounded policy for the dynamic allocation of effort to a collection of restless bandit projects, i.e. binary-action (active/passive) Markov decision processes, in which sequence-independent switching penalties (costs or delays) are incurred when switching from one project to another. We deploy the framework of partial conservation laws, introduced by Ni�±o-Mora (2001, 2002), to establish the existence of and calculate a marginal productivity index (MPI), under certain conditions. The MPI, which extends earlier indices proposed by Gittins (1979) and Whittle (1988), yields a corresponding MPI policy, which prescribes to dynamically engage the project with larger index.
Cite as

José Niño-Mora. Marginal productivity index policies for scheduling restless bandits with switching penalties. In Algorithms for Optimization with Incomplete Information. Dagstuhl Seminar Proceedings, Volume 5031, pp. 1-6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{ninomora:DagSemProc.05031.13,
  author =	{Ni\~{n}o-Mora, Jos\'{e}},
  title =	{{Marginal productivity index policies for scheduling restless bandits with switching penalties}},
  booktitle =	{Algorithms for Optimization with Incomplete Information},
  pages =	{1--6},
  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.dagstuhl.de/entities/document/10.4230/DagSemProc.05031.13},
  URN =		{urn:nbn:de:0030-drops-644},
  doi =		{10.4230/DagSemProc.05031.13},
  annote =	{Keywords: stochastic scheduling , restless bandits , index policies , switching penalties}
}
Document
DOI: 10.4230/DagSemProc.05031.14
Minorant methods for stochastic global optimization

Authors: Vladimir Norkin and Boris. Onischenko

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.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
DOI: 10.4230/DagSemProc.05031.15
Models and Algorithms for Stochastic Online Scheduling

Authors: Nicole Megow, Marc Uetz, and Tjark Vredeveld

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.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
DOI: 10.4230/DagSemProc.05031.16
Modification of Recourse Data for Mixed-Integer Recourse Models

Authors: Maarten H. van der Vlerk

Abstract
We consider modification of the recourse data, consisting of the second-stage parameters and the underlying distribution, as an approximation technique for solving two-stage recourse problems. This approach is applied to several specific classes of mixed-integer recourse problems; in each case, the resulting recourse problem is much easier to solve.
Cite as

Maarten H. van der Vlerk. Modification of Recourse Data for Mixed-Integer Recourse Models. 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{vlerk:DagSemProc.05031.16,
  author =	{Vlerk, Maarten H. van der},
  title =	{{Modification of Recourse Data for Mixed-Integer Recourse Models}},
  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.dagstuhl.de/entities/document/10.4230/DagSemProc.05031.16},
  URN =		{urn:nbn:de:0030-drops-738},
  doi =		{10.4230/DagSemProc.05031.16},
  annote =	{Keywords: stochastic programming, integer programming, approximation}
}
Document
DOI: 10.4230/DagSemProc.05031.17
Network Discovery and Verification

Authors: Zuzana Beerliova, Felix Eberhard, Thomas Erlebach, Alexander Hall, Michael Hoffmann, Matus Mihalak, and L. Shankar Ram

Abstract
Consider the problem of discovering (or verifying) the edges and non-edges of a network, modelled as a connected undirected graph, using a minimum number of queries. A query at a vertex v discovers (or verifies) all edges and non-edges whose endpoints have different distance from v. In the network discovery problem, the edges and non-edges are initially unknown, and the algorithm must select the next query based only on the results of previous queries. We study the problem using competitive analysis and give a randomized on-line algorithm with competitive ratio O(sqrt(n*log n)) for graphs with n vertices. We also show that no deterministic algorithm can have competitive ratio better than 3. In the network verification problem, the graph is known in advance and the goal is to compute a minimum number of queries that verify all edges and non-edges. This problem has previously been studied as the problem of placing landmarks in graphs or determining the metric dimension of a graph. We show that there is no approximation algorithm for this problem with ratio o(log n) unless P=NP. Furthermore, we prove that the optimal number of queries for d-dimensional hypercubes is Theta(d/log d).
Cite as

Zuzana Beerliova, Felix Eberhard, Thomas Erlebach, Alexander Hall, Michael Hoffmann, Matus Mihalak, and L. Shankar Ram. Network Discovery and Verification. 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{beerliova_et_al:DagSemProc.05031.17,
  author =	{Beerliova, Zuzana and Eberhard, Felix and Erlebach, Thomas and Hall, Alexander and Hoffmann, Michael and Mihalak, Matus and Ram, L. Shankar},
  title =	{{Network Discovery and Verification}},
  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.dagstuhl.de/entities/document/10.4230/DagSemProc.05031.17},
  URN =		{urn:nbn:de:0030-drops-594},
  doi =		{10.4230/DagSemProc.05031.17},
  annote =	{Keywords: on-line algorithms , set cover , landmarks , metric dimension}
}
Document
DOI: 10.4230/DagSemProc.05031.18
New Old Algorithms for Stochastic Scheduling

Authors: Andreas S. Schulz

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.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
DOI: 10.4230/DagSemProc.05031.19
Note on Negative Probabilities and Observable Processes

Authors: Ulrich Faigle and Alexander Schoenhuth

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.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
DOI: 10.4230/DagSemProc.05031.20
Online Scheduling

Authors: Jiri Sgall

Abstract
We survey some recent results on scheduling unit jobs. The emphasis of the talk is both on presenting some basic techniques and providing an overview of the current state of the art. The techniques presented cover charging schemes, potential function arguments, and lower bounds based on Yao's principle. The studied problem is equivalent to the following buffer management problem: packets with specified weights and deadlines arrive at a network switch and need to be forwarded so that the total weight of forwarded packets is maximized. A packet not forwarded before its deadline brings no profit. The presented algorithms improve upon 2-competitive greedy algorithm, the competitive ratio is 1.939 for deterministic and 1.582 for randomized algorithms.
Cite as

Jiri Sgall. Online Scheduling. 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{sgall:DagSemProc.05031.20,
  author =	{Sgall, Jiri},
  title =	{{Online Scheduling}},
  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.dagstuhl.de/entities/document/10.4230/DagSemProc.05031.20},
  URN =		{urn:nbn:de:0030-drops-695},
  doi =		{10.4230/DagSemProc.05031.20},
  annote =	{Keywords: online algorithms , scheduling}
}
Document
DOI: 10.4230/DagSemProc.05031.21
Online scheduling of splittable tasks

Authors: Leah Epstein and Rob van Stee

Abstract
We consider online scheduling of splittable tasks on parallel machines. In our model, each task can be split into a limited number of parts, that can then be scheduled independently. We consider both the case where the machines are identical and the case where some subset of the machines have a (fixed) higher speed than the others. We design a class of algorithms which allows us to give tight bounds for a large class of cases where tasks may be split into relatively many parts. For identical machines we also improve upon the natural greedy algorithm in other classes of cases.
Cite as

Leah Epstein and Rob van Stee. Online scheduling of splittable tasks. 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{epstein_et_al:DagSemProc.05031.21,
  author =	{Epstein, Leah and Stee, Rob van},
  title =	{{Online scheduling of splittable tasks}},
  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.dagstuhl.de/entities/document/10.4230/DagSemProc.05031.21},
  URN =		{urn:nbn:de:0030-drops-743},
  doi =		{10.4230/DagSemProc.05031.21},
  annote =	{Keywords: online scheduling , splittable tasks , parallel machines , greedy algorithm}
}
Document
DOI: 10.4230/DagSemProc.05031.22
Online Scheduling with Bounded Migration

Authors: Peter Sanders, Naveen Sivadasan, and Martin Skutella

Abstract
Consider the classical online scheduling problem where jobs that arrive one by one are assigned to identical parallel machines with the objective of minimizing the makespan. We generalize this problem by allowing the current assignment to be changed whenever a new job arrives, subject to the constraint that the total size of moved jobs is bounded by~$\beta$ times the size of the arriving job. Our main result is a linear time `online approximation scheme', that is, a family of online algorithms with competitive ratio~$1+\epsilon$ and constant migration factor~$\beta(\epsilon)$, for any fixed~$\epsilon>0$. This result is of particular importance if considered in the context of sensitivity analysis: While a newly arriving job may force a complete change of the entire structure of an optimal schedule, only very limited `local' changes suffice to preserve near-optimal solutions. We believe that this concept will find wide application in its own right. We also present simple deterministic online algorithms with migration factors~$\beta=2$ and~$\beta=4/3$, respectively. Their competitive ratio~$3/2$ beats the lower bound on the performance of any online algorithm in the classical setting without migration. We also present improved algorithms and similar results for closely related problems. In particular, there is a short discussion of corresponding results for the objective to maximize the minimum load of a machine. The latter problem has an application for configuring storage servers that was the original motivation for this work.
Cite as

Peter Sanders, Naveen Sivadasan, and Martin Skutella. Online Scheduling with Bounded Migration. 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{sanders_et_al:DagSemProc.05031.22,
  author =	{Sanders, Peter and Sivadasan, Naveen and Skutella, Martin},
  title =	{{Online Scheduling with Bounded Migration}},
  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.dagstuhl.de/entities/document/10.4230/DagSemProc.05031.22},
  URN =		{urn:nbn:de:0030-drops-707},
  doi =		{10.4230/DagSemProc.05031.22},
  annote =	{Keywords: scheduling, sensitivity analysis, online algorithm}
}
Document
DOI: 10.4230/DagSemProc.05031.23
Polyhedral Risk Measures and Lagrangian Relaxation in Electricity Portfolio Optimization

Authors: Andreas Eichhorn, Werner Römisch, and Isabel Wegner

Abstract
We present a multistage stochastic programming model for mean-risk optimization of electricity portfolios containing physical components and energy derivative products. Stochasticity enters the model via the uncertain (time-dependent) prices and electricity demand. The objective is to maximize the expected overall revenue and, simultaneously, to minimize a multiperiod risk measure, i.e., a risk measure that takes into account the intermediate time cash values. We compare the effect of different multiperiod risk measures taken from the class of polyhedral risk measures which was suggested in our earlier work. Furthermore, we discuss how such a mean-risk optimization problem can be solved by dual decomposition techniques (Lagrangian relaxation).
Cite as

Andreas Eichhorn, Werner Römisch, and Isabel Wegner. Polyhedral Risk Measures and Lagrangian Relaxation in Electricity Portfolio Optimization. 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{eichhorn_et_al:DagSemProc.05031.23,
  author =	{Eichhorn, Andreas and R\"{o}misch, Werner and Wegner, Isabel},
  title =	{{Polyhedral Risk Measures and Lagrangian Relaxation in Electricity Portfolio Optimization}},
  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.dagstuhl.de/entities/document/10.4230/DagSemProc.05031.23},
  URN =		{urn:nbn:de:0030-drops-574},
  doi =		{10.4230/DagSemProc.05031.23},
  annote =	{Keywords: Stochastic Programming , Mean-Risk Optimization , Risk Measure , Lagrangian Relaxation , Electricity;}
}
Document
DOI: 10.4230/DagSemProc.05031.24
Properties and Calculation of Singular Normal Distributions

Authors: René Henrion and Tamas Szantai

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.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
DOI: 10.4230/DagSemProc.05031.25
Rowing to Barbados

Authors: Andy Philpott and Geoff Leyland

Abstract
In October 2003, sixteen boats set off from La Gomera in the Canary Islands headed for Barbados 4800 km distant. Each boat was manned by two oarsmen who were competing in the Transatlantic Challenge, an ocean rowing endurance event. This paper describes an optimization model developed for route planning in this event. It was used successfully by the Holiday Shoppe team to win the race in world record time. We describe the tool, its history, and the way it was used in the race.
Cite as

Andy Philpott and Geoff Leyland. Rowing to Barbados. In Algorithms for Optimization with Incomplete Information. Dagstuhl Seminar Proceedings, Volume 5031, pp. 1-6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{philpott_et_al:DagSemProc.05031.25,
  author =	{Philpott, Andy and Leyland, Geoff},
  title =	{{Rowing to Barbados}},
  booktitle =	{Algorithms for Optimization with Incomplete Information},
  pages =	{1--6},
  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.dagstuhl.de/entities/document/10.4230/DagSemProc.05031.25},
  URN =		{urn:nbn:de:0030-drops-656},
  doi =		{10.4230/DagSemProc.05031.25},
  annote =	{Keywords: ocean rowing , weather routing , dynamic programming , isochrones}
}
Document
DOI: 10.4230/DagSemProc.05031.26
Scenario Optimization for Multi-Stage Stochastic Programming Problems

Authors: Ronald Hochreiter

Abstract
The field of multi-stage stochastic programming provides a rich modelling framework to tackle a broad range of real-world decision problems. In order to numerically solve such programs - once they get reasonably large - the infinite-dimensional optimization problem has to be discretized. The stochastic optimization program generally consists of an optimization model and a stochastic model. In the multi-stage case the stochastic model is most commonly represented as a multi-variate stochastic process. The most common technique to calculate an useable discretization is to generate a scenario tree from the underlying stochastic process. In the first part of the talk we take a look at scenario optimization from the viewpoint of a decision taker, to provide rather non-technical insights into the problem. In the second part of the talk we examplify scenario tree generation by reviewing one specific algorithm based on multi-dimensional facility location applying backward stagewise clustering. An example from the area of financial engineering concludes the talk.
Cite as

Ronald Hochreiter. Scenario Optimization for Multi-Stage Stochastic Programming 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{hochreiter:DagSemProc.05031.26,
  author =	{Hochreiter, Ronald},
  title =	{{Scenario Optimization for Multi-Stage Stochastic Programming 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.dagstuhl.de/entities/document/10.4230/DagSemProc.05031.26},
  URN =		{urn:nbn:de:0030-drops-614},
  doi =		{10.4230/DagSemProc.05031.26},
  annote =	{Keywords: Stochastic programming, scenario generation, facility location, financial engineering}
}
Document
DOI: 10.4230/DagSemProc.05031.27
Searching with an Autonomous Robot

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

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.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
DOI: 10.4230/DagSemProc.05031.28
Subtree decomposition for multistage stochastic programs

Authors: Shane Dye

Abstract
A class of algorithms for solving multistage stochastic recourse problems is described. The scenario tree is decomposed using a covering collection of subtrees. The approach is illustrated with two examples: adapting the diagonal quadratic approximation algorithm and adapting nested Bender's decomposition. The approach leads to a class of methods based on the subtree cover chosen (including the original implementation of the algorithm adapted). This approach increases flexibility in the size, number and structure of subproblems for multistage stochastic programming decomposition methods.
Cite as

Shane Dye. Subtree decomposition for multistage 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{dye:DagSemProc.05031.28,
  author =	{Dye, Shane},
  title =	{{Subtree decomposition for multistage 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.dagstuhl.de/entities/document/10.4230/DagSemProc.05031.28},
  URN =		{urn:nbn:de:0030-drops-562},
  doi =		{10.4230/DagSemProc.05031.28},
  annote =	{Keywords: Stochastic programming , scenario tree , decomposition}
}
Document
DOI: 10.4230/DagSemProc.05031.29
Topology Matters: Smoothed Competitiveness of Metrical Task Systems

Authors: Guido Schäfer and Naveen Sivadasan

Abstract
We consider online problems that can be modeled as metrical task systems: An online algorithm resides in a graph of n nodes and may move in this graph at a cost equal to the distance. The algorithm has to service a sequence of tasks that arrive over time; each task specifies for each node a request cost that is incurred if the algorithm services the task in this particular node. The objective is to minimize the total request plus travel cost. Borodin, Linial and Saks gave a deterministic work function algorithm (WFA) for metrical task systems having a tight competitive ratio of 2n-1. We present a smoothed competitive analysis of WFA. Given an adversarial task sequence, we add some random noise to the request costs and analyze the competitive ratio of WFA on the perturbed sequence. We prove upper and matching lower bounds. Our analysis reveals that the smoothed competitive ratio of WFA is much better than its (worst case) competitive ratio and that it depends on several topological parameters of the graph underlying the metric, such as maximum degree, diameter, etc. For example, already for moderate perturbations, the smoothed competitive ratio of WFA is O(log(n)) on a clique and O(\sqrt{n}) on a line. We also provide the first average case analysis of WFA. For a large class of probability distributions, we prove that WFA has O(log(D)) expected competitive ratio, where D is the maximum degree of the underlying graph.
Cite as

Guido Schäfer and Naveen Sivadasan. Topology Matters: Smoothed Competitiveness of Metrical Task Systems. 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{schafer_et_al:DagSemProc.05031.29,
  author =	{Sch\"{a}fer, Guido and Sivadasan, Naveen},
  title =	{{Topology Matters: Smoothed Competitiveness of Metrical Task Systems}},
  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.dagstuhl.de/entities/document/10.4230/DagSemProc.05031.29},
  URN =		{urn:nbn:de:0030-drops-684},
  doi =		{10.4230/DagSemProc.05031.29},
  annote =	{Keywords: online algorithm, metrical task systems, work function algorithm, smoothed competitive analysis}
}
Document
DOI: 10.4230/DagSemProc.05031.30
Tracking mobile users

Authors: Leah Epstein and Asaf Levin

Abstract
Cellular telephony systems, where locations of a mobile users may be unknown at some times, are becoming more common. Mobile users are roaming in a zone. A user reports its location only if it leaves the zone entirely. We consider cellular zones with n cells and m mobile users roaming among the cells. The location of the users is uncertain and is given by m probability distribution vectors. The Conference Call Search problem (CCS) deals with tracking a set of mobile users, in order to establish a call between all of them. The search is performed in a limited number of rounds, and the goal is to minimize the expected search cost. In the "unit cost model", a single query for a cell outputs a list of users located in that cell. The "bounded bandwidth" model allows a query for a single user per cell in each round. We discuss three types of protocols; oblivious, semi-adaptive and adaptive search protocols. An oblivious search protocol decides on all requests in advance, and stops only when all users are found. A semi-adaptive search protocol decides on all the requests in advance, but it stops searching for a user once it is found. An adaptive search protocol stops searching for a user once it has been found (and its search strategy may depend on the subsets of users that were found in each previous round). We establish the differences between the distinct protocol types and answer some open questions which were posed in previous work on the subject.
Cite as

Leah Epstein and Asaf Levin. Tracking mobile users. 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{epstein_et_al:DagSemProc.05031.30,
  author =	{Epstein, Leah and Levin, Asaf},
  title =	{{Tracking mobile users}},
  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.dagstuhl.de/entities/document/10.4230/DagSemProc.05031.30},
  URN =		{urn:nbn:de:0030-drops-580},
  doi =		{10.4230/DagSemProc.05031.30},
  annote =	{Keywords: mobile users , PTAS}
}
Document
DOI: 10.4230/DagSemProc.05031.31
Tree-Sparse Modeling and Solution of Multistage Stochastic Programs

Authors: Marc Steinbach

Abstract
Multistage stochastic programs are prototypical for nonlinear programs with an inherent tree structure inducing characteristic sparsity patterns in the KKT systems of interior methods. We present an integrated modeling and solution approach for such tree-sparse programs. Three closely related natural formulations having desirable control-theoretic properties lead to KKT system solution algorithms with linear complexity. Application examples from computational finance and process engineering demonstrate the efficiency of the approach.
Cite as

Marc Steinbach. Tree-Sparse Modeling and Solution of Multistage 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{steinbach:DagSemProc.05031.31,
  author =	{Steinbach, Marc},
  title =	{{Tree-Sparse Modeling and Solution of Multistage 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.dagstuhl.de/entities/document/10.4230/DagSemProc.05031.31},
  URN =		{urn:nbn:de:0030-drops-714},
  doi =		{10.4230/DagSemProc.05031.31},
  annote =	{Keywords: Tree-sparse programs, multistage stochastic optimization, KKT systems, hierarchical sparsity}
}
Document
DOI: 10.4230/DagSemProc.05031.32
Uncertainties in stochastic programming models: The minimax approach

Authors: Jitka Dupacová

Abstract
50 years ago, stochastic programming was introduced to deal with uncertain values of coefficients which were observed in applications of mathematical programming. These uncertainties were modeled as random and the assumption of complete knowledge of the probability distribution of random parameters became a standard. Hence, there is a new type of uncertainty concerning the probability distribution. Using a hypothetical, ad hoc distribution may lead to bad, costly decisions. Besides of a subsequent output analysis it pays to include the existing, possibly limited information into the model, cf. the minimax approach which will be the main item of this presentation. It applies to cases when the probability distribution is only known to belong to a specified class of probability distributions and one wishes to hedge against the least favorable distribution. The minimax approach has been developed for special types of stochastic programs and special choices of the class of probability distributions and there are recent results aiming at algorithmic solution of minimax problems and on stability properties of minimax solutions.
Cite as

Jitka Dupacová. Uncertainties in stochastic programming models: The minimax approach. 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{dupacova:DagSemProc.05031.32,
  author =	{Dupacov\'{a}, Jitka},
  title =	{{Uncertainties in stochastic programming models: The minimax approach}},
  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.dagstuhl.de/entities/document/10.4230/DagSemProc.05031.32},
  URN =		{urn:nbn:de:0030-drops-452},
  doi =		{10.4230/DagSemProc.05031.32},
  annote =	{Keywords: stochastic programming models , minimax approach}
}

Filters

  • Authors
  • A
  • Albers, Susanne
  • Azar, Yossi
  • B
  • Bastin, Fabian
  • Bayraksan, Guzin
  • Becchetti, Luca
  • Beerliova, Zuzana
  • D
  • Dupacová, Jitka
  • Dye, Shane
  • E
  • Eberhard, Felix
  • Ehrhoff, Jan
  • Eichhorn, Andreas
  • Epstein, Leah
  • Erlebach, Thomas
  • F
  • Faigle, Ulrich
  • Fekete, Sándor
  • Fujiwara, Hiroshi
  • G
  • Grothklags, Sven
  • H
  • Hall, Alexander
  • Henrion, René
  • Hochreiter, Ronald
  • Hoffmann, Michael
  • Hoogeveen, Han
  • I
  • Iwama, Kazuo
  • K
  • Klein, Rolf
  • L
  • Leonardi, Stefano
  • Levin, Asaf
  • Leyland, Geoff
  • Lorenz, Ulf
  • M
  • Marchetti-Spaccamela, Alberto
  • Megow, Nicole
  • Mihalak, Matus
  • Möhring, Rolf H.
  • Morton, David P.
  • N
  • Niño-Mora, José
  • Norkin, Vladimir
  • Nüchter, Andreas
  • O
  • Onischenko, Boris.
  • P
  • Pflug, Georg Ch.
  • Philpott, Andy
  • R
  • Ram, L. Shankar
  • Rambau, Jörg
  • Richter, Yossi
  • Römisch, Werner
  • S
  • Sanders, Peter
  • Schaefer, Guidouca
  • Schäfer, Guido
  • Schoenhuth, Alexander
  • Schultz, Rüdiger
  • Schulz, Andreas S.
  • Schütz, Peter
  • Sgall, Jiri
  • Shmoys, David
  • Sivadasan, Naveen
  • Skutella, Martin
  • Stee, Rob van
  • Steinbach, Marc
  • Stougie, Leen
  • Swamy, Chaitanya
  • Szantai, Tamas
  • T
  • Tomasgard, Asgeir
  • U
  • Uetz, Marc
  • V
  • Van den Akker, Marjan
  • Vlerk, Maarten H. van der
  • Vredeveld, Tjark
  • W
  • Wegner, Isabel

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