Catálogo de publicaciones - libros

We consider an APX-hard variant (Δ-Max-ATSP) and an APX-hard relaxation (Max-3-DCC) of the classical traveling salesman problem. Δ-Max-ATSP is the following problem: Given an edge-weighted complete loopless directed graph such that the edge weights fulfill the triangle inequality, find a maximum weight Hamiltonian tour of . We present a -approximation algorithm for Δ-Max-ATSP with polynomial running time. Max-3-DCC is the following problem: Given an edge-weighted complete loopless directed graph, compute a spanning collection of node-disjoint cycles, each of length at least three, whose weight is maximum among all such collections. We present a -approximation algorithm for this problem with polynomial running time. In both cases, we improve on the previous best approximation performances. The results are obtained via a new decomposition technique for the fractional solution of an LP formulation of Max-3-DCC.

In the Vehicle Routing Problem (VRP), as in the Traveling Salesman Problem (TSP), we have a metric space of customer points, and we have to visits all customers. Additionally, every customer has a , a quantity of a commodity that has to be delivered in our vehicle from a single point called . Because the vehicle capacity is bounded, we need to return to the depot each time we run out of the commodity to distribute. We describe a fully polynomial time algorithm with approximation 2.5, we also modify this algorithm for the on-line version of VRP, the randomized version has competitive ratio of 2.5 on the average, and the deterministic version has ratio 4. We also describe 2 approximation for a restricted version of the problem.

In this paper we discuss the problem of constructing minimum-cost, prefix-free codes for equiprobable words under the assumption that all codewords are restricted to belonging to an arbitrary language and extend the classes of languages to which can belong.

Branch mispredictions is an important factor affecting the running time in practice. In this paper we consider tradeoffs between the number of branch mispredictions and the number of comparisons for sorting algorithms in the comparison model. We prove that a sorting algorithm using ( log ) comparisons performs Ω( log) branch mispredictions. We show that Multiway MergeSort achieves this tradeoff by adopting a multiway merger with a low number of branch mispredictions. For adaptive sorting algorithms we similarly obtain that an algorithm performing ((1 + log(1 + Inv/))) comparisons must perform Ω( log(1 + Inv/)) branch mispredictions, where Inv is the number of inversions in the input. This tradeoff can be achieved by GenericSort by Estivill-Castro and Wood by adopting a multiway division protocol and a multiway merging algorithm with a low number of branch mispredictions.

We present two results on derandomization of randomized algorithms. The first result is a derandomization of the Johnson-Lindenstrauss (JL) lemma based randomized dimensionality reduction algorithm. Our algorithm is simpler and faster than known algorithms. It is based on deriving a pessimistic estimator of the probability of failure. The second result is a general technique for derandomizing semidefinite programming (SDP) based approximation algorithms. We apply this technique to the randomized algorithm for Max Cut. Once again the algorithm is faster than known deterministic algorithms for the same approximation ratio. For this problem we present a technique to approximate probabilities with bounded error.

We obtain subquadratic algorithms for 3SUM on integers and rationals in several models. On a standard word RAM with -bit words, we obtain a running time of ( / max{}). In the circuit RAM with one nonstandard operation, we obtain ( /). In external memory, we achieve ( / ()), even under the standard assumption of data indivisibility. Cache-obliviously, we obtain a running time of ( / ). In all cases, our speedup is almost quadratic in the parallelism the model can afford, which may be the best possible. Our algorithms are Las Vegas randomized; time bounds hold in expectation, and in most cases, with high probability.

We present efficient approximation algorithms for a number of problems that call for computing the prices that maximize the revenue of the seller on a set of items. Algorithms for such problems enable the design of auctions and related pricing mechanisms [3]. In light of the fact that the problems we address are APX-hard in general [5], we design near-linear and near-cubic time approximation schemes under the assumption that the number of distinct items for sale is constant.

We consider the well known problem of matching two planar point sets under rigid transformations so as to minimize the directed Hausdorff distance. This is a well studied problem in computational geometry. Goodrich, Mitchell, and Orletsky [GMO94] presented a very simple approximation algorithm for this problem, which computes transformations based on aligning pairs of points. They showed that their algorithm achieves an approximation ratio of 4. We consider a minor modification to their algorithm, which is based on aligning midpoints rather than endpoints. We show that this algorithm achieves an approximation ratio not greater than 3.13. Our analysis is sensitive to the ratio between the diameter of the pattern set and the Hausdorff distance, and we show that the approximation ratio approaches 3 in the limit. Finally, we provide lower bounds that show that our approximation bounds are nearly tight.