Abstracts presentations phd students
BIJVANK, MARCO
Department of Mathematics
Vrije Universiteit Amsterdam
De Boelelaan 1081a
1081 HV Amsterdam
mbijvank@few.vu.nl
Supervisors
Ger Koole and Iris Vis
Equilibrium probabilities of lost sales inventory systems
Abstract
Equilibrium probabilities of lost sales inventory systems Abstract: The equilibrium distribution of the inventory on hand enables us to calculate all kinds of performance measures (e.g., service levels, cost objectives). These measures can be used again to find properties of the inventory system or optimal parameter values. During this presentation, we discuss a new technique that can be used to approximate such equilibrium probabilities for lost sales inventory models. We test the technique for different replenishment policies and different demand distributions.
| Back to home page | Program | Parallel sessions |
COENE, SOFIE
Katholieke Universiteit Leuven
Naamsestraat 69
3000 Leuven, Belgium
sofie.coene@econ.kuleuven.be
Supervisor
Frits Spieksma
Profit-based Latency Problems on the Line
Abstract
Consider the following problem. Given are a set of n clients located in some metric space and profits pi associated with each client i, i = 1,2,...,n. In addition, a single server is given, positioned at the origin at time t = 0. The server travels at unit speed. If the server serves client i at time t, the revenue collected by the server equals pi - t. The goal is to select clients and to find a route for the server serving the selected clients, such that total collected revenue is maximal.
We refer to this problem as the traveling repairman problem with profits, or TRPP for short. The TRPP is a generalization of the well-known traveling repairman problem (TRP), also known as the minimum latency problem (MLT). In the TRP, no profits are given and the goal is to serve all clients with minimal total latency.
We show:
(i) how a dynamic program solves the TRPP on the line in polynomial time,
(ii) how this result can be generalized to the problem with multiple identical servers (referred to as MTRPP on the line),
(iii) that the problem with multiple non-identical servers and release dates for each client, is NP-hard.
In the proof of the latter result we settle the complexity of an open problem described in literature.
| Back to home page | Program | Parallel sessions |
ES-SAGHOUANI, ABDELGHAFOUR
University of Amsterdam
Korteweg - de
Vries Institute for Mathematics
Plantage Muidergracht 24
1018 TV Amsterdam
aessagho@science.uva.nl
Supervisor
Michel Mandjes
On the correlation structure of a Lévy-driven queue
Abstract
Clich here for pdf file of the abstract
| Back to home page | Program | Parallel sessions |
HAAN, ROLAND DE
University of Twente
Faculty of EWI
Department of Mathematics
P.O. Box 217
7500 AE Enschede
r.dehaan@ewi.utwente.nl
Supervisor
Richard Boucherie
A polling model with an autonomous server
Abstract
Polling models are used as an analytical performance tool in several application areas. In these models, the focus often is on controlling the operation of the server as to optimize some performance measure. For some applications, controlling the server is not an issue as the server moves independently through the system. We present the analysis for such a polling model with a so-called autonomous server. In this model, the server always remains for an exponential time at a queue, which implies that service is preemptive. Another implication, which contrasts with most of the previous research on polling models, is that the server does not immediately switch to a next queue when the current queue becomes empty. The analysis is based on considering imbedded Markov chains at specific instants. A system of equations for the queue-length distributions at these instants is given and solved for. Besides, we study to which extent the queues in the polling model are independent and identify parameter settings for which this is indeed approximately the case. These results may be used to approximate performance measures for complex multi-queue models by analyzing a simple single-queue vacation model. Finally, we show that tandem models with a single autonomous server can be analyzed using the same techniques.
| Back to home page | Program | Parallel sessions |
IERSEL, LEO VAN
Eindhoven University of Technology
Department of Mathematics and Computer Science
P.O. Box 513
5600 MB Eindhoven
l.j.j.v.iersel@tue.nl"
Supervisors
Judith Keijsper and Leen Stougie
Level-k phylogenetic networks: uniqueness and complexity
Abstract
A central problem in biology is to reconstruct plausible evolutionary histories. This area of research is called phylogenetics and provides fascinating challenges for both biologists and mathematicians. Throughout most of the history of phylogenetics researchers have concentrated on constructing phylogenetic trees. In recent years however, more and more attention is devoted to phylogenetic networks. From a biological point of view, networks are able to explain and visualise more complex evolutionary scenarios, since they take into account biological phenomena that cannot be displayed in a tree. These phenomena are so-called reticulate evolutionary events such as hybridisation, recombination and horizontal gene transfer. From a mathematical point of view however, phylogenetic networks pose formidable challenges. In this talk I consider the construction of level-k phylogenetic networks from triplets, i.e. phylogenetic trees with three leaves. The level k of the networks determines how non-treelike the evolution is allowed to be, with level-0 networks being trees. I give, for each k, a level-k network that is uniquely defined by its triplets. I demonstrate the applicability of this result in two proofs that show the computational intractability of constructing level-k phylogenetic networks from triplets, for all k.
| Back to home page | Program | Parallel sessions |
LEAHU, HARALAMBIE
Vrije Universiteit Amsterdam
De Boelelaan 1105
1081 HV Amsterdam
hleahu@feweb.vu.nl
Supervisor
Bernd Heidergotts
Strong bounds on perturbations using weak derivatives
Abstract
Clich here for pdf file of the abstract
| Back to home page | Program | Parallel sessions |
MNICH, MATTHIAS
Eindhoven University of Technology
Department of Mathematics and Computer Science
P.O. Box 513
5600 MB Eindhoven
m.mnich@tue.nl
Supervisor
Gerhard Woeginger
Exact construction of galled phylogenetic networks from triplets
Abstract
Galled phylogenetic networks provide a way to describe and visualise evolutionary histories that have undergone so-called reticulate evolutionary events such as recombination, hybridisation or horizontal gene transfer. In galled phylogenetic networks the undirected cycles of recombination are disjoint. We study the problem of constructing galled phylogenetic networks from triplets, i.e. phylogenetic trees for three leaves (taxa). It is NP-hard to construct a galled network consistent with a maximum number of input triplets, even when the input is dense. As a response to this intractability we give an exponential time exact algorithm for constructing galled networks consistent with a maximum number of input triplets. This is joint work with Leo van Iersel (TU/e) and Steven Kelk (CWI).
| Back to home page | Program | Parallel sessions |
ROOIJ, JOHAN VAN
Utrecht University
Department of Information and Computer Science
P.O. Box 80.089
3508 Utrecht
johanvr@cs.uu.nl
Supervisor
Hans Bodlaender
Design by measure and conquer: A faster exact algorithm for Dominating Set
Abstract
Clich here for pdf file of the abstract
| Back to home page | Program | Parallel sessions |
ROUBOS, DENNIS
Faculty of Sciences
Vrije Universiteit Amsterdam
De Boelelaan 1081a
1081 HV Amsterdam
droubos@few.vu.nl
Supervisor
Sandjai Bhulai
Average-cost approximate dynamic programming for the control of birth-death processes
Abstract
Dynamic programming is an attractive method for solving decision problems in stochastic systems. However, due to the large scale and complex nature of many decision problems, dynamic programming suffers from the curse of dimensionality. Therefore, standard solutions techniques, such as value iteration and policy iteration, cannot be applied directly. Consequently, much research effort has been put into approximate dynamic programming to alleviate this problem.
Approximate dynamic programming when applied to average-cost decision problems with a countably infinite state space suffers from several computational issues. In particular, the algorithm may converge to non-stable solutions and requires knowledge on the average cost in advance. We address these issues by providing a theoretical basis for the approximation structure such that the unique stable solution will be attained. We illustrate this for the broad class of birth-death processes.
| Back to home page | Program | Parallel sessions |
VERLOOP, MAAIKE
CWI
Kruislaan 413
1098 SJ Amsterdam
maaike.verloop@cwi.nl
Supervisors
Sem Borst and Sindo Núñez Queija
Scheduling in bandwidth-sharing networks
Abstract
Bandwidth-sharing networks as considered by Massoulie & Roberts provide a natural modeling framework for describing the dynamic flow-level interaction among elastic data transfers. We focus on some simple linear bandwidth-sharing networks which provide a useful model for flows that traverse several links and experience bandwidth contention from independent cross-traffic. First we show that size-based scheduling strategies such as Shortest Remaining Processing Time first (SRPT) and Least Attained Service first (LAS), which are known to improve the mean-delay performance in a single server system, may cause instability effects in a linear network and will therefore not yield optimal delay performance. Then we characterize policies that minimize the mean delay or equivalently the mean number of users. For some particular cases, priority policies will stochastically minimize the number of users. In general, the optimal policy can be described by so-called switching curves. However, no exact characterization exists. By analyzing a related fluid model, we find that linear switching curves accurately approximate the optimal strategy. When two nodes on the flow path are equally loaded, however, the fluid scaling is not appropriate, and it may be shown that the switching curve has a square-root shape. Finally, we compare the performance of the optimal policy with that of various alpha-fair policies, which are representations of common distributed allocation schemes, and find that alpha-fair policies perform quite well.
| Back to home page | Program | Parallel sessions |
VLIEGEN, INGRID
Eindhoven University of Technology
Department of Technology Management
P.O. Box 513
5600 MB Eindhoven
i.m.h.vliegen@tue.nl
Supervisors
Geert-Jan van Houtum and Ton de Kok
Bounds on the order fill rates for an inventory system of service tools
Abstract
In this talk, we deal with the analysis of a single-location, multi-item inventory model for service tools. Multiple service tools are kept, with different stock levels, at the warehouse. Independent Poisson demand streams arrive at the warehouse requesting different sets of tools. Those tools from the requested set that are in stock are then released; they are “in use” for an exponential amount of time, after which they are returned together. (Requested tools that are not on stock are delivered via an emergency channel; for the warehouse they may be considered as lost sales.) Thus our model features coupled demands and coupled returns - sets of tools are released and returned together. We are interested in the order fill rates, i.e., the percentage of demands for which all requested tools are delivered from stock. As the Markov chain describing the original system is of extremely high dimension, we introduce two, more tractable, approximate models. By combining Markov reward theory and aggregation we prove that the order fill rates of these approximate models lead to a lower and an upper bound on the order fill rate in the original model.
| Back to home page | Program | Parallel sessions |
WANG, XINHUI
University of Twente
Faculty of EWI
Department of Mathematics
P.O. Box 217
7500 AE Enschede
xinhuiw@math.utwente.nl
Supervisor
Walter Kern
Recent results of the exact algorithm for Steiner tree problem
Abstract
Clich here for pdf file of the abstract
| Back to home page | Program | Parallel sessions |