Catálogo de publicaciones - libros

Reliable implementation of geometric algorithms is a notoriously difficult task. Algorithms are usually designed for the Real-RAM, capable of computing with real numbers in the sense of mathematics, and for non-degenerate inputs. But, real computers are not Real-RAMs and inputs are frequently degenerate.

In the first part of the talk we illustrate the pitfalls of geometric computing by way of examples [KMP04]. The examples demonstrate in a lucid way that standard and frequently taught algorithms can go completely astray when naively implemented with floating point arithmetic.

Over the past four decades the design and analysis of algorithms has been a vibrant area of computer science research, since it was early realized that adoption of a superior algorithm could achieve accelerations unattainable by conceivable technological improvements.

A search problem is given by a binary relation (,) in , such that ∀  ∃ ,|| ≤ (||) (,). The computational task is for given find such a . We believe that in general this is not possible in polynomial time and oracles are known for which this is the case.

Many-to-one and Turing reductions between search problems are defined in a natural way. We conjecture that there is no complete search problem.

Our aim is to classify search problems and show relations between the computational complexities of them and the proof complexities of the sentences ∀  ∃ ,|| ≤ (||) (,). A typical example of a class of search problems is the class Polynomial Local Search defined as follows.

A problem is given by a -time relation (,) and a -time function (,) such that (,) holds for all . The search problem is for every and ≤ to find a ≤ such that

A typical result relating proof complexity and computational complexity of search problems is the following theorem of Buss and Krajíček.

We consider the minimum line covering problem: given a set of points in the plane, we want to find the smallest number of straight lines needed to cover all points in . We show that this problem can be solved in ( log ) time if ∈ (log), and that this is optimal in the algebraic computation tree model (we show that the Ω(log ) lower bound holds for all values of up to ). Furthermore, a (log )-factor approximation can be found within the same ( log ) time bound if . For the case when ∈ Ω(log ) we suggest how to improve the time complexity of the exact algorithm by a factor exponential in .

In the rectangle stabbing problem we are given a set of axis parallel rectangles and a set of horizontal and vertical lines, and our goal is to find a minimum size subset of lines that intersect all the rectangles. We study the capacitated version of this problem in which the input includes an integral capacity for each line that bounds the number of rectangles that the line can cover. We consider two versions of this problem. In the first, one is allowed to use only a single copy of each line (), and in the second, one is allowed to use multiple copies of every line provided that multiplicities are counted in the size of the solution ().

For the case of -dimensional rectangle stabbing with soft capacities, we present a 6-approximation algorithm and a 2-approximation algorithm when = 1. For the case of hard capacities, we present a bi-criteria algorithm that computes 16-approximate solutions that use at most two copies of every line. For the one dimensional case, an 8-approximation algorithm for hard capacities is presented.

is a well-known algorithmic tool used in the context of computing robust estimators for fitting a line to a collection of points in the plane. We demonstrate that it is possible to perform slope selection in expected time using only constant extra space in addition to the space needed for representing the input. Our solution is based upon a space-efficient variant of Matoušek’s , and we believe that the techniques developed in this paper will prove helpful in the design of space-efficient randomized algorithms using samples. To underline this, we also sketch how to compute the repeated median line estimator in an in-place setting.

We present a fully polynomial time approximation scheme (FPTAS) for minimizing an objective (+)(+) under linear constraints ≤. Examples of such problems are combinatorial minimum weight product problems such as, e.g., the following: Given a graph =(,) and two edge weights find an – path that minimizes ()(), the product of its edge weights relative to and .

90C20, 90C26, 90C27.

We show that the number of all solutions of minimum weight exact satisfiability can be found in (.||||+2) time, for a CNF formula containing propositional variables equipped with arbitrary real-valued weights. In recent years merely the unweighted counterpart of this problem has been studied [2, 3, 7].

We give a deterministic algorithm for testing satisfiability of Boolean formulas in conjunctive normal form with no restriction on clause length. Its upper bound on the worst-case running time matches the best known upper bound for randomized satisfiability-testing algorithms [6]. In comparison with the randomized algorithm in [6], our deterministic algorithm is simpler and more intuitive.

The network discovery (verification) problem asks for a minimum subset  ⊆  of queries in an undirected graph = (,) such that these queries discover all edges and non-edges of the graph. In the distance query model, a query at node returns the distances from to all other nodes in the graph. In the on-line network discovery problem, the graph is initially unknown, and the algorithm has to select queries one by one based only on the results of previous queries. We give a randomized on-line algorithm with competitive ratio for graphs on nodes. We also show lower bounds of and Ω(log) on the competitive ratio of deterministic and randomized on-line algorithms, respectively. In the off-line network verification problem, the graph is known in advance and the problem is to compute a minimum number of queries that verify all edges and non-edges. We show that the problem is -hard and present an (log)-approximation algorithm.