Catálogo de publicaciones - libros

Recently Bansal and Sviridenko [4] proved that there is no asymptotic PTAS for without rotations allowed, unless . We show that similar approximation hardness results hold for several rectangle packing problems even if rotations by ninety degrees around the axes are allowed. Moreover, for some of these problems we provide explicit lower bounds on asymptotic approximation ratio of any polynomial time approximation algorithm.

The paper concerns a new variant of the on metric powers (), which is a multi-level uncapacitated facility location problem defined as follows. The input consists of a set of locations that may open a facility, subsets ,,..., of locations that may open an intermediate transmission station and a set of locations of clients. Each client in must be serviced by an open transmission station in and every open transmission station in must be serviced by an open transmission station on the next lower level, . An open transmission station on the first level, must be serviced by an open facility. The cost of assigning a station on level ≥ 1 to a station on level -1 is . For ∈ , the cost of opening a facility at location is ≥ 0. It is required to find a feasible assignment that minimizes the total cost. A constant ratio approximation algorithm is established for this problem. This algorithm is then used to develop constant ratio approximation algorithms for the and the problems.

Consider a truck running along a road. It picks up a load at point and delivers it at , carrying at most one load at a time. The speed on the various parts of the road in one direction is given by () and that in the other direction is given by (). Minimizing the total time spent to deliver loads ,..., is equivalent to solving the Traveling Salesman Problem (TSP) where the cities correspond to the loads with coordinates (, ) and the distance from to is given by if ≥ and by if < . This case of TSP is polynomially solvable with significant real-world applications.

Gilmore and Gomory obtained a polynomial time solution for this TSP [6]. However, the bottleneck version of the problem (BTSP) was left open. Recently, Vairaktarakis showed that BTSP with this distance metric is NP-complete [10].

We provide an approximation algorithm for this BTSP by exploiting the underlying geometry in a novel fashion. This also allows for an alternate analysis of Gilmore and Gomory’s polynomial time algorithm for the TSP. We achieve an approximation ratio of (2+) where . Note that when ()=(), the approximation ratio is 3.

We introduce a new combinatorial optimization problem in this paper, called the (MCIP) problem, which was inspired by computational biology applications including ortholog assignment and DNA fingerprint assembly. A of a positive integer is a multiset of positive integers that add up to exactly , and an of a multiset of integers is defined as the multiset union of partitions of integers in . Given a sequence of multisets , ⋯, of integers, where ≥ 2, we say that a multiset is a if it is an integer partition of every multiset , 1≤ ≤ . The MCIP problem is thus defined as to find a common integer partition of , ⋯, with the minimum cardinality. It is easy to see that the MCIP problem is NP-hard since it generalizes the well-known Set Partition problem. We can in fact show that it is APX-hard. We will also present a -approximation algorithm for the MCIP problem when = 2, and a -approximation algorithm for ≥ 3.

Given two rooted, labeled trees and the tree path subsequence problem is to determine which paths in are subsequences of which paths in . Here a path begins at the root and ends at a leaf. In this paper we propose this problem as a useful query primitive for XML data, and provide new algorithms improving the previously best known time and space bounds.

Let Δ≥ 1 and ≥ 0 be real numbers. A tree =(,′) is a Δ of a graph =(,) if (,) ≤ Δ  (,) +  and (,) ≤ Δ  (,) +  hold for every ,∈ . The Δ asks for a given graph to decide whether has a distance (Δ,)-approximating tree. In this paper, we consider unweighted graphs and show that the distance (Δ,0)-approximating tree problem is NP-complete for any Δ≥ 5 and the distance (1,1)-approximating tree problem is polynomial time solvable.

The paper studies the following variant of clustering or laying out problems of graphs: Given a directed acyclic graph (DAG for short), the objective is to find a mapping of its nodes into blocks of size at most that minimizes the maximum number of external arcs during traversals of the acyclic structure by following paths from the roots to the leaves. An external arc is defined as an arc connecting two distinct blocks. The problem can be shown to be NP-hard generally, and to remain intractable even if = 2 and the height of DAGs is three. In this paper we provide a factor linear time approximation algorithm for = 2, and prove that the ratio is optimal in terms of approximation guarantee. In the case of ≥ 3, we also show that there is no factor approximation algorithm assuming P ≠ NP, where is arbitrarily small positive. Furthermore, we give a 2 factor approximation algorithm for = 3 if the input is restricted to a set of layered graphs.

We present a new on-line algorithm for coloring bipartite graphs. This yields a new upper bound on the on-line chromatic number of bipartite graphs, improving a bound due to Lovász, Saks and Trotter. The algorithm is on-line competitive on various classes of – free bipartite graphs, in particular -free bipartite graphs and -free bipartite graphs, i.e., that do not contain an induced path on six, respectively seven vertices. The number of colors used by the on-line algorithm in these particular cases is bounded by roughly twice, respectively roughly eight times the on-line chromatic number. In contrast, it is known that there exists no competitive on-line algorithm to color -free (or -free) bipartite graphs, i.e., for which the number of colors is bounded by any function only depending on the chromatic number.

In this paper we construct two distributed algorithms for computing approximations of a largest matching and a minimum dominating set in planar graphs on vertices. The approximation ratio in both cases approaches one with tending to infinity and the number of synchronous communication rounds is poly-logarithmic in . Our algorithms are purely deterministic.

The perfect matching problem for general graphs reduces to the same for regular graphs. Even finding an NC algorithm for the perfect matching problem in cubic (3-regular) or 4-regular graphs will suffice to solve the general problem (see [DK 92]). For regular bipartite graphs an NC algorithm is already known [LPV 81], while [SW 96] give an NC algorithm for cubic-bipartite graphs.

We present a new and conceptually simple parallel algorithm for finding a perfect matching in -regular bipartite graphs. When is small (polylogarithmic) our algorithm in fact runs in NC. In particular for cubic-bipartite graphs, our algorithm as well as its analysis become much simpler than the previously known algorithms for the same. Our techniques are completely different from theirs.

Interestingly, our algorithm is based on a method used by [MV 00] for finding a perfect matching in planar-bipartite graphs. So, it is remarkable that, circumventing the planarity, we could still make the same approach work for a non-planar subclass of biparitite graphs.