Catálogo de publicaciones - libros

Let  = (,) denote an undirected weighted graph of nodes and edges, and let  ⊆ . The of a node  ∈  is the maximum distance in between and any other node of , while the of in is the minimum relative eccentricity of all the nodes in . Several facility location problems ask for partitioning the nodes of so as to minimize some global optimization function of the radii of the subsets of the partition. Here, we focus on the problem of partitioning the nodes of into exactly  ≥ 2 non-empty subsets, so as to minimize the sum of the subset radii, called the of the partition. This problem can be easily seen to be NP-hard when is part of the input, but when is fixed it can be solved in polynomial time by reducing it to a similar partitioning problem. In this paper, we first present an efficient () time algorithm for the notable case  = 2, which improves the ( +  log) running time obtainable by applying the aforementioned reduction. Then, in an effort of characterizing meaningful polynomial-time solvable instances of the problem when is part of the input, we show that (i) when is a tree, then the problem can be solved in () time, and (ii) when has bounded treewidth , then the problem can be solved in () time.

The algorithms of Mahajan and Vinay compute determinant and Pfaffian in a completely non-classical and combinatorial way, by reducing these problems to summation of paths in some acyclic graphs. The attractive feature of these algorithms is that they are division-free. We present a novel algebraic view of these algorithms: a relation to a pseudo-polynomial dynamic-programming algorithm for the knapsack problem. The main phase of MV-algorithm can be interpreted as a computation of an algebraic version of the knapsack problem, which is an alternative to the graph-theoretic approach used in the original algorithm. Our main results show how to implement Mahajan-Vinay algorithms without divisions, in time using the fast matrix multiplication algorithm.

We propose a polynomial-time-delay polynomial-space algorithm to enumerate all efficient extreme solutions of a multi-criteria minimum-cost spanning tree problem, while only the bi-criteria case was studied in the literature. The algorithm is based on the reverse search framework due to Avis & Fukuda. We also show that the same technique can be applied to the multi-criteria version of the minimum-cost basis problem in a (possibly degenerated) submodular system. As an ultimate generalization, we propose an algorithm to enumerate all efficient extreme solutions of a multi-criteria linear program. When the given linear program has no degeneracy, the algorithm runs in polynomial-time delay and polynomial space. To best of our knowledge, they are the first polynomial-time delay and polynomial-space algorithms for the problems.

We consider the parameterized complexity of the problem: given a family of sets and a parameter , we ask whether there exists a subfamily that covers at least  elements exactly once. This -complete problem has applications in wireless networks and radio broadcasting and is also a natural generalization of the well-known problem. We show that this problem is fixed-parameter tractable with respect to the parameter . That is, for every fixed , there exists a polynomial-time algorithm for it. One way to prove a problem fixed-parameter tractable is to show that it is kernelizable. To this end, we show that if no two sets in the input family intersect in more than  elements there exists a problem kernel of size . This yields a  kernel for the problem, proving fixed-parameter tractability. Subsequently, we show a 4 kernel for this problem. However a more general weighted version, with costs associated with each set and profits with each element, turns out to be much harder. The question here is whether there exists a subfamily with total cost at most a prespecified budget  such that the total profit of uniquely covered elements is at least , where  and  are part of the input. In the most general setting, assuming real costs and profits, the problem is not fixed-parameter tractable unless . Assuming integer costs and profits we show the problem to be [1]-hard with respect to  as parameter (that is, it is unlikely to be fixed-parameter tractable). However, under some reasonable restriction, the problem becomes fixed-parameter tractable with respect to both  and  as parameters.

We study the complexity of structurally restricted homomorphism and constraint satisfaction problems. For every class of relational structures , let be the problem of deciding whether a structure has a homomorphism to a given arbitrary structure , when each element in is only allowed a certain subset of elements of as its image. We prove, under a certain complexity-theoretic assumption, that this is solvable in polynomial time if and only if all structures in have bounded tree-width. The result is extended to the connected list homomorphism, edge list homomorphism, minimum cost homomorphism and maximum solution problems. We also show an inapproximability result for the minimum cost homomorphism problem.

Given a set of points in the plane, and a set of unit disks of fixed location, the problem is to find a minimum-cardinality subset that covers all points of . This problem is a geometric version of the general set cover problem, where the sets are defined by a collection of unit disks. It is still NP-hard, but while the general set cover problem is not approximable within , for some constant , the discrete unit disk cover problem was shown to admit a constant-factor approximation. Due to its many important applications, e.g., in wireless network design, much effort has been invested in trying to reduce the constant of approximation of the discrete unit disk cover problem. In this paper we significantly improve the best known constant from 72 to 38, using a novel approach. Our solution is based on a 4-approximation that we devise for the subproblem where the points of are located below a line and contained in the subset of disks of centered above . This problem is of independent interest.

Let be a simple polygon of  vertices and let be a set of  points lying in the interior of . A (,) with center  and radius  is the set of points in that have a geodesic distance ≤  from (where the geodesic distance is the length of the shortest polygonal path connection that lies in ). In this paper we present an output sensitive algorithm for finding all geodesic disks centered at the points of , for a given value of . Our algorithm runs in time, for some constant and output size . It is the basis of a cluster reporting algorithm where geodesic distances are used.

We present an algorithm to compute a shortest path for a robot between two points that avoids discs growing at a common speed in the plane. Our algorithm runs in (log) time, thus improving upon the best previous solution by a factor of . The complexity for the growing disc problem matches the known bound for the more restricted case when the discs are static.

There are many ways to triangulate a simple -gon; for certain optimization criteria such as maximization of the smallest internal angle it is known how to efficiently compute the best triangulation with respect to this criterion. In this paper we consider a natural extension of this problem: Given a simple polygon and one Steiner point in its interior, determine the optimal location of and a triangulation of and which is best amongst all triangulations and placements of . We present a polynomial-time algorithm for this problem when the optimization criterion is maximization of the minimum angle. Furthermore, we also provide a more general polynomial-time algorithm for finding the optimal placement of a constant number of Steiner points under the same optimization criterion.

In this paper, we study an interesting geometric partition problem, called , which arises in (IMRT). In current clinical practice, a multi-leaf collimator (MLC) is used to deliver the prescribed intensity maps (IMs). However, the of an MLC may require to split a large intensity map into several overlapping sub-IMs. We develop the first optimal linear time algorithm for solving the field splitting problem while minimizing the total complexity of the resulting sub-IMs. Meanwhile, our algorithm strives to minimize the maximum beam-on time of those sub-IMs. Our basic idea is to formulate the field splitting problem as computing a shortest path in a directed acyclic graph, with a special “layered” structure. The edge weights of the graph satisfy the Monge property, which enables us to speed up the algorithm to optimal linear time. To minimize the maximum beam-on time of the resulting sub-IMs, we consider an interesting min-max slope path problem in a monotone polygon which is solvable in linear time. The min-max slope path problem is of its own interest.