| [home] - [up] |
Abstract: A kinetic data structure (KDS) is a data structure that maintains a certain attribute - the convex hull, for instance - of a set of continuously moving objects. In most KDSs, the attribute under consideration is uniquely defined, and it is maintained explicitly. In such cases one can obtain a lower bound on the maintenance cost (the number of events the KDS has to process) by proving a lower bound on the number of changes the attribute can undergo. In other cases, e.g. when one wants to maintain a binary space partition of a set of moving objects, the attribute is not uniquely defined, and proving lower bounds becomes more difficult. Finally, one can consider KDSs that do not explicitly maintain a certain attribute of the given set, but only a data structure that can answer queries about the set. In such cases, there will be a trade-off between the maintenance cost and query time. In this talk I will discuss lower bounds for some problems of each of these three types.
Colloquium - 16:00
Abstract: A standard tool to attack NP-hard problems is local search. In this case the problem is resource constrained project scheduling. An instance is given by a set of jobs with positive processing times, a directed graph describing the precedence constraints, and a set of forbidden sets representing the resource constraints. The problem is to find a feasible schedule that minimizes the project completion time, the so-called makespan.
To resolve the resource conflicts a waiting job is chosen for every forbidden set, which has to wait for the completion of at least one of the other jobs in the set. This selection can be represented by an AND/OR-network. For an AND/OR-network, there exists a unique earliest start schedule which minimizes the makespan for this selection and can be computed in polynomial time.
We will consider a canonical neighborhood on the set of all AND/OR-networks for a given instance of the scheduling problem. As a main result we will show that the set of feasible networks is connected with respect to the neighborhood relation, thus it is possible to find an optimum schedule by just considering feasible networks. We will also have a short discussion on search strategies in this neighborhood relation.