Catálogo de publicaciones - libros

Stable matching is one of the oldest problems studied from an algorithmic point of view, whose original version is defined as follows: An instance consists of men, women, and each person’s preference list. A preference list is a totally ordered list including all members of the opposite sex depending on his/her preference. For a matching between men and women, a pair of a man and a woman is called a if both prefer each other to their current partners. A matching with no blocking pair is called .

Meshing of surfaces is an ubiquitous problem in many applications of science and engineering. Among different approaches available for meshing surfaces, Delaunay meshing is often favored because of its directional independence and good quality in general. As application varies, so does the input form of the surface to be meshed. We present algorithms to compute Delaunay meshes for various forms of input surfaces. Specifically, we consider surfaces input with (i) point cloud data, (ii) implicit equations, and (iii) polyhedra. These algorithms come with theoretical guarantees and some of them have been successfully implemented. In this talk we detail the algorithms, provide the mathematical reasoning behind their designs, and show the results of some experiments.

We explore the three main avenues of research still unsolved in the algorithmic graph-minor theory literature, which all stem from a key min-max relation between the treewidth of a graph and its largest grid minor. This min-max relation is a keystone of the Graph Minor Theory of Robertson and Seymour, which ultimately proves Wagner’s Conjecture about the structure of minor-closed graph properties.

First, we obtain the only known polynomial min-max relation for graphs that do not exclude any fixed minor, namely, map graphs and power graphs. Second, we obtain explicit (and improved) bounds on the min-max relation for an important class of graphs excluding a minor, namely, -minor-free graphs, using new techniques that do not rely on Graph Minor Theory. These two avenues lead to faster fixed-parameter algorithms for two families of graph problems, called minor-bidimensional and contraction-bidimensional parameters. Third, we disprove a variation of Wagner’s Conjecture for the case of graph contractions in general graphs, and in a sense characterize which graphs satisfy the variation. This result demonstrates the limitations of a general theory of algorithms for the family of contraction-closed problems (which includes, for example, the celebrated dominating-set problem). If this conjecture had been true, we would have had an extremely powerful tool for proving the existence of efficient algorithms for any contraction-closed problem, like we do for minor-closed problems via Graph Minor Theory.

Branch & Reduce and dynamic programming on graphs of bounded treewidth are among the most common and powerful techniques used in the design of exact (exponential time) algorithms for NP hard problems. In this paper we discuss the efficiency of algorithms based on combinations of these techniques. We give several examples of possible combinations of branching and programming which provide the fastest known algorithms for a number of NP hard problems: and some variations, counting the number of maximum weighted independent sets. We also briefly discuss how similar techniques can be used to design parameterized algorithms. As an example, we give fastest known algorithm solving - problem.

In this paper the well-known problem of finding the median of an ordered set is studied under a very restrictive streaming model with sequential read-only access to the data. Only a constant number of reference objects from the stream can be stored for comparison with subsequent stream elements. A first non-trivial bound of distance to the extrema of the set is presented for a single pass over streams which do not reveal their total size . For cases with known size, an algorithm is given which guarantees a distance of Ω() to the extrema, which is an -approximation for the proven best bound possible.

We study generalizations of the Tower of Hanoi (ToH) puzzle with relaxed placement rules. In 1981, D. Wood suggested a variant, where a bigger disk may be placed a smaller one if their size difference is less than . In 1992, D. Poole suggested a natural disk-moving strategy, and computed the length of the shortest move sequence (algorithm) under its framework. However, other strategies were not considered, so the lower bound/optimality question remained open. In 1998, Beneditkis, Berend, and Safro were able to prove the optimality of Poole’s algorithm for the first non-trivial case =2 only. We prove it be optimal in the general case. Besides, we prove a tight bound for the diameter of the configuration graph of the problem suggested by Wood. Further, we consider a generalized setting, where the disk sizes should not form a continuous interval of integers. To this end, we describe a finite family of potentially optimal algorithms and prove that for any set of disk sizes, the best one among those algorithms is optimal. Finally, a setting with the relaxed placement rule (suggested by D. Berend) is defined. We show that it is not more general, by finding a reduction to the second setting.

Motivated by emerging applications for DNA code word design, we consider a generalization of the code word design problem in which an input graph is given which must be labeled with equal length binary strings of minimal length such that the Hamming distance is small between words of adjacent nodes and large between words of non-adjacent nodes. For general graphs we provide algorithms that bound the word length with respect to either the maximum degree of any vertex or the number of edges in either the input graph or its complement. We further provide multiple types of recursive, deterministic algorithms for trees and forests, and provide an improvement for forests that makes use of randomization.

We study the online frequency allocation problem for wireless linear (highway) cellular networks, where the geographical coverage area is divided into cells aligned in a line. Calls arrive over time and are served by assigning frequencies to them, and no two calls emanating from the same cell or neighboring cells are assigned the same frequency. The objective is to minimize the span of frequencies used.

In this paper we consider the problem with or without the assumption that calls have infinite duration. If there is the assumption, we propose an algorithm with absolute competitive ratio of 3/2 and asymptotic competitive ratio of 1.382. The lower bounds are also given: the absolute one is 3/2 and the asymptotic one is 4/3. Thus, our algorithm with absolute ratio of 3/2 is best possible. We also prove that the Greedy algorithm is 3/2-competitive in both the absolute and asymptotic cases. For the problem without the assumption, i.e. calls may terminate at arbitrary time, we give the lower bounds for the competitive ratios: the absolute one is 5/3 and the asymptotic one is 14/9. We propose an optimal online algorithm with both competitive ratio of 5/3, which is better than the Greedy algorithm, with both competitive ratios 2.

In this paper we study the Revocable Online Knapsack Problem (ROKP) which is an extension of the Online Knapsack Problem [8]. We prove an optimal upper bound of 1/ for the competitive ratio of ROKP, where is a real root of 4 + 5 – – 4 = 0 ( ≈0.76850 and 1/ ≈1.3012). To prove this result, we made a full use of computer programs as follows: For the base algorithm that is designed in a conventional manner, we first construct an equivalent finite state diagram with about 300 states. Then for each state, we generate a finite set of inequalities such that the competitive ratio at that state is at most 1/ if the set of inequalities do not have a real solution. The latter can be checked by Mathematica. The number of inequalities generated was approximately 600 in total, and our computation time was 30 minutes using Athlon XP 2600+.

We consider the problem. Input to this problem is a sequence of requests, each specified by a point in a metric space. There is a “server” that moves from point to point to serve these requests. To serve a request, the server needs to visit the point corresponding to that request. The objective is to minimize the total distance travelled by the server in the metric space. In order to achieve this, the server is allowed to serve the requests in any order that requires to “buffer” at most requests at any time. Thus a valid reordering can serve a request only after serving all but previous requests.

In this paper, we consider this problem on a line metric which is motivated by its application to a widely studied disc scheduling problem. On a line metric with uniformly spaced points, our algorithm yields the first and runs in quasi-polynomial time () where is the total number of requests. Our approach is based on a dynamic program that keeps track of the number of pending requests in each of (log) line segments that are geometrically increasing in length.