Search

We generalize the notions of flippable and simultaneously flippable edges in a triangulation of a set S of points in the plane into so called pseudo-simultaneously flippable edges. We prove a worst-case tight lower bound for the number of pseudosimultaneously flippable edges in a triangulation in terms of the number of vertices. We use this bound for deriving new upper bounds for the maximal number of crossing-free straight-edge graphs that can be embedded on any fixed set of N points in the plane. We obtain new upper bounds for the number of spanning trees and forests as well. Specifically, let tr(N) denote the maximum number of triangulations on a set of N points in the plane. Then we show (using the known bound tr(N) < 30N) that any N-element point set admits at most 6.9283N ċ tr(N) < 207.85N crossing-free straight-edge graphs, O(4.8795N) ċ tr(N) = O(146.39N) spanning trees, and O(5.4723N) ċ tr(N) = O(164.17N) forests. We also obtain upper bounds for the number of crossing-free straight-edge graphs that have fewer than cN or more than cN edges, for a constant parameter c, in terms of c and N.

The fire service needs a new station and it should be located optimally with respect to the houses served by it. The quality of the location is measured by the maximum of the distances to the relevant houses, and this greatest distance should obviously be as short as possible. The author shows how the solution is developed, and in so doing he explains how randomized algorithms work.

The general theme underlying the talk is the following question: Given a set of constraints, how much interleaving of these constraints (relative to how serious these constraints are) is necessary so that all of them cannot be satisfied simultaneously? For a concrete setting we consider boolean formulas in conjunctive normal form (CNF), where the clauses play the role of constraints. If all clauses are large, it needs many clauses to obtain an unsatisfiable formula; moreover, these clauses have to interleave. We review quantitative results for the amount of interleaving required, many of which rely on the Lovasz Local Lemma, a probabilistic lemma with many applications in combinatorics. In positive terms, we are interested in simple combinatorial conditions which guarantee for a CNF formula to be satisfiable. The criteria obtained are nontrivial in the sense that even though they are easy to check, it is by far not obvious how to compute a satisfying assignment efficiently in case the conditions are fulfilled; until recently, it was not known how to do so. It is also remarkable that while deciding satisfiability is trivial for formulas that satisfy the conditions, a slightest relaxation of the conditions leads us into the territory of NP-completeness. This is a survey with recent results by Heidi Gebauer, Robin Moser, Dominik Scheder, and Gabor Tardos, among others.

We consider boolean formulas in conjunctive normal form (CNF). If all clauses are large, it needs many clauses to obtain an unsatisfiable formula; moreover, these clauses have to interleave. We review quantitative results for the amount of interleaving required, many of which rely on the Lovasz Local Lemma, a probabilistic lemma with many applications in combinatorics. In positive terms, we are interested in simple combinatorial conditions which guarantee for a CNF formula to be satisfiable. The criteria obtained are nontrivial in the sense that even though they are easy to check, it is by far not obvious how to compute a satisfying assignment efficiently in case the conditions are fulfilled; until recently, it was not known how to do so. It is also remarkable that while deciding satisfiability is trivial for formulas that satisfy the conditions, a slightest relaxation of the conditions leads us into the territory of NP-completeness. Several open problems remain, some of which we mention in the concluding section.

Fur die Feuerwehr soll ein neuer Standort gefunden werden, der fur die Hauser, fur die sie zustandig ist, optimal gewahlt ist. Die Qualitat des neuen Standorts misst sich an der grosten Distanz, die zu einem der relevanten Hauser auftritt, wobei diese groste Distanz naturlich moglichst klein sein sollte. Wir idealisieren die Hauser und den neuen Standort der Feuerwehr zu Punkten in der Ebene und wahlen fur die Distanz zwischen zwei Punkten deren Abstand. Die Eingabe unseres Problems ist also eine Menge P von Punkten in der Ebene.

We give a brief account of results concerning the number of triangulations on finite point sets in the plane, both for arbitrary sets and for specific sets such as the n × n integer lattice.

We consider the family of crossing-free geometric graphs of a certain type—most notably triangulations, but also spanning (Hamiltonian) cycles, spanning trees, matchings, etc.—on a given point set in the plane. In particular, we address the question of how large these families can be in terms of the number of points. After the issue was raised for Hamiltonian cycles by Newborn and Moser, and for triangulations by Avis, it was shown in 1982 by Ajtai, Chvatal, Newborn, and Szemeredi that for any set of n points the number of all crossing-free geometric graphs on is at most cn for c=1013 (as opposed to the previously known bounds of the form cn logn). We report on some of the developments since then, e.g. a 43n bound on the number of triangulations whose proof takes a detour via random triangulations. While this problem seems elusive despite of some progress, related algorithmic questions are even less understood: For example the complexity of determining or approximating the number of triangulations of a point set, or generating a triangulation uniformly at random from all triangulations of a point set.

The infrastructure for mobile distributed tasks is often formed by cellular networks. One of the major issues in such networks is interference. In this paper we tackle interference reduction by suitable assignment of transmission power levels to base stations. This task is formalized introducing the Minimum Membership Set Cover combinatorial optimization problem. On the one hand we prove that in polynomial time the optimal solution of the problem cannot be approximated more closely than with a factor ln n. On the other hand we present an algorithm exploiting linear programming relaxation techniques which asymptotically matches this lower bound.

There is an ongoing attempt of designing a provably fast method for solving Linear Programs and related geometric optimization problems by combinatorial methods in the unit cost model (as opposed to the bit-model, where polynomial methods are known). Among others, this research has brought forth randomized methods with subexponential running time, but also a number of interesting combinatorial models like Oriented Matroids, Abstract Objective Functions (AOF), Unimodal Numberings, LP-type Problems, Abstract Optimization Problems (AOP), Unique Sink Orientations of Cubes (USO), et cetera. Although many of these models are quite general, so far there has been little success in showing good lower bounds even in these generalized abstractions. As for the simplex method, there are a number of open questions concerning several pivoting rules, notably randomized ones.

A recent result by Pach and Pinchasi on so-called balanced lines of a finite two-colored point set in the plane is related to other facts on halving triangles in 3-space and to a special case of the Generalized Lower Bound Theorem for convex polytopes.

For the first time, a running time analysis of population-based multi-objective evolutionary algorithms for a discrete optimization problem is given. To this end, we define a simple pseudo-Boolean bi-objective problem (LOTZ: leading ones - trailing zeroes) and investigate time required to find the entire set of Pareto-optimal solutions. It is shown that different multi-objective generalizations of a (1+1) evolutionary algorithm (EA) as well as a simple population-based evolutionary multi-objective optimizer (SEMO) need on average at least �(n3) steps to optimize this function. We propose the fair evolutionary multi-objective optimizer (FEMO) and prove that this algorithm performs a black box optimization in �(n2 log n) function evaluations where n is the number of binary decision variables.

Let C be a compact set in R2 and let S be a set of n points in R2. We consider the problem of computing a translate of C that contains the maximum number, ?*, of points of S. It is known that this problem can be solved in a time that is roughly quadratic in n. We show how random-sampling and bucketing techniques can be used to develop a near-linear-time Monte Carlo algorithm that computes a placement of C containing at least (1 - ?)?* points of S, for given ? > 0, with high probability. We also present a deterministic algorithm that solves the ?-approximate version of the optimal-placement problem and runs in O((n1+? + n/?) log m) time, for arbitrary constant ? > 0, if C is a convex m-gon.

In the context of graph transformations we look at the operation of switching, which can be viewed as a method for realizing global transformations of graphs through local transformations of the vertices. A switching class is then a set of graphs obtainable from a given start graph by applying the switching operation.Continuing the line of research in Ehrenfeucht, Hage, Harju and Rozenberg we consider the problem of detecting three kinds of graphs in switching classes. For all three we find algorithms running in time polynomial in the number of vertices in the graphs, although switching classes contain exponentially many graphs.

This tutorial is aiming at some randomized approaches for geometric optimization that have been developed over the last ten to fifteen years. The methods are simple, sometimes even the analysis is. The simplicity of the methods entails that they use very little of the underlying structure of the problems to tackle, and, as a consequence, they are applicable to a whole range of problems. Most prominently, they have led to new bounds for combinatorial solutions to linear programming. But with little adaption necessary — basically few problem specific primitive operations have to be supplied —the methods can be used for computing smallest enclosing balls of point sets, smallest volume enclosing ellipsoids, the distance between polytopes (given either as convex hulls or as intersection of halfspaces), and for several other problems. If the dimension of the input instance is constant, then several linear time methods are available, and some of them even behave ‘well’ when the dimension grows; at least, no better provable behavior is known. Many of the methods can be interpreted as variants of the simplex algorithm, with appropriately chosen randomized pivot rules.

We are given n points in the plane and a vertical line l (directed upwards) that intersects the convex hull, convS, of S. We want to find ‘ways’ to the first edge (facet) of convS met by line l.

Recent years have brought some progress in the knowledge of the complexity of linear programming in the unit cost model, and the best result known at this point is a randomized ‘combinatorial’ algorithm which solves a linear program over d variables and n constraints with expected O(d2n+eO(√d log d)) arithmetic operations. The bound relies on two algorithms by Clarkson, and the subexponential algorithms due to Kalai, and to Matousek, Sharir & Welzl.

Es sollen hier Resultate aus drei verschiedenen Gebieten bewiesen werden. Ein Verfahren zum Lernen Boolescher Funktionen, wobei man moglichst wenige Fehler macht [7]. Eine Konstruktion fur eine Schranke aus der kombinatorischen Geometrie [4] mit algorithmischen Anwendungen (siehe auch [13]). Und ein Algorithmus zur Optimierung X. Aus der Vielfalt der Ergebnisse ergibt sich bereits, das weniger das Ziel als vielmehr der Weg dorthin unser zentrales Anliegen ist: Eine Beweismethode, die man als „iteratives Umgewichten“ oder „Suchen bzw. Konstruktion durch Verdoppeln“ bezeichnen kann. Dabei beginnen wir mit einer Menge Mo und ziehen daraus eine Teilmenge T0. Durch Verdoppeln der Elemente aus T0 erhalten wir eine Menge M1 (tatsachlich haben hier die Elemente nun Vielfachheiten). Dann ziehen wir eine Teilmenge T1 aus M1, verdoppeln alle Elemente in M1, die in T1 vorkommen, und erhalten dadurch M2, usw. Wie wir die Teilmengen bekommen, ergibt sich erst in den konkreten Beispielen. Mit dem Verdoppeln verfolgen wir unterschiedliche Ziele. In einem Fall verringert hohe Vielfachheit die Chance, in einer der Mengen Ti aufzutauchen. Das heist, kein Element wird viel ofter als andere in den Iterationen gezogen werden. In einer anderen Anwendung hat M gute und schlechte Elemente—welche gut und welche schlecht sind, ist uns nicht bekannt. Es gelingt uns aber immer, Teilmengen Ti zu ziehen, die mindestens ein gutes Element haben, wir wissen aber nicht, welches. Verdoppeln erhoht die Chance, in spateren Ti’s aufzutreten. Da aber immer mindestens ein gutes Element verdoppelt wird, gewinnen diese schnell die Uberhand und konnen dadurch identifiziert werden. Diese Skizze der Idee wird vielleicht erst im Ruckblick verstandlich, deutet aber schon den evolutionaren Charakter der Verfahren an (Bronnimann und Goodrich nennen dies „algorithmischen Darwinismus“ [1]). In jedem Fall geht es uns aber nur um Methoden, in denen die Intuition auch durch Beweise untermauert werden kann.

We are given a two-dimensional square grid of size N×N, where N∶=2n and n≥0. A space filling curve (SFC) is a numbering of the cells of this grid with numbers from c+1 to c+N2, for some c≥0. We call a SFC recursive (RSFC) if it can be recursively divided into four square RSFCs of equal size. Examples of well-known RSFCs include the Hilbert curve, the z-curve, and the Gray code.

We consider the problem of minimizing some linear function in d variables subject to n linear inequalities. Geometrically, this corresponds to finding a point extremal in some direction inside a polyhedron defined as the intersection of n halfspaces in d-space, see e.g. [Shr]. There is vivid interest in this problem, starting with Dantzig's simplex method (which was shown to require exponential time on certain inputs, but works very good in practice). Recent years have brought some progress on the complexity of this problem in the unit cost model, and the best result known at this point is a randomized 'combinatorial' algorithm which computes the solution with expected O(d2n + e ~ ) log n) arithmetic operations. The bound relies on two algorithms by Clarkson, [Cla], and the subexponential algorithms due to Kalai, [Kal], and Matoufiek, Sharir, and Welzl, [MSW]. Note that the expectation is with respect to the internal 'coin flips' of the algorithm, and it holds for any input in contrast to the polynomial average bounds (first proved by Borgwardt) for the simplex method, which assume that the input is random with respect to some distribution. The polynomial bounds (due to Khachiyan and Karmarkar) in the bit-model are also in terms of the size of the coefficients of the input (not only in d and n). One nice feature of the combinatorial algorithms is that they can be formulated in a quite general abstract framework, and so they are applicable to a number of nonlinear optimization problems, as e.g. computing the smallest ball (ellipsoid) enclosing n points in d-space, computing the largest ellipsoid in a convex d-polytope with n facets, computing the distance between two convex d-polytopes with n facets or with n vertices, etc. Similar bounds as the one claimed above hold for all these problems, provided one can solve basic problems of small sizes efficiently (like (1) computing the smallest ball enclosing d + 1 points in d-space, (2) computing the distance between two d-simplices). Recently, Giirtner, [Giir], established subexponential bounds for the two basic cases (1) and (2) just mentioned. Other cases (like those involving ellipsoids) are still open.

Every set S of n points in the plane has a spanning tree such that no line disjoint from S has more than O(√n) intersections with the tree (where the edges are embedded as straight line segments). We review the proof of this result (originally proved by Bernard Chazelle and the author in a more general setting), point at some methods for constructing such a tree, and describe some algorithmic and combinatorial applications.

We present a simple randomized algorithm which solves linear programs with n constraints and d variables in expected O(d32 d n) time. The expectation is over the internal randomizations performed by the algorithm, and holds for any input.

The post-office problem for n point sites in the plane (determine which site is closest to a later specified query point) is generalized to the situation when the residence of each site is uncertain and it is described via uniform distribution within a disk. Two probabilistic concepts of neighborhood — expected closest site and probably closest site — are discussed and the resulting Voronoi diagrams are investigated from a combinatorial and computational point of view.

A weaving W is a simple arrangement of lines (or line segments) in the plane together with a binary relation specifying which line is “above” the other. An m by n bipartite weaving consists of m horizontal and n vertical lines or line segments which mutually intersect. A system of lines (or line segments) in 3-space is called a realization of W, if its projection into the plane is W and the relative positions of the lines respect the “above” specifications. An equivalence class of weavings induced by the combinatorial equivalence of the underlying planar arrangement of lines is said to be a weaving pattern. A weaving pattern is realizable if at least one element of the equivalence class has a realization. A weaving (pattern) W is called perfect, if along each line of W, the lines intersecting it are alternately “above” and “below”. We prove that (i) a perfect weaving pattern of n lines is realizable if and only if n≤3, (ii) a perfect m by n bipartite weaving pattern is realizable if and only if min(m, n)≤3, (iii) if n is sufficiently large then almost all weaving patterns of n lines are nonrealizable.

We consider the problem of approximating a convex figure in the plane by a pair (τ, R) of homothetic (i.e. similar and parallel) rectangles with τ⊂C⊂R. We show the existence of such pairs where the sides of the outer rectangle have length at most double the length of the inner rectangle, thereby solving a problem posed by Polya and Szegő.

The paper starts with a discussion of an application of graph grammars as means for determining polynomial-time recognizability of graph properties. Then boundary NLC graph grammars are reviewed with emphasis on the application outlined in the first part. Finally, partition controlled graph grammars are introduced as an extension of boundary NLC graph grammars which still preserves many of the properties of boundary NLC graph grammars and, moreover, allows a simple characterization result.

A tour τ of a finite set P of points is a necklace-tour if there are disks with the points in P as centers such that two disks intersect if and only if their centers are adjacent in τ. It has been observed by Sanders that a necklace-tour is an optimal traveling salesman tour.

Node label controlled (NLC) grammars are graph grammars (operating on node labeled undirected graphs) which rewrite single nodes only and which establish connections between the embedded graph and neighbors of the rewritten node on the basis of the labels of the involved nodes only. They define (possibly infinite) languages of undirected node labeled graphs (or, if we just omit the labels in the generated graphs, languages of unlabeled graphs). NLC grammars have been introduced in [JRzl,2] as a basic framework for the mathematical investigation of graph grammars. Other concepts for graph grammars can be found e.g. in [RsM,P,CL,E,N,HbK,JRz] (of course, this is not an exhaustive list). Boundary NLC grammars, BNLC grammars for short, are NLC grammars which are distinguished by the properties that (i) the left-hand side of each production is a nonterminal label and (ii) all the graphs involved (i.e., the axiom graph of the grammar and the right-hand sides of the productions) are such that nodes labeled by nonterminals are never adjacent. BNLC grammars have been investigated in [RzW1,2,3].

A typical (notion of a sequential) graph grammar G consists of a f i n i t e set of labels z, a set of terminal labels A, (A ~ z) , a f i n i t e set of productions of the form YI ~ Y2' where YI and Y2 are graphs (with labels from z) , and a s ta r t graph (or a f i n i t e set of s ta r t graphs). A der ivat ion step in G is performed as fol lows. Given a graph X and a production Y1 ~ Y2 from G, one locates a subgraph of X isomorphic to YI and "replaces" i t by a subgraph Y1⁄2 isomorphic to Y2" The crucial part of the replacement is to establ ish connections between Y' and the remainder of ×. , 2 The way that the connections are established is specif ied by the so-called embeddingmechanism which may be unique for the whole grammar or i n t r i n s i c to each of the productions. This embedding mechanism is rea l l y "the heart of G". Often also appl icat ion conditions are added to the productions in G roughly speaking, they specify which subgraphs of × that are isomorphic to Y1 may be replaced. The language generated by G is the set of a l l graphs labeled by terminal labels only which can be derived from a s ta r t graph in one or more steps. (See Rosenfeld & Milgram, 19~2; Della Vigna & Ghezzi, 1978; Nagl, 1979; Ehrig, 1979; or Janssens & Rozenberg, 1980, 1982, for examples of d i f fe ren t types of graph grammars and embedding mechanisms.) We give here a somewhat informal presentation of a very simple idea which is well applicable to (almost) every graph grammar concept independently of the embedding mechanism used. Given a graph X in a graph language generated by a graph grammar G, we encode this graph by encoding i t s der ivat ion. In general, such an endoding w i l l be more "cOmplex" than the standard representation of X by i t s nodes, edges, and labels. However, i f the der ivat ion of the graph is "reasonably short" , then th is encoding outperforms the standard representation. This simple observation has a number of implications for normal forms of graph grammars. In par t icu lar , we show that a graph grammar which generates a l l graphs ( la beled by some arb i t ra ry but f ixed set of labels) cannot be essent ia l l y growing.