Tenth Workshop on Applied/Advanced Research
in Combinatorial Optimization

January 20, 2003

University of Southern Denmark, Odense, Room 99

Submitted abstracts:

The Strong Perfect Graph Theorem

Maria Chudnovsky, Princeton University, USA

A graph is called perfect if for every induced subgraph the size of its largest clique equals the minimum number of colors needed to color its vertices. In 1960's Claude Berge made a conjecture that has become one of the most well-known open problems in graph theory: any graph that contains no induced odd cycles of length greater than three or their complements is perfect. This conjecture is know as the Strong Perfect Graph Conjecture. We call graphs containing no induced odd cycles of length greater than three or their complements Berge graphs. A stronger conjecture was made recently by Conforti, Cornuejols and Vuskovic that any Berge graph either belongs to one of a few well understood basic classes or has a decomposition that can not occur in a minimal counterexample to Berge's Conjecture. In joint work with Neil Robertson, Paul Seymour and Robin Thomas we were able to prove this conjecture and consequently the Strong Perfect Graph Theorem. The fundamental question of finding a polynomial time recognition algorithm for perfect graphs has been reduced to finding an algorithm that detects whether a graph contains an odd hole or antihole. Recently we were able find such an algorithm, which is, in fact, independent of the proof of the SPGT.

Canonical Forms and Algorithms for Steiner Trees in Uniform Orientation Metrics

Martin Zachariasen, Copenhagen University, Denmark

We present some fundamental structural properties for minimum length networks (known as Steiner minimum trees) interconnecting a given set of points in an environment in which edge segments are restricted to $\lambda$ uniformly oriented directions. We show that the edge segments of any full component of such a tree contain a total of at most 4 directions if $\lambda$ is not a multiple of $3$, or 6 directions if $\lambda$ is a multiple of $3$. This result allows us to develop useful canonical forms for these full components. The structural properties of these Steiner minimum trees are then used to resolve an important open problem in the area: does there exist a polynomial-time algorithm for constructing a Steiner minimum tree, if the topology of the tree is known? We obtain a simple linear time algorithm for constructing a Steiner minimum tree for any given set of points and a given Steiner topology. Joint work with Marcus Brazil, Doreen A. Thomas and Jia F. Weng

Fully-Dynamic Two Dimensional Orthogonal Range and Line Segment Intersection Reporting in Logarithmic Time

Christian Worm Mortensen, IT-University, Denmark

We consider the two dimensional fully-dynamic orthogonal range reporting problem and the two dimensional fully-dynamic orthogonal line segment intersection reporting problem in the comparison model. We show that if $n$ is the number of stored elements, then these problems can be solved in worst case time $\Theta(\log n)$ plus time proportional to the size of the output pr.\ operation.

Perfectness is an Elusive Graph Property

Annegret Wagler, ZIB, Berlin, Germany

A graph property is called elusive (or evasive) if every algorithm for testing this property has to read in the worst case $n\choose 2$ entries of the adjacency matrix of the given graph. Several graph properties have been shown to be elusive, e.g. planarity (Best et al 1974), $k$-colorability (Bollobas 1978), 2-connectivity (Triesch 1982), or the membership in any minor closed family (Chakrabarti, Khot, Shi 2002) . A famous conjecture of Karp (1973) says that every non-trivial monotone graph property is elusive. We prove that a non-monotone but hereditary graph property is elusive: perfectness. Joint work with Stefan Hougardy, HU Berlin

Bounds for Seat Reservation Allowing One Seat Change

Joan BoyarUniversity of Southern Denmark

In the original Seat Reservation Problem, a train travels from a start station to an end station, stopping at a fixed number of stations. Passengers may attempt to make reservations at any point before they get on the train. The train has a fixed number of seats, and the seat reservation system attempts to maximize income. Since passengers must be assigned to seats when they buy their seat reservations, rather than after the system knows about all future requests for seat reservations, the problem is on-line. We consider a variant of the Seat Reservation Problem in which one seat change is allowed. A deterministic algorithm, Modified-Kierstead-Trotter, is proposed for this variant and shown to seat all passengers if the optimal off-line algorithm could have accommodated them with half as many seats. In contrast, for the original Seat Reservation Problem, Kierstead and Trotter showed that if the optimal off-line algorithm requires more than 1/3 as many seats as the algorith has, then there are sequences which will cause the algorithm to reject some requests. We prove an upper bound for any deterministic algorithm for the variant allowing one seat change, showing that if the optimal off-line algorithm requires more than 2/3 as many seats as the algorithm has, then there are sequences which will cause the algorithm to reject some requests. This is joint work with Susan Krarup, Kim S. Larsen, and Morten N. Nielsen.

The Relative Worst Order Ratio for On-Line Algorithms

Lene Monrad Favrholdt, DIKU, Denmark,

We consider a new measure for the quality of on-line algorithms, the relative worst order ratio, using ideas from the Max/Max ratio and from the random order ratio. The new ratio is used to compare on-line algorithms directly by taking the ratio of their performances on their respective worst orderings of a worst-case sequence. Two variants of the bin packing problem are considered: the Classical Bin Packing Problem and the Dual Bin Packing Problem. Standard algorithms are compared using this new measure. For the Classical Bin Packing Problem, all algorithms considered can be linearly ordered by this measure. For the Dual Bin Packing problem some algorithms are found to be incomparable under this new measure, i.e., there are sequences where the one algorithm does better and sequences where the other does better. Many of the results obtained here are consistent with those previously obtained with the competitive ratio or the competitive ratio on accommodating sequences, but new separations and easier results are also shown to be possible with the relative worst order ratio. Joint work with Joan Boyar

Hierarchical Network Design Using Simulated Annealing

Tommy Thomadsen, IMM, The Techinical University of Denmark

Extensive research has taken place in network design and backbone network design in particular. Most research divides the design process into two phases (I) Design of topology and (II) routing of traffic. Backbone networks are for historical and/or administrative reasons divided into hierarchies. We will present a model of hierarchical networks which defines the hierarchical topology and includes the routing of traffic. The hierarchical network problem is defined as that of finding the least cost hierarchical network able to meet the demand given by an origin-destination demand matrix. The problem is solved by an integrated approach using simulated annealing for the topology design and a greedy algorithm for the routing of the network traffic.

Decentralized Ground Staff Scheduling

Martin Dedenroth S\o rensen and Jens Clausen IMM, The Techinical University of Denmark

Typically, ground staff is centrally planned in an airport. We consider a decentralized approach, where the terminal in question is decided into zones consisting of stands geographically next to each other. Staff is assigned to work in one zone only, and the staff scheduling is planned decentralized for each zone. The workload in a particular zone depends on the flights operated from that zone, so the allocation of aircraft to stands is a component of the problem. A mathematical model of the problem is proposed, which integrates the stand allocation and the staff scheduling. A heuristic solution method is developed and applied to a real case from British airways, London Heathrow Airport. The case study shows that the problem as may be expected contains various trade-offs between cost and quality of the solution. Also, the robustness of the solution in the context of disruptions is addressed.

Subexponential-time Algorithms for Maximum Independent Set and Related Problems on Box Graphs

Martin Wahlen Lund University, Sweden

A box graph is an intersection graph of orthogonal rectangles in the plane. We consider such basic combinatorial problems on box graphs as maximum independent set and vertex cover. We show that they can be exactly solved in subexponential time, more precisely, in time $2^{O(\sqrt n \log n)},$ by applying Miller's simple cycle planar separator theorem \cite{Mil84}.