## Seminars already given (chronological order)

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

### 1995

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


Topic:   The Use of Linear Programming in Combinatorial Optimization
Speaker: Karen Aardal, Department of Computer Science,
Utrecht University


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


Topic:   A Survey of Recent Developments in Linear Optimization
Speaker: C. Roos, Department of SSOR, TU Delft 

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

 Topic:   Linear and Integer Programming: Complexity Aspects
and Special Cases
Speaker: Marinus Veldhorst, Department of Computer Science,
Utrecht University


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


Topic:   Introduction to Polyhedral Combinatorics
Speaker: Karen Aardal, Department of Computer Science,
Utrecht University


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


Topic:   Polyhedral Combinatorics, Part II
Speaker: Karen Aardal, Department of Computer Science,
Utrecht University


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


Topic:   Finding Tours in the TSP
Speaker: W. Cook, Institute for Econometrics and Operations Research,
Bonn University

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.

#### Abstract

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


Topic:   On Approximation Algorithms for the TSP
Speaker: Jan van Leeuwen, Department of Computer Science,
Utrecht University



#### Abstract

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


Topic:   Solving the Frequency Assignment Problem
Speaker: Karen Aardal, Department of Computer Science,
Utrecht University



#### Abstract

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.

### 1996

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


Topic 1:    Introduction to Vehicle Routing Algorithms
Topic 2:    Packing a Bin with Boxes
Speaker 1:  Goos Kant, Utrecht University and ORTEC Consultants.
Speaker 2:  Bram Verweij, ORTEC Consultants


#### 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:
• Sequential insertion algorithm
• Parallel insertion algorithm
• Savings algorithm
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


Speaker:    Jacques Verriet, Department of Computer Science,
Utrecht University



#### Abstract

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


Topic:      Vaste Parameter Complexiteit
Speaker:    Hans Bodlaender, Department of Computer Science,
Utrecht University



#### Abstract

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


Topic:      Approximation Algorithms for MAX CUT and MAX 2SAT
Speaker:    Karen Aardal, Department of Computer Science,
Utrecht University


#### Abstract

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


Topic:      Approximation
Speaker:    Marinus Veldhorst, Department of Computer Science,
Utrecht University



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


Topic:      Approximations in Connectivity Certificates and Max Flow
Speaker:    Gerard Tel, Department of Computer Science,
Utrecht University



#### Abstract

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


Topic:      EIDMA Mini-course: Approximation Algorithms
Speaker:    David P. Wiliamson, IBM T.J. Watson Research Center



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


Topic:      Constraint satisfaction (tentative title)
Speaker:    Dimitris Thilikos, Department of Computer Science,
Utrecht University



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


Topic:      Unexplored algorithms for integer programming
Speaker:    Karen Aardal, Department of Computer Science,
Utrecht University



#### Abstract

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


Topic:      Applications from Telecommunication
Speaker:    Stan van Hoesel, Maastricht



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


Topic:   Designing Private Line Networks (.ps-version)
Speaker: Laurence Wolsey, Universit'e Catholique de Louvain,
Louvain-la-Neuve, Belgium


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


Topic:   Approximation Algorithms for Scheduling Problems
Speaker: Jan Karel Lenstra, Department of Mathematics and Computing Science,
Eindhoven University of Technology



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

 Topic:   On-line algorithms for Scheduling Problems
Speaker: Arjen Vestjens, Department of Mathematics and Computing Science,
Eindhoven University of Technology


#### Abstract

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

 Topic:   Beautiful and Fast: New Minimum Cut Algorithms
Speaker: Andrew V. Goldberg, NEC Research Institute, Princeton NJ, USA


#### Abstract

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 http://www.neci.nj.nec.com/homepages/avg.html. It is joint work with Chandra Chekuri, David Karger, Matt Levine, and Cliff Stein.

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

 Topic:   Real-life Vehicle Routing Problems
Speaker: Goos Kant, ORTEC Consultants, B.V. and
Department of Computer Science, Utrecht University


#### Abstract

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:

• Applying Savings with more restrictions. We present techniques how to adapt the well known Savings Heuristic for the VRP such that it can cope with different restrictions.
• Scheduling and Vehicle Routing. We consider the problem of vehicle routing between a number of sites, where only one vehicle at a time is allowed to (un)load at a location.
• HUB-problem. We consider the problem of having a number of locations with a matrix with amounts, to be transported between them, and a number of side-constraints.
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

 Topic:   A Fully Polynomial Approximation Scheme for Single Item
Capacitated Economic Lot Sizing with Concave Costs
Speaker: Albert Wagelmans, Econometric Institute, Erasmus University


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

 Topic:   ABACUS - A Branch-And-CUt System
Speaker: Stefan Thienel, Universität zu Köln


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

 Topic:   Test sets in Integer Programming
Speaker: Robert Weismantel, ZIB-Berlin


#### Abstract

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

 Topic:   Scheduling tree-structured programs in
the LogP model
Speaker: Jacques Verriet, Department of Computer Science,


#### Abstract

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

 Topic:   Integrated Vehicle and Crew Scheduling in Public
Transport
Speaker: Richard Freling, Econometrisch Instituut, Erasmus
Universiteit Rotterdam, and ORTEC Consultants bv


#### Abstract

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

 Topic:   Approximation algorithms for location problems
Speaker: Karen Aardal, Department of Computer Science,
Utrecht University


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

 Topic:   Graaf reductie
Speaker: Hans L. Bodlaender, Department of Computer Science,
Utrecht University


                 *** EXTRA SEMINAR ***



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

 Topic:   Triangulating colored graphs and Indo-European
Speaker: Tandy Warnow, Department of Computer and
Information Science, University of Pennsylvania



#### Abstract

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

 Topic:   EIDMA Minocourse "Computational Combinatorial Optimization"
Speaker: W. Cook, Rice University, USA


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

 Topic:   10-jarig jubileum "Landelijk Netwerk Matematische
Besliskunde"
Room:    Lorentz Center, RU Leiden


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

 Topic:   Operations Research and Finance
Speaker: Marc Salomon, Rabobank and KUB


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

 Topic:   Discussion
Speaker: Various


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

 Topic:   Approximating Total Flow Time on Parallel Machines
Speaker: Stefano Leonardi, MPI, Saarbruecken


#### Abstract

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

 Topic:       Discussion of Hochbaum's book
Responsible: Jacques Verriet


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

 Topic:   Enkele problemen uit de statistische beveiliging
Speaker: Leon Willenborg, Sector Statistische Methoden
Centraal Bureau voor de Statistiek, Voorburg


#### Abstract

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

 Topic:       Discussion of Hochbaum's book
Responsible: Bram Verweij


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

 Topic:       Discussion of Hochbaum's book
Responsible: Bram Verweij


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

 Topic 1:       An algorithm for solving a diophantine equation
with bounds on the variables
Speaker 1:     Karen Aardal

Topic 2:       Routing problems in practice
Speaker 2:     Goos Kant, ORTEC Consultants b.v.



### 1998

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


Topic:   Discussion Hochbaum's book
Speaker: Various


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


Topic:   On an integer multicommodity flow problem from the
airplane industry
Speaker: Bram Verweij


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


Topic:   Non-approximability results for scheduling problems
with minsum criteria
Speaker: Petra Schuurman


#### Abstract

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

 Topic:       Hochbaum's book, Chapter 5
Responsible: Hans Bodlaender, Department of Computer Science,
Utrecht University


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

 Topic:       Hochbaum's book, Chapter 5 (cont.)
Responsible: Hans Bodlaender, Department of Computer Science,
Utrecht University


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

 Topic:       Cryptography
Responsible: Gerard Tel, Department of Computer Science,
Utrecht University


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

 Topic:       Hoochbaum's book, Chapter 6
Responsible: Marinus Veldhorst, Department of Computer Science,
Utrecht University


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

 Topic:       Workshop "Non-standard methods for IP"
Organizers:  Karen Aardal and Laurence Wolsey,
Department of Computer Science,
Utrecht University


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

 Topic:       Single Machine and Labour Constrained Scheduling
(starting from Chapter 1, Section 7 of Hochbaum)
Speaker:     Laurence Wolsey, Department of Computer Science,
Utrecht University, and C.O.R.E., Louvain-la-Neuve,
Belgium


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

 Topic:       Hoochbaum's book, Chapter 6 (cont.)
Responsible: Marinus Veldhorst, Department of Computer Science,
Utrecht University


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

 Topics:      1: Threshold schemes in cryptography
2: An example of quantum computation
Speaker:     Dimitrios Thilikos, Department of Computer Science,
Utrecht University


#### 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


Topic:   A Communication Optimal 3-Edge-Connected Component
Algorithm
Speaker: Esther Jennings, Technion, Israel.


#### Abstract

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


Topic:   Carrying an Object under Distributed Control
Speaker: Masafumi Yamashita, Kyushu University, Japan



#### Abstract

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


Topic:   Optimization in practice
Speaker: Babette de Fluiter, CQM.



#### Abstract

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


Topic:   Sorteren, soms sneller
Speaker: Jop Sibeyn, Max-Planck-Institut für Informatik, Saarbrücken



#### Abstract

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.

### 1999

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


Topic:   An Optimization Algorithm for Maximum Independent Set
with Applications in Map Labelling
Speaker: Bram Verweij



#### Abstract

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


Topic:   Test sets for integer programs
Speaker: Herbert E. Scarf, Yale University.



#### Abstract

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


Topic:   On-line single server dial-a-ride problems
Speaker: Leen Stougie, Technische Universiteit Eindhoven.



#### Abstract

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


Topic:   Market Split and Basis Reduction
Speaker: Job Smeltink, Utrecht University.



#### Abstract

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


Topic:   Minimalisering met behulp van positionele completeringstijden
Speaker: Han Hoogeveen, Utrecht University.



#### Abstract

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


Topic:   Network Design Approximation: the Reinforcement Problem
Speaker: Lisa Fleischer, CORE and Columbia University.



#### Abstract

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


Topic:   Operationele inzet van personeel: een case study
Speaker: Marinus Veldhorst, UU.



#### Abstract

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


Topic:   Point Labeling with Sliding Labels
Speaker: Tycho Strijk, UU.



#### Abstract

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


Topic:  Improved polynomial algorithm for scheduling with
release times and tails
Speaker: Nodari Vakhania, University of Morelos (Mexico)



#### Abstract

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


Topic:   A 3-approximation algorithm for the k-level uncapacitated
facility location problem
Room:    CGN C009, Uithof Campus
Speaker: Karen Aardal



#### Abstract

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

 Topic: Linkage Information Processing In Distribution Estimation Algorithms Room: CGN B205a, Uithof Campus Speaker: Peter Bosman

#### Abstract

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

 Topic: Minimizing Total Weighted Tardiness in a Generalized Job Shop Room: CGN B205a, Uithof Campus Speaker: Koen de Bontridder, Eindhoven University of Technology

#### Abstract

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

 Topic: Proactieve Veiligheid Room: CGN C009, Uithof Campus Speaker: Gerard Tel

#### Abstract

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

 Topic: Restarts can help in on-line scheduling Room: CGN C009, Uithof Campus Speaker: Han Hoogeveen

#### Abstract

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

 Topic: Pathwidth of planar graphs Room: CGN B205a, Uithof Campus Speaker: Fedor Fomin, St.Petersburg State University

#### Abstract

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

 Topic: Route planning in the CARiN system: Simple algorithms in a complex environment Room: CGN C006, Uithof Campus Speaker: Jacques Verriet, CQM

#### Abstract

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

 Topic: Development of exact algorithms for frequency assignment problems Room: CGN C006, Uithof Campus Speaker: Stan van Hoesel, Universiteit Maastricht

#### Abstract

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

 Topic: Bepalen de deelnemers zelf Room: CGN C006, Uithof Campus Speaker: Gerard Tel

#### Abstract

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!

### 2000

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

 Topic: Scheduling Jobs On-Line, Selecting the Execution Time in Advance Room: CGN C009, Uithof Campus Speaker: Rob van Stee, CWI

#### Abstract

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

 Topic: Subspace Methods in Large Scale Semidefinite Optimization Room: CGN C009, Uithof Campus Speaker: Mischja van Bossum, Universiteit Utrecht

#### Abstract

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

 Topic: Implicit Enumeration Algorithms for the Maximization of Submodular Functions Room: CGN C009, Uithof Campus Speaker: Boris Goldengorin, Department of Econometrics and Operations Research, Groningen University

#### Abstract

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.

References

[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.

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

 Topic: On a spectral graph invariant and geometric representations of graphs Room: CGN C009, Uithof Campus Speaker: Rudi Pendavingh, Technische Universiteit Eindhoven

#### Abstract

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

 Topic: The Merchant Subtour Problem Room: CGN C009, Uithof Campus Speaker: Bram Verweij

#### Abstract

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

 Topic: Lambda-kleuring Room: CGN C009, Uithof Campus Speaker: Hans Bodlaender

#### Abstract

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

 Topic: Planning of production and distribution in the newspaper industry Room: CGN C009, Uithof Campus Speaker: Geert Teeuwen of CQM

#### Abstract

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

 Topic: Packing connectors Room: CGN C009, Uithof Campus Speaker: Judith Keijsper of the University of Twente

#### Abstract

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

 Topic: Maximizing Job Completions Online Room: CGN C009, Uithof Campus Speaker: Kirk Pruhs, Department of Computer Science, University of Pittsburgh

#### Abstract

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

 Topic: Multi-depot Vehicle Routing with Integrally Split Deliveries Room: CGN C009, Uithof Campus Speaker: Bram Verweij

#### Abstract

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

 Topic: Slot allocation for flight departures Room: CGN C009, Uithof Campus Speaker: Marjan van den Akker of the National Aerospace Laboratory (NLR)

#### Abstract

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.