Seminars already given (chronological order)

[1995] [1996] [1997] [1998] [1999] [2000] [Bottom]


Friday September 8, 1995, 11:00 - 13:00

Wednesday September 20, 1995, 09:00-11:00

Friday October 6, 1995, 11:00-13:00

Friday October 20, 1995, 11:00-13:00

Friday November 3, 1995, 11:00-13:00

Thursday November 16, 1995, 13:00-15:00 (Note day and time!)

Bill Cook, currently at Bonn University, will visit the Department of Computer Science on November 16, 1995. He is, together with David Applegate, Bob Bixby and Vasek Chvatal, working on solving large instances of the traveling salesman problem. This group holds the current "world record" after solving a 7397-city instance to optimality. To solve the problem they used an array of Silicon Graphics machines at Silicon Graphics' Center in Houston. The array consisted of 10 Challenge XL machines, each having 20 processors and 2 gigabytes of memory.


We describe some of the components of a computer code for solving travelling salesman problems. The tour finding portion of the code is based on branch-width and a new implementation of Martin, Otto, and Felten's Chained Lin-Kernighan heuristic. Our lower bounds are computed using a threadsafe version of Cplex and a collection of cutting plane separation algorithms. We also discuss several applications of branch-width and tour-finding in telecommunications. This talk is based on ongoing work with Paul Seymour and with David Applegate, Bob Bixby, and Vasek Chvatal.

Friday December 1, 1995, 11:00-13:00


We discuss a recent note by Chalasani and Motwani on the k-delivery traveling salesman problem, dealing with the near-optimal routing of a k-capacity vehicle.

Friday December 15, 1995, 11:00-13:00


The frequency assignment problem (FAP) is described as follows. A set of transmission links needs to be established in order to enable communication between a set of points. With each link we associate a set of possible choices of frequencies. The assignment of a frequency to a link has to be done such that no interference occurs between any pair of links, i.e., such that for every pair of links the frequencies assigned to these links differ by a prespecified amount, possibly zero. The objective is to minimize the number of frequencies that are used. We discuss different formulations of FAP, and how to generate good lower and upper bounds.


Friday February 2, 1996, 11:00-13:00

Abstract 1

A brief introduction, and challenges of the "Vehicle Routing Problem with Time Windows (VRPTW)" is given. The following algorithms for this problem will be described in more detail, including related data structures, (dis)advantages, and required time bounds: Moreover, open problems and new directions of further research will be described.

Abstract 2

There exists ample literature about the two and three dimensional bin packing problem. However, non of the algorithms presented in the literature are designed for the case that there are constraints on the order in which the objects have to be removed from the bin. This constraint is relevant in the case that we are loading a truck with several orders that have to be unloaded at different destinations. We present a population-based search heuristic for packing a bin with boxes, and present the data structures needed to implement the heuristic in both two and three dimensions. The algorithm is re-entrant and can be called iteratively to pack a bin with orders for different destinations.

Friday February 16, 1996, 11:00-13:00


The problem of finding a shortest execution of a program on a parallel computer can be modelled by the following scheduling problem: the program is represented by a directed graph, every node is a part of the program and an arc corresponds to a precedence constraint. The objective is assigning a starting time to every task such that the last task is completed as early as possible. We will consider a more general problem: every task has a deadline before which its execution has to be completed. If communication between different processors is neglected, then for a special class of precedence graphs a schedule in which no deadline is violated can be found in polynomial time. When communication delays are introduced, the problem becomes more complicated. I will present a way of dealing with the communication delays.

Friday March 15, 1996, 11:00-13:00


Veel bekende combinatorische problemen kunnen worden gezien als geparametriseerde problemen: problemen waar een zeker gedeelte van de input wordt onderscheiden als parameter. In deze lezing kijken we naar de complexiteit van dit soort problemen wanneer de parameter klein (een constante) is. Downey en Fellows introduceerden de theorie van de vaste parameter complexiteit, om preciezer te kijken naar het gedrag van problemen die polynomiaal oplosbaar zijn met een constante parameter. Een inleiding zal worden gegeven in deze theorie, en een aantal centrale begrippen zullen worden uitgelegd. Tenslotte zal een moeilijkheidsbewijs geleverd worden voor het precedence constrained k-processor scheduling probleem.

Friday March 29, 1996, 11:00-13:00


We discuss the result presented in the paper by Goemans and Williamson: ".878-Approximation Algorithms for MAX CUT and MAX 2SAT", Proceedings STOC 94. We also briefly discuss other applications of semidefinite programming.

Friday April 12, 1996, 11:00-13:00

Friday April 26, 1996, 11:00-13:00


Every graph contains a subgraph (spanning forest) that preserves all local connectivities: indeed, if an xy-path exists in G then such a path exists in the forest. Likewise, every graph contains a subgraph (called k-connectivity certificate) that preserves the DEGREE of connectivity up to k, that is, if G has l disjoint xy-paths, then the certificate has min(l,k) of such paths. Computing the smallest k-certificate is NPC (see Garey and Johnson GT31), but we can compute k-certificates with less than kn edges surprisingly efficient. These Sparse certificates have interesting applications, such as, in linear-time approximations of connectivity and fast epsilon-approximations of (s,t) flow.

Friday May 10, 1996, 11:00-13:00

Friday May 24, 1996, 11:00-13:00

Friday June 7, 1996, 11:00-13:00


In this informal talk we discuss a "branching-on-hyperplane" technique for solving general linear integer programming problems. The main ingredient in such a technique is basis reduction. We focus on the basis reduction algorithm by A.K. Lenstra, H.W. Lenstra Jr., and L. Lov'asz. We also briefly describe the so-called general basis reduction algorithm by Lov'asz and Scarf.

Friday June 21, 1996, 11:00-13:00

Friday September 13, 1996, 11:00 - 13:00

Friday October 4, 1996, 11:00-13:00

Friday October 11, 1996, 11:00-13:00


On-line scheduling problems are classified according to which part of the problem is given on-line. There are several very different possibilities. Jobs can arrive either one by one or over time, with either known or unknown characteristics.

In this presentation, we concentrate on deterministic on-line algorithms for scheduling problems where jobs arrive over time, and all job characteristics become known at their arrival. For several machine environments we present lower bounds on the worst-case ratio of any on-line algorithm. Furthermore, for some of these problems we present on-line algorithms with a worst-case ratio equal to the lower bound.

Friday October 25, 1996

No seminar due to ALCOM-IT workshop and WG Najaarssymposium.

Friday November 8, 1996, 11:00-13:00

  • Topic: Solving an integer feasibility problem arising in video signal processing
  • Speaker: Karen Aardal, Department of Computer Science, Utrecht University

  • Friday November 22, 1996, 11:00-13:00

  • Topic: Column generation in combinatorial optimization - a review
  • Speaker: Bram Verweij, Department of Computer Science, Utrecht University

  • Friday December 6, 1996, 11:00-13:00

  • Topic: How to solve problems on graphs of bounded treewidth
  • Speaker: Hans Bodlaender, Department of Computer Science, Utrecht University

  • Friday December 20, 1996, 11:15-12:15

  • Topic: Cutting problems in theory and practice -- a column generation approach with local search refinements
  • Speaker: Cor Hurkens, Department of Mathematics and Computing Science, Eindhoven University of Technology

  • 1997

    Monday January 13, 1997, 14:00-15:00


    Recently, exciting new algorithms have been developed for the minimum cut problem. The new algorithms include those by Nagamochi and Ibaraki, Hao and Orlin, Karger and Stein, and Karger. These algorithms are very different from the earlier ones and from each other and substantially improve worst-case time bounds for the problem. We conduct experimental evaluation of relative performance of these algorithms. In the process, we develop heuristics and data structures that substantially improve practical performance. We also develop problem families for testing minimum cut algorithms. Our work leads to a better understanding of practical performance of the minimum cut algorithms and produces very efficient codes for the problem.

    The technical report NECI-TR-96-132 describing these results in detail is available via URL It is joint work with Chandra Chekuri, David Karger, Matt Levine, and Cliff Stein.

    Friday January 31, 1997, 11:00-13:00


    In this talk we consider several Vehicle Routing Problems, occuring in real-life situations. Outline and motivations of the problems are given in a mathematical sense. We also present the (heuristic) algorithms, as applied (or going to be) to the algorithms, including advantages and disadvantages. In particular, we consider the following problems:

    As mentioned above, the work on these problems is not finished yet. Hence comments, suggestions and new directions for research in this area is very welcome and motivated.

    Friday February 14, 1997, 11:00-13:00

    Monday, March 3, 1997, 11:00-13:00

    Friday March 14, 1997, 11:00-13:00


    For an integer programming problem, a test set is a set of vectors such that for every feasible, non-optimal point of the program there exists a member in the test set with which the non-optimal point can be improved. n this talk we review known test sets in literature such as the Graver test set and test sets based on Gröbner basis methods. We show how to compute them in general and in special cases. We also discuss complexity issues for questions related to test sets and establish various connections to decomposition in integer programming and to polyhedral combinatorics.

    Friday April 11, 1997, 11:00-13:00


    The LogP model is a model of parallel computation that characterises a parallel computer architecture by four parameters: the latency L, the overhead o, the gap g and the number of processors P. We study the problem of constructing minimum-length schedules for tree-structured programs in the LogP model. This problem is proved to be NP-hard, even for trees of depth two in LogP models with an unlimited number of processors and a positive gap. For the problem of constructing minimum-length schedules for d-ary intrees in a LogP model with a finite number of processors, an approximation algorithm is presented that is applicable in many models of parallel computation. It constructs schedules on P processors of length at most (d+1)-[(d^2+d)/(d+P)] times the length of a minimum-length schedule plus the time needed for at most P-1 communication actions.

    Friday April 25, 1997, 11:00-13:00


    The talk deals with new models and techniques for an integrated approach to vehicle and crew scheduling and applications to real life problems. These techniques include exploitation of network flow structures using Lagrange duality and column generation, and new algorithms for vehicle scheduling and the column generation pricing problem.

    Traditionally, vehicle and crew scheduling have been dealt with in a sequential manner, were vehicle schedules are determined before the crew schedules. We discuss potential benefits of integration and provide an overview on the scarce literature which considers only partial integration. Our approach is new in the sense that we consider complete integration of vehicle and crew scheduling. Concerning the vehicle scheduling aspect of our approaches, we only consider the basic single depot vehicle scheduling problem. This makes our approach in principle applicable for bus and driver scheduling.

    We also propose a new approach for scheduling crews independent of vehicles. This approach can serve as a measure of the potential benefit of integration, that is, it may be beneficial to integrate if the solution value of the traditional sequential approach differs much from the solution value of the independent approach. We discuss several new mathematical formulations for the approaches considered in this chapter, and consider corresponding relaxations and optimization based heuristic algorithms. These algorithms rely on column generation applied to set partitioning type of models. The talk is concluded with a computational study which shows the applicability of the proposed techniques in practice, and addresses the effectiveness of integration when compared to a sequential approach.

    Friday May 23, 1997, 11:00-13:00

    Friday June 6, 1997, 11:00-13:00

                     *** EXTRA SEMINAR *** 

    Tuesday June 10, 1997, 15:00-16:00


    The inference of evolutionary history is a complex problem. In this talk we will describe a new method that has been developed by historical linguists and computer scientists, which uses graph-theoretic algorithms to reconstruct the history of the Indo-European family of languages.

    June 9-13, 1997

    Friday, June 20, 1997, 13:30-18:00

    Friday, September 12, 1997, 11:00-13:00

    Friday, September 26, 1997, 11:00-13:00

    Friday, October 3, 1997, 11:00-13:00


    We consider the problem of minimizing the total Flow Time of a set of jobs released over time in a multiprocessor setting. The individual flow time of a job is the time between its release and its completion. The total flow time is the overall time spent by the jobs in the system before completion. We present the first approximation algorithms with performance guarantee for the preemptive and the non-preemptive version of the problem.

    (Joint work with Danny Raz.)

    Friday, October 10, 1997, 11:00-13:00

    Friday, October 24, 1997, 11:00-13:00


    Statistische bureau's als het CBS verzamelen gegevens van personen, huishoudens, instellingen en bedrijven voor statistisch onderzoek. Deze gegevens worden in enigerlei vorm aan onderzoekers ter beschikking gesteld, bijvoorbeeld in de vorm van microdata (bestanden gevens van individuele eenheden) of tabellen (aggregaten). Omwille van de privacybescherming van de individuen waar de verstrekte gegevens betrekking op hebben, worden de gevens altijd geanonymiseerd, hetgeen betekent dat directe identificerende kenmerken zoals naam, adres, telefoonnummer e.d. niet worden meegeleverd. Dit is echter vaak niet voldoende om onthulling van individuen in de verstrekte data tegen te gaan, zeker niet wanneer de data andere identificerende informatie bevat. Daarom worden data voordat zij het statistisch bureau verlaten gecontroleerd op hun veiligheid, d.w.z. het risico waarmee zij onthulling zouden toelaten. Zo mogelijk worden de data aangepast om het onthullingsrisico in te perken. Data kunnen op diverse maieren worden gemodificeerd: variabelen kunnen minder gedetailleerd worden gemaakt (hercoderen), waarden kunnen worden vervangen door ontbrekende waarden (onderdrukken), waarden kunnen volgens een stochastisch procede worden vervangen door andere waarden. De kunst is om dit zo te doen dat enerzijds veilige data worden gemaakt (volgens de criteria die men daarvoor hanteert) en anderzijds dat niet te veel informatie verloren gaat.

    In de voordracht wordt ingegaan op diverse problemen die men hierbij ontmoet, zoals het formuleren van veiligheidscriteria, het kwantificeren van informatieverlies, het optimaal modificeren van de data. Voor een belangrijk deel betreft het problemen die momenteel onderwerp van studie zijn. Het doel van de voordracht is om het - buiten de wereld van statistische bureau's - betrekkelijk onbekende terrein van de statistische beveiliging te schetsen, en daarbij in het bijzonder te wijzen op het multidisciplinaire karakter van een aantal kernproblemen.

    Friday, October 31, 1997, 11:00-13:00

    Friday, November 14, 1997, 11:00-13:00

    Friday, December 12, 1997, 11:00-13:00


    Friday January 23, 1998, 11:00 - 13:00

    Friday January 30, 1998, 11:00 - 13:00

    Friday February 13, 1998, 11:00 - 13:00


    In the past decades much effort has been put in determining the complexity of combinatorial optimization problems. Once an optimization problem is found to be NP-hard, it is unlikely that there is a polynomial time algorithm that produces an optimal solution. This motivates the search for algorithms that output good solutions in polynomial time. A fundamental question is how good we can approximate an optimization problem in polynomial time. Here, we are interested in negative results. For machine scheduling problems there are many negative results. All these results are based on the so-called gap technique. The introduction of the complexity classes MAX NP and MAX SNP by Papadimitriou and Yannakakis combined with the work of Arora, Lund, Motwani and Sudan on hardness of approximation problems in the early 90s, has given a new tool to prove non-approximability results for all kinds of optimization problems. We consider three deterministic machine scheduling problems in an off-line setting. All these problems have as objective to minimize the sum of completion times. The first problem we study is a parallel machine problem in which the machines are unrelated and the jobs have release dates. The second and the third problem are shop problems, the standard flow shop problem and the standard open shop problem respectively. By means of L-reductions from MAX SNP-hard problems, we prove that the scheduling problems have no polynomial time approximation scheme, unless P=NP.

    This is joint work with Han Hoogeveen and Gerhard Woeginger.

    Friday, February 27, 1998, 11:00-13:00

    Friday, March 20, 1998, 11:00-13:00

    Friday, March 27, 1998, 11:00-13:00

    Friday, April 17, 1998, 11:00-13:00

    Monday, April 20, 1998, 10:00-17:00

    Friday, May 8, 1998, 11:00-13:00

    Friday, May 22, 1998, 11:00-13:00

    Friday, May 29, 1998, 11:00-13:00

    Abstract Topic 1

    In this talk we will describe ways to share a secret to k persons so that only if lm l<= k of them (or more) will be able to recover it. In particular we will present in detail the Asmuth-Bloom threshold scheme based on the Chinese remainder theorem. We will finally discuss some ``special purpose'' threshold schemes proposed in the bibliography.

    Abstract Topic 2

    In this talk we will make an attempt of an introduction to what is called Quantum Computing. We will give a simple example of quantum computation commending its differences with the classical probabilistic machine paradigm.

    Friday September 11, 1998, 11:00 - 12:00


    We present an asynchronous distributed algorithm for finding 3-edge-connected components in arbitrary networks. For networks having n processors and m links, the algorithm executes in O(n) time using O(m) messages, where message length is O(log n) bits. The algorithm uses a novel onion-skin structure to achieve communication optimality. The algorithm is also existentially time optimal in the sense that there exist networks for which the time complexity is the best possible.

    Friday September 25, 1998, 11:00 - 13:00


    Consider two omnidirectional robots carrying a ladder, one at each end, in the plane without obstacles. Given start and goal positions of the ladder, what is a time-optimal motion of the robots subject to given constraints on their kinematics such as maximum acceleration and velocity? Applying the optimal control theory, we solved this problem under a kinematic constraint that the speed of each robot must be either 0 or a given constant v at any moment during the motion. The solution, which requires complicated calculation, is centralized and off-line: we calculate the motion and give it to the robots in advance. In this talk, we demonstrate that even without the complicated calculation, a motion that is sufficiently close to time-optimal can be obtained using a simple distributed strategy in which each robot decides its motion individually based on the current and goal positions of the ladder.

    Friday October 9, 1998, 11:00 - 13:00


    At CQM-Optimization, we (among other things) make software modules for solving optimization problems of our customers. Usually, the problems fall in one the following categories: transportation problems, rostering problems, or design optimization problems. In this talk, I will present one or more problems on which I have been working in the last years. I will present the problems, and (most of) the constraints and the practical limitations. I will also briefly discuss the algorithms implemented by us, and some extensions to the problems that will have to be built in in the future.

    Friday October 23, 1998, 11:00 - 13:00


    Voor sorteren in de verschillende berekeningsmodellen, sequentieel, parallel en extern, zijn scherpe ondergrenzen bekend. Aan de andere kant zijn er algorithmen, denk aan bucket-sort, die onder de ondergrenzen uitkomen. Dat kan zijn omdat we het probleem een beetje vereenvoudigen of omdat we iets doen dat niet gedekt wordt door het bewijs van de ondergrens. In deze voordracht wordt geprobeerd een antwoord te geven op de vraag wanneer en hoe de ondergrenzen onderboden kunnen worden. Oa. zal ik kijken naar sorteren op reconfigurable-arrays, naar het sorteren van uniforme verdelingen, naar sorteren zonder omordenen, naar padded sorting en naar word-level parallelism.


    Friday January 8, 1999, 13:00 - 14:00


    We consider the following map labelling problem: given distinct points $p_1, p_2, \ldots, p_n$ in the plane, find a set of pairwise disjoint axis-parallel squares $Q_1, Q_2, \ldots, Q_n$ where $p_i$ is a corner of $Q_i$. This problem is equivalent to that of finding a maximum independent set in a graph.

    We present an optimization algorithm for finding maximum independent sets and apply it to independent set instances arising from map labelling. The algorithm uses a new technique for setting variables in the branch and bound tree that implicitly exploits the Euclidean nature of the independent set problems arising from map labelling. Computational experiments show that this technique is very successful in controlling the size of the branch and bound tree.

    Friday January 15, 1999, 10:00 - 17:00


    For postscript file of abstract click here.
    This is a C code for computing the complex of maximal lattice free bodies for an n+1 by n matrix.

    Friday January 29, 1999, 11:00 - 13:00


    In this lecture results on the dial-a-ride problem with a single server are presented. Requests for rides consist of two points in a metric space, a source and a destination. A ride has to be made by the server from the source to the destination. The server travels at unit speed in the metric space and the objective is to minimize some function of the delivery times at the destinations. We study this problem in the natural on-line setting. Calls for rides come in while the server is traveling. This models e.g. the taxi problem, or, if the server has capacity more than 1 a minibus or courier service problem. For the version of this problem in which the server has infinite capacity having as objective minimization of the time the last destination is served, we design an algorithm that has competitive ratio 2. We also show that this is best possible, since no algorithm can have competitive ratio better than 2 independently of the capacity of the servers. Besides, we give a simple 2.5-competitive algorithm for the case with finite capacity. Then we study the on-line problem with objective minimization of the sum of completion times of the rides. We prove a lower bound on the competitive ratio of any algorithm of $1+\sqrt{2}$ for a server with any capacity and of 3 for a server with capacity 1. Finally, we present the first competitive algorithm for the case the server has infinite capacity and the metric space is the real line. The algorithm has competitive ratio 15.

    Friday February 12, 1999, 11:00 - 13:00


    Cornuéjols and Dawande proposed a set of 0-1 linear programming instances that proved to be very hard to solve by traditional methods, and in particular by linear programming based branch-and-bound. They offered these market split instances as a challenge to the integer programming community. The market split problem can be formulated as a system of linear diophantine equations in 0-1 variables. We perform some computations to illustrate why these problems are hard. Furthermore, we use the algorithm of Aardal, Hurkens and Lenstra (1998) based on lattice basis reduction to reformulate the problem. As a result we obtain a formulation which is much easier to solve. This algorithm is not restricted to deal with market split instances only but is a general method for solving systems of linear diophantine equations with bounds on the variables. This is joint work with Karen Aardal, Cor Hurkens and Arjen Lenstra.

    Friday March 5, 1999, 11:30 - 13:00


    In deze voordracht kijk ik naar verschillende varianten van het twee-machine flow shop probleem; in een twee-machine flow shop probleem moet iedere taak eerst door machine 1 en vervolgens door machine 2 worden bewerkt. Ik zal aangeven hoe deze problemen kunnen worden gemodelleerd met behulp van positionele completeringstijden, en hoe je dit kunt gebruiken bij het bepalen van onder- en bovengrenzen.

    Friday April 16, 1999, 11:00 - 13:00


    The reinforcement problem is defined on a graph G=(V,E) with capacities, costs, and communication pairs. The object is to select a minimum cost reinforcement ( = subset of edges) so that the capacity between pair of nodes (i,j) in the set of communicating pairs is at least D(i,j).

    This problem can be modelled as a integer program (IP). The standard integer programming formulation of this problem has the property that the ratio between the optimal IP solution and the optimal solution to the linear program (LP) obtained by removing the integrality constraints on the variables can be as bad as min (|E|, D)/2. (This is in contrast to the problem with uniform capacities, for which a 2-approximation is obtainable using the LP relaxation). We introduce additional inequalities to the linear program that are satisfied by all integer solutions and show that, for a special class of graph, these improve the worst case IP/LP ratio to 2 if there is only one communicating pair, and to at least 3 if there is more than one communicating pair. We also show that these inequalities reduce the ratio in general graphs. Our proof technique extends to some more general covering problems.

    We also describe approximate separation algorithms for these inequalities to obtain polynomial time approximation algorithms with a guarantee that matches our improved bound on the IP/LP ratio. Our algorithms extend to the multicover problem (the generalization of the set cover problem when each element must be covered multiple times) and improve upon the best previous approximation guarantees for this problem.

    This is work in progress joint with Bob Carr, Cindy Phillips, and Vitus Leung, all of Sandia National Laboratories, Albuquerque, USA.

    Friday May 7, 1999, 11:00 - 13:00


    Met de ontwikkelingen in CAO's en ARBO-wetgeving wordt het vinden van goede dienstroosters voor de inzet van personeel zodanig ingewikkeld dat het ondoenbaar wordt ze handmatig te genereren. Vaak is er een heel scala van criteria die bepalen of een gegeven dienstrooster al of niet goed is; een dezer criteria wordt gevormd door de personele kosten van een dienstrooster. Een ander criterium is de mate van spreiding van werklast over de verschillende personeelsleden, of de mate waarin een dienstrooster de alertheid van het personeel op peil weet te houden.

    In deze voordracht zal ik ingaan op een specifiek dienstrooster probleem, wiskundige modelleringen geven, en in gaan op het ontwerp van heuristieken.

    Friday May 21, 1999, 11:00 - 13:00


    We look at the point labeling problem: given n points p_1,...,p_n in the plane and n rectangular labels l_i,...,l_n, try to place as many labels as possible under the conditions that the labels must not intersect and that the point must lie on one the four edges of the corresponding label. In the slider models the labels are not restricted to a finite number of positions, such as in the 4-position model. We compare slider models to fixed position models both in theory and in practice.

    The point labeling problem can be formulated as a special case of the independent set problem. For general graphs there does not exist an approximation scheme for the independent set problem. However, for the point labeling problem we can give a polynomial-time approximation scheme and a simple and efficient factor-½ approximation algorithm for the slider and fixed position models. Finally we present experimental results of the factor-½ approximation algorithm to compare the different models in practice and to compare this algorithm to other algorithms suggested in the literature.

    Wednesday July 7, 1999, 13:00 - 16:00


    We consider the problem of scheduling n independent jobs on m identical processors when each job has a release time and additional tail. A tail needs no machine time but is taken into account for the calculation of the maximal job completion time or the makespan. Our objective is to minimize the makespan. We propose a new improved polynomial time algorithm for this problem.

    Friday September 3, 1999, 11:00 - 13:00


    In the k-level uncapacitated facility location problem, we have a set of demand points where clients are located. The demand of each client is known. Facilities have to be located at given sites in order to service the clients, and each client is to be serviced by a sequence of k different facilities, each of which belongs to a distinct level. There are no capacity restrictions on the facilities. There is a positive fixed cost of setting up a facility, and a per unit cost of shipping goods between each pair of locations. We assume that these distances are all nonnegative and satisfy the triangle inequality. The problem is to find an assignment of each client to a sequence of k facilities, one at each level, so that the demand of each client is satisfied, for which the sum of the setup costs and the service costs is minimized.

    We develop a randomized algorithm for the k-level facility location problem that is guaranteed to find a feasible solution of expected cost within a factor of 3 of the optimum cost. The algorithm is a randomized rounding procedure that uses an optimal solution of a linear programming relaxation and its dual to make a random choice of facilities to be opened. We show how this algorithm can be derandomized to yield a 3-approximation algorithm.

    This is joint work with F. Chudak and D.B. Shmoys

    Friday September 17, 1999, 11:00 - 13:00


    The last few years there has been an increasing amount of interest in the field of distribution estimation optimization algorithms. As more techniques are introduced, the variety in tested distribution structures increases. In this talk we analyze the implications of the form of such a structure. We show that learning the linkage relations alone and using them directly in a distribution estimation algorithm to generate new samples is not sufficient for building competent evolutionary algorithms. The information needs to be processed to identify and use the building blocks.

    Friday October 1, 1999, 11:00 - 13:00


    We consider a generalization of the classical job shop scheduling problem. In our model there are release times, positive end-start time lags, and a general precedence graph. As objective we consider the total weighted tardiness.

    We use a tabu search algorithm to search for the order in which the operations are processed on each machine. Given an execution order of the operations on each machine, we determine optimal starting times by solving a maximum cost flow problem. The starting times could also be determined by solving a single source longest path tree in an acyclic graph. We show that it only costs a small amount of extra computation time to determine the solution of the maximum cost flow problem.

    The solution of the maximum cost flow problem is used to determine the neighborhood for our tabu search algorithm. All sequences in our neighborhood are obtained by swapping certain pairs of adjacent operations. We show that only swaps that possess a certain property can improve the current solution; if no such swap is available in the neighborhood, then the current solution is optimal. We finally give extensive computational results.

    Friday October 29, 1999, 13:00 - 15:00


    Proactieve veiligheid is een techniek om een geheim zeer lang te kunnen bewaren, zelfs als servers door aanvallers kunnen worden gelezen of van malafide software worden voorzien. Het geheim wordt hiervoor over meerdere servers verdeeld met (standaard) SECRET SHARING technieken, maar deze worden VERIFYABLE gemaakt zodat de integriteit van de shares publiek controleerbaar wordt. Vervolgens bekijken we de protocollen die nodig zijn voor een periodieke (bv. wekelijkse) herberekening van shares. Bedoeling hiervan is dat het geheim opnieuw wordt verdeeld, zodat gestolen shares van een zekere week niet gebruikt kunnen worden in combinatie met shares die in een andere week zijn gestolen. Dit is een heel delicate kwestie, want er moet op subtiele veiligheidseisen worden gelet, en tijdens de herberekening mag op geen enkel moment de kennis van het geheim in te weinig servers geconcentreerd zijn. Als de tijd het toelaat bekijken we ook nog een toepassing van deze techniek waar we niet vrolijk van worden: cryptovirussen die bestanden op de harde schijf encrypten om een losgeld af te persen.

    Friday November 5, 1999, 13:30 - 16:00


    We consider a single-machine on-line scheduling problem where jobs arrive over time. A set of independent jobs has to be scheduled on a single machine. Each job becomes available at its release date, which is not known in advance, and its characteristics, i.e., processing requirement and delivery time, become known at its arrival. The objective is to minimize the time by which all jobs have been delivered. In our model preemption is not allowed, but we are allowed to restart a job, that is, the processing of a job can be broken off to have the machine available to process an urgent job, but the time already spent on processing this interrupted job is considered to be lost. We propose an on-line algorithm and show that its performance bound is equal to 1.5, which matches a known lower bound due to Vestjens. For the same problem without restarts the optimal worst-case bound is known to be equal to $(\sqrt{5}+1)/2 \approx 1.61803$; this is the first example of a situation in which the possibility of applying restarts reduces the worst-case performance bound.

    Friday November 19 1999, 11:00 - 13:00


    We discuss the following conjecture: for any 2-connected planar graph of pathwidth $k$ the pathwidth of its geometric dual is at most $k+1$. We show how to prove the conjecture for graphs with maximum vertex degree 3.

    Friday December 3 1999, 11:00 - 13:00


    I will give an overview of the route planning algorithm of the CARiN car navigation system. I will do so by showing how a well-known shortest path algorithm can be changed into a route planning algorithm that efficiently constructs high-quality routes using the limited means of a car navigation system.

    Friday December 10 1999, 11:00 - 13:00


    A frequency assignment problem considers a set of transmitter stations that are to be assigned frequencies from a given set. These frequencies might interfere with frequencies from neighboring stations, resulting in loss of quality of the transmission lines. The objective is to assign frequencies with a minimum total loss of quality.

    The problem is modeled with a graph of vertices (stations) and edges (if choices of frequencies have interference, for the endvertices of an edge. The amount of interference for each choice of combinations is measured with a penalty.

    We can formulate this problem as a binary constraint satisfaction problem. A first technique to solve this problem is by use of a cutting plane algorithm (in a branch-and-cut framework). We present valid inequalities, lifting theorems and computational results. A second technique makes use of a structural property of the graph, namely its tree width. By use of dynamic programming techniques this can be used to solve some of the instances we have. A third technique is also based an a structural property but now on the penalty of the edges. The corresponding algorithm leads to even better results than the previous techniques.

    Friday December 17 1999, 11:00 - 13:00


    Job heeft me gevraagd de eeuw op een bij UCOS passende wijze af te sluiten en daarom blijft wat we precies gaan doen, behalve dat het met grafen en (natuurlijk) gedistribueerde algoritmen te maken heeft, nog een verrassing. Er wordt gerapporteerd over werk dat ik vorige maand in Bordeaux met Yves Metivier heb gedaan. Als voorbereiding moeten alle deelnemers iets bedenken dat met een feest te maken heeft. Ik hoop dat jullie allemaal komen!


    Friday January 28 2000, 11:00 - 13:00


    We study the problem of scheduling jobs online, where we may choose to serve any job partially in order to use the machines more efficiently. For every job, the scheduler must decide how long it will run that job before it starts: preemption is not allowed. We analyze the competitive performance of algorithms for jobs with varying sizes and for unit-sized jobs.

    Friday February 11 2000, 11:00 - 13:00


    Many analysis, planning and design problems arising in economics, engineering and in mathematics, can be cast, or recast, in the form of a convex programming problem, i.e., minimizing a convex objective subject to convex constraints.

    Nesterov and Nemirovskii have extended interior-point algorithms for linear programming (such as Karmarkar's) to handle convex problems. As a result a broad class of convex programming problems can now be solved by using interior-point algorithms in a number of steps that depends polynomial on the problem size. In this class the semidefinite programming problems form a very interesting subclass, from a theoretical, a practical point of view, and an applications minded view. In the last few years several impressive applications of semidefinite programming have been obtained in various fields such as, stability in control and system theory, structural optimization, combinatorial optimization, geometry, and linear algebra.

    "Real-life" optimization problems are usually high dimensional and it takes much computational effort to solve them. My research focuses on identifying faster ways solving such problems by means of stable numerical methods, in the interior-point algorithms.

    Friday February 18 2000, 11:00 - 13:00


    Let us consider a submodular function z defined on the Boolean hypercube to which we can apply a classic theorem of Cherenin that z is quasi-concave on any chain that intersects a local maxima component. This result enables a clearer understanding of the structure of a submodular function in terms of components defined by local maxima.We show that if Cherenin's Dichotomy Algorithm (CDA) finds a global maximum then the given submodular function has exactly one strict component. We proposed a generalization of the CDA which is useful in two respects. Firstly it is suitable for use in epsilon-optimal procedures which obtain an approximate global maximum to within specified bounds. Secondly our generalization allows the derivation of alternatives to the so called prime excluding rules by which we are able to discard subintervals of smaller cardinality than the one-half of the original interval. We illustrate the working of our algorithm by means of the Simple Plant Location Problem. Computer experiments on random instances of the Quadratic Cost Partition Problem show an improvement upon published results from Lee, Nemhauser, Wang (1996), particularly when the data correspond to nonsparse graphs.


    [1] B. Goldengorin, G. Sierksma, G. A. Tijssen, M. Tso. The Data-Correcting Algorithm for Minimization of Supermodular Functions. Management Science 1999 45(11) 1539-1551.
    [2] B. Goldengorin, G. A. Tijssen.The Maximization of Submodular Functions: Old and New Proofs for the Correctness of the Dichotomy Algorithm (submitted to Mathematics of OR).
    [3] B. Goldengorin. Correcting Algorithm for the Solution of Some Discrete Optimization Problems, Soviet Math. Dokl.1983 27(3) 620-623.
    [4] H. Lee, G.L. Nemhauser, Y. Wang. Maximizing a Submodular Function by Integer Programming: Polyhedral Results for the Quadratic Case. European J. Oper. Res. 94 154-156.

    All papers are available:

    Friday March 3 2000, 11:00 - 13:00


    We present an overview of results on a graph parameter introduced by Yves Colin de Verdière some 10 years ago. This parameter, a natural number µ(G) associated with a graph G, has an algebraic definition, but seems to be a measure of topological complexity. An interesting property of µ is that it is minor monotone, i.e. if G has H as a minor, then µ(H) is at most µ(G).

    Following this general introduction to µ we will present in more detail some results about the relationship between µ and geometric representations of a graph.

    Friday March 10 2000, 11:00 - 13:00


    A merchant is a person who travels around in a vehicle of fixed capacity, and makes a living by buying goods at places where they are cheap and selling them at places where he can make a profit. A merchant subtour is a (directed) closed walk of a merchant starting and ending at a given place, together with a description of the load of the vehicle along each traversed arc. Travelling is not for free, and therefore we assume the merchant has to pay a cost that is linear in the distance he travels. This talk addresses the problem of finding a minimum cost merchant subtour where the cost of a merchant subtour equals the travel cost minus the profit made by trading along the way. We call this problem the merchant subtour problem (MSP).

    The MSP models certain aspects of a multi-depot vehicle routing problem with split deliveries that occurs at Van Gend & Loos, The Netherlands. Apart from this, the MSP is related to several problems that are reported on in the literature. It has a very rich structure, making it an interesting problem to study in its own right. We consider the computational complexity of the MSP, a special case that is solvable in polynomial time, heuristic algorithms and an optimization algorithm.

    Friday March 24 2000, 11:00 - 13:00


    Een lambda-kleuring van een graaf beeldt elke knoop in een graaf af op een niet-negatieve integer, zodat grenzende knopen minstens verschil 2 hebben, en knopen met afstand 2 ongelijke kleuren hebben. Gezocht wordt naar een lambda-kleuring met zo klein mogelijke maximale waarde. Dit probleem modelleert een toepassing in frekwentie-toewijzing van radio-kanalen. In dit artikel geven we een aantal bovengrenzen (en enkele ondergrenzen) voor het aantal kleuren dat nodig is op bepaalde klassen van grafen, waaronder planaire grafen en grafen met begrensde boombreedt. Ook bewijzen we dat het probleem NP-moeilijk is voor planaire grafen. Dit werk is gedaan samen met Ton Kloks, Jan van Leeuwen en Richard Tan.

    Friday March 31 2000, 11:00 - 13:00


    Since news needs to be timely, the time between production and distribution of a newspaper should be as short as possible. Therefore it is not possible to produce newspapers in advance and maintain a stock of finished newspapers. The processes of production and distribution are therefore tightly coupled in the newspaper industry. We investigated strategies for scheduling production and distribution and applied them in a case for Brabant Pers.

    Friday April 28 2000, 11:00 - 13:00


    A spanning tree of a graph G is a set of edges of G containing a unique path between every pair of vertices of G. An edge cover of G is a set of edges of G covering all vertices of G (an edge `covers' both its endpoints). We introduce the concept of an S-T connector as a common generalization of an edge cover in a bipartite graph and a spanning subgraph (set of edges containing a spanning tree) in an arbitrary graph. Given a graph G=(V,E) and a partition {S,T} of its vertex set V an S-T connector is a subset F of the edge set E such that every component of the graph (V,F) intersects both S and T (equivalently, F contains a v-T path for every v \in S, and a S-v path for every v \in T).

    Both the problem of finding a maximum number of disjoint spanning trees in a graph and the problem of finding a maximum number of disjoint edge covers in a bipartite graph can be solved in polynomial time. In this talk, we explain how the algorithms for these two packing problems can be combined to obtain an algorithm for packing S-T connectors.

    We derive a min-max relation for the maximum number of S-T connectors in a graph. We also sketch how the result can be viewed as a special case of a packing theorem for matroids.

    Friday May 26 2000, 11:00 - 13:00


    We consider the problem of maximizing the number of jobs completed by their deadline in an online single processor system where the jobs are preemptable and have release times. So in the standard three field scheduling notation, this is the online version of the problem 1 | r_i; pmtn | sum (1 - U_i). We present a deterministic algorithm Lax, and show that for every instance I, it is the case that either Lax, or the well-known deterministic algorithm SRPT (Shortest Remaining Processing Time), is constant competitive on I. An immediate consequence of this result is a constant competitive randomized algorithm for this problem. It is known that no constant competitive deterministic algorithm exists for this problem. This is the first time that this phenomenon, the randomized competitive ratio is constant in spite of the fact that the deterministic competitive ratio is nonconstant, has been demonstrated to occur in a natural online problem. This result is also a first step toward determining how an online scheduler can use additional processors in a real-time setting to achieve competitiveness.

    This is joint work with Bala Kalyanasundaram.

    Tuesday June 6 2000, 15:00 - 17:00


    We consider a vehicle routing problem in which we have at our disposal a fleet of trucks that are stationed at several depots, and in which we are given a set of customers with an integral demand for different commodities. Each commodity originates from one customer and is destined for another customer. Goods of each commodity may be split into integral amounts for transportation. Assuming that we know the cost of driving from one place to another, the problem is to transport all demand using the available trucks, minimising the total cost of driving.

    We develop a heuristic for the problem that is based on LP column generation. On medium-size problem instances with real-life characteristics our computational study shows that the algorithm is capable of finding solutions that are on average within a factor of 1.65 from optimal.

    Friday June 23 2000, 11:00 - 13:00


    Slot allocation is concerned with the assignment of departure slots to all flights departing from airports in a given area. This assignment has to ensure that overload in en-route control sectors and on runways is avoided. For Western Europe, slot allocation is performed by the Central Flow Management Unit of EUROCONTROL. It has been shown that the current method can significantly be improved by applying exact optimisation.

    We discuss a solution method for a basic version of the European slot allocation problem. The approach is based on integer linear programming and column generation. Computational results are encouraging, because they indicate both possibilities for real-time applications and nearly optimal solutions.

    Our current research on slot allocation focuses on Collaborative Decision Making (CDM). Key issue in CDM is improvement of the information exchange and co-operation between different actors in air traffic handling (Air Traffic Control, airlines, airport authorities). We briefly discuss possible applications of CDM in slot allocation.

    Previous Your Remarks