Oct 30 - Nov 2, 2000 RIMS, Kyoto University, Kyoto, Japan Sponsored by Research Institute for Mathematical Science, Kyoto University, and Grants-in-aid for Scientific Research of Priority Areas, Ministry of Education, Science, Sports and Culture of Japan Invited Talks: Octber 30 13:00-14:00 Stefan Naeher (Universitaet Trier) A Generic Tool for Interactive Visualization of Geometric Algorithms (GeoWin) Abstract: The visualization of algorithms and data structures is very important in the design and implementation of algorithms, especially in the area of compuational geometry. It is useful for the presentation of results, teaching, debugging and testing, the design of worst-case or degenerate inputs, and it often helps to discover problems and find new solutions. In this paper we present {\em GeoWin} a \CC data type for the visualization and manipulation of geometric objects and show how to use it in the presentation and animation of geometric algorithms. By the use of templates and object-oriented programming, GeoWin is a {\em generic} visualization and animation tool that can be used for arbitrary types of geometric objects, as long as they provide as small set of basic operations. This makes GeoWin independent from any concrete geometric kernel. Currently, it is used as visualization tool for both the CGAL and LEDA projects. ------------------------------------------------------------------------------ 14:00-15:00 Tamal Krishna Dey (The Ohio State University) Detecting Undersampling in Surface Reconstruction: Theory and Experiments Abstract: Current surface reconstruction algorithms perform satisfactorily on well-sampled, smooth surfaces without boundaries. However, these algorithms have severe problems when met with undersampling. Cases of undersampling is prevalant in real data since often they sample a part of the boundary of an object, or are derived from a nonsmooth surface. In this paper we present an algorithm to detect the regions of undersampling. This information can be used to reconstruct surfaces with boundaries, and also to detect the locality of sharp features in nonsmooth surfaces. We report the effectiveness of the algorithm with a number of experimental results. Theoretically, we justify the algorithm with some mild assumptions that are valid for most practical data. ------------------------------------------------------------------------------ 15:30-16:30 Mario Szegedy (Rutgers University) CKit: A Preprocessor for Algorithmic Experiments Abstract: CKit is a general purpose preprocessor that I originally designed for and tested in code theoretical and combinatorial experiments. In this article I explore the most important features of this preprocessor, describe its design principles, and illustrate its novel use with examples. I introduce the notions of {\em macros with associative power} and {\em lexical inheritance}, and give examples to their use in CKit. ------------------------------------------------------------------------------ 16:30-17:30 Wolfgang Slany (Technische Universitaet Wien) Theory and Practice of Shift Scheduling Abstract: Generating high-quality schedules for a rotating workforce is a critical task in all situations where a certain staffing level must be guaranteed, such as in industrial plants, hospitals, or airline companies. Results from ergonomics indicate that shift schedules have a profound impact on the health and satisfaction of employees as well as on their performance at work. Moreover, shift schedules must satisfy legal requirements and should also meet the objectives of the employing organization. Shift scheduling comprises several sub-problems such as the allocation of workers to shifts or the design of the shifts themselves that present interesting challenges both from practical (our algorithms are sold in a successful commercial package) as well as theoretical (hardness, approximability) viewpoints. I will describe some of our results in both areas. In particular, we studied in depth the (non-)approximability of the shift design problem, a network flow variant that has many applications beyond shift scheduling. ------------------------------------------------------------------------------ October 31 9:30-10:30 Ingo Wegener (University of Dortmund) On the Design and Analysis of Evolutionary Algorithms Abstract: Evolutionary algorithms are randomized search heuristics for the optimization of functions $f$. They have applications if time, money or skills are not available to design a problem-specific algorithm or in black box optimization where $f$ is not known and information on $f$ can only be gained by sampling. Many experiments with evolutionary algorithms have been performed but only few theoretical results are known. Such a theory can be built up only by people with experience in the analysis of algorithms. Here a simple evolutionary algorithm for the optimization of functions $f:\{0,1\}^n \to {I\!\!R}$ is investigated. The algorithm works with population size 1 and mutations only. Most results can be generalized to larger populations. It is shown that such algorithms cannot optimize all unimodal functions efficiently. However, linear functions can be optimized in an expected time of $O(n \log n)$. The effect of varying mutation probabilities is studied. Finally, the first example is presented where it is proven that uniform crossover can improve the expected runtime from superpolynomial to polynomial and also the first example where it is proven that 1-point-crossover can improve the expected runtime from exponential to polynomial. (Some of the results are obtained together with Stefan Droste and Thomas Jansen). ------------------------------------------------------------------------------ 10:30-11:30 Oscar H. Ibarra (University of California) Some Complexity Issues in Parallel Computing Abstract: We give an overview of the computational complexity of linear and meshconnected cellular arrays with respect to well known models of sequential and parallel computation. We discuss one-way communication versus two-way communication, serial input versus parallel input, and space-efficient simulations. In particular, we look at the parallel complexity of cellular arrays in terms of the PRAM theory and its implications, e.g., to the parallel complexity of recurrence equations and loops. We also point out some important and fundamental open problems that remain unresolved. Next, we investigate the solvability of some reachability and safety problems concerning machines operating in parallel and cite some possible applications. Finally, we briefly discuss the complexity of the "commutativity analysis" technique that is used in the areas of parallel computing and parallelizing compilers. Keywords: cellular array, computational complexity, P-complete, parallel complexity, recurrence equations, reachability, safety, commutativity analysis. ------------------------------------------------------------------------------ November 1 9:30-10:30 James Ferdinand Geelen (University of Waterloo) An Algebraic Approach to Matching Problems Abstract: In Tutte's seminal paper on matching, he associates a skew-symmetric matrix with a graph; this matrix is now known as {\em Tutte matrix}. The rank of the Tutte matrix is exactly twice the size of a maximum matching in the graph. This formulation easily leads to an efficient randomized algorithm for matching. The Tutte matrix is also useful in obtaining a min-max theorem and an efficient deterministic algorithm. We review these results and look at similar formulations of other problems; namedly, linear matroid intersection, linear matroid parity, pth matching, and matching forests. ------------------------------------------------------------------------------ 10:30-11:30 David Williamson (IBM T. J. Watson Research Center) A Short Primer on the Primal-Dual Method for Approximation Algorithms Abstract: The primal-dual method is a well-known tool used in the design of algorithms for problems in combinatorial optimization. Typically it is used for problems whose solution can be characterized by linear programs (for example, shortest paths, network flows, bipartite matchings). However, in the last decade a wealth of results has shown that a modified version of the method is also useful for designing approximation algorithms for a wide variety of NP-hard optimization problems. An approximation algorithm is one that runs in polynomial time and produces a solution whose value is within some factor of the optimal solution. The primal-dual method has been shown to give good approximation algorithms for the set cover problem, the vertex cover problem, network design problems, feedback vertex set problems, the uncapacitated facility location problem, the k-median problem, and others. Additionally, experimental results show that the method results in practical heuristics, whose solution values are typically quite close to the value of the optimal. In this talk, I will review the primal-dual method for approximation algorithms and some interesting results that have been derived from it. ------------------------------------------------------------------------------ 13:00-14:00 Celso Ribeiro (Catholic University of Rio de Janeiro) A Hybrid GRASP with Perturbations and Adaptive Path-Relinking for the Steiner Problem in Graphs Abstract: We Propose and describe a hybrid GRASP with weight perturbations and adaptive path-relinking heuristic (HGP-PR) for the Steiner problem in graphs. In this multi-start approach, the greedy randomized construction phase of a GRASP is replaced by the combination of several construction heuristics with a weight perturbation strategy that combines intensification and diversification elements, adn in a strategic oscillation approach. The improvement phase circularly explores two different local search strategies: the first uses a node-based neighborhood for local search, while the second used a key-path-based neighborhood. An adaptive path-relinking technique is applied to a set of elite solutions as a post-optimization strategy. Computational experiments on a large set of benchmark problems of three dirrerent classes are reported. We first illustrate the effectiveness of preprocessing procedures for seceral classesof test problems. Next, We present computational results illustrating the contribution of each algorithmic feature to the robustness of the complete algorithm. Finally, we show that our algorithm outperforms other heuristics in the literature, obtaining consistently better or comparably good solutions for alll calsses of test problems. ------------------------------------------------------------------------------ 14:00-15:00 Ibrahim Osman (American University of Beirut) Metaheuristics: A general framework Abstract: The most successful meta-heuristics are briefly reviewed with their associated components. A unified-meta-heuristic framework will be presented. It will be shown how the existing metaheuristics can fit into the presented framework. In addition, it also invites extra research into desiging new innovative and unexplored meta-heuristics. Finally we conclude by highlighting current trends and future research directions in this active area of the science of heuristics. ------------------------------------------------------------------------------ November 2 9:30-10:30 Shay Kutten (Faculty of Industrial Engineering and Management, Technion, Israel) On Time Adaptivity and Stabilization Abstract: We study the scenario where a transient fault hit a minority of the nodes in a distributed system by corrupting their state. The notion of {\em time adaptive}, or of {\em fault locality} were introduced to take advantage of the fact that the number of faults in such realistic scenarios may be small. A stabilizing distributed protocol is called \emph{adaptive} if its recovery time from a state-corrupting fault is proportional to the number of processors hit by the fault, rather than to the total number of nodes. We describe time adaptive protocols, and upper and lower bound for their stabilization time, and their fault resilience. We describe basic problems, both in the static case, and in the interactive case, such that more general problems can be reduced to them. We then solve these problems optimally. We describe the main techniques, as well as the new definitions, such as that of the amount of fault resilience that can be obtained, the different kind of stabilization (state stabilization versus output stabilization), and the additional desirable properties for such protocols. This area is rather new, and a lot of addition research is still needed. ------------------------------------------------------------------------------ 10:30-11:30 Gerhard Woeginger (Technical University Graz) Preemptive Scheduling with Rejection Abstract: We consider the problem of preemptively scheduling a set of $n$ jobs on $m$ (identical, uniformly related, or unrelated) parallel machines. The scheduler may reject a subset of the jobs and thereby incur job-dependent penalties for each rejected job, and he must construct a schedule for the remaining jobs so as to optimize the preemptive makespan on the $m$ machines plus the sum of the penalties of the jobs rejected. We provide a complete classification of these problems with respect to complexity and approximability. Our main results are various approximation schemes, constant factor approximation algorithms, and in-approximability results for different variants of this problem. ------------------------------------------------------------------------------