Catálogo de publicaciones - libros

In the frequency allocation problem, we are given a mobile telephone network, whose geographical coverage area is divided into cells, wherein phone calls are serviced by assigning frequencies to them so that no two calls emanating from the same or neighboring cells are assigned the same frequency. The problem is to use the frequencies efficiently, i.e., minimize the span of frequencies used. The frequency allocation problem can be regarded as a multicoloring problem on a weighted hexagonal graph. In this paper, we give a 1-local 4/3-competitive distributed algorithm for multicoloring a triangle-free hexagonal graph, which is a special case. Based on this result, we then propose a 1-local 13/9-competitive algorithm for multicoloring the (general-case) hexagonal graph, thereby improving the previous 1-local 3/2-competitive algorithm.

In this paper, we study parameterized algorithms for the problem, for both weighted and unweighted versions. First, we develop a new and effective technique based on a probabilistic method that allows us to develop a simpler and more efficient (deterministic) kernelization algorithm for the unweighted problem. We then propose a randomized algorithm for the weighted problem that is based on a new subset partition technique and has its running time bounded by (2), which even significantly improves the previously known upper bound for the unweigthed problem. We also show that our algorithm can be de-randomized, thus derive the first fixed parameter tractable algorithm for the weighted problem.

When ties and incomplete preference lists are permitted in the Stable Marriage problem, stable matchings can have different sizes. The problem of finding a maximum cardinality stable matching in this context is known to be NP-hard, even under very severe restrictions on the number, size and position of ties. In this paper, we describe a polynomial-time -approximation algorithm for a variant in which ties are on one side only and at the end of the preference lists. The particular variant is motivated by important applications in large scale centralized matching schemes.

The black and white traveling salesman problem (BWTSP) is to find the minimum cost hamiltonian tour of an undirected complete graph , containing black and white vertices, subject to two restrictions: the number of white vertices, and the cost of the subtour between two consecutive black vertices are bounded. This paper focuses on designing approximation algorithms for the BWTSP in a graph satisfying the triangle inequality. We show that approximating the tour which satisfies the length constraint is NP-hard. We then show that the BWTSP can be approximated with tour cost times the optimal cost, when at most white vertices appear between two consecutive black vertices. When exactly white vertices appear between two consecutive black vertices, the approximation bound can be slightly improved to . This approximation bound is further improved to 2.5 when  = 2.