Approximation Algorithms for Bounded Facility Location Problems

The bounded k-median problem is to select in an undirected graph G = (V,E) a set S of k vertices such that the distance from any vertex v V to S is at most a given bound d and the average distance from vertices V\S to S is minimized. We present randomized algorithms for several versions of this problem and we prove some inapproximability results. We also study the bounded version of the uncapacitated facility location problem and present extensions of known deterministic algorithms for the unbounded version.     

Improved approximation algorithms for metric MaxTSP

We present two polynomial-time approximation algorithms for the metric case of the maximum traveling salesman problem. One of them is for directed graphs and its approximation ratio is . The other is for undirected graphs and its approximation ratio is . Both algorithms improve on the previous bests. A preliminary version of this paper appeared in the Proceedings of 13th European Symposium on Algorithms (ESA2005), Lecture Notes in Computer Science, Vol. 3669, pp. 179–190, 2005.     

Improved Approximation Algorithms for Maximum Graph Partitioning Problems

We consider the design of approximation algorithms for a number of maximum graph partitioning problems, among others MAX-k-CUT, MAX-k-DENSE-SUBGRAPH, and MAX-k-DIRECTED-UNCUT. We present a new version of the semidefnite relaxation scheme along with a better analysis, extending work of Halperin and Zwick (2002). This leads to an improvement over known approximation factors for such problems. The key to the improvement is the following new technique: It was already observed by Han et al. (2002) that a parameter-driven choice of the random hyperplane can lead to better approximation factors than obtained by Goemans and Williamson (1995). But it remained difficult to find a “good” set of parameters. In this paper, we analyze random hyperplanes depending on several new parameters. We prove that a sub-optimal choice of these parameters can be obtained by the solution of a linear program which leads to the desired improvement of the approximation factors. In this fashion a more systematic analysis of the semidefinite relaxation scheme is obtained.     

A Further Improved Approximation Algorithm for Breakpoint Graph Decomposition

Breakpoint graph decomposition is a crucial step in all recent approximation algorithms for SORTING BY REVERSALS, which is one of the best-known algorithmic problems in computational molecular biology. Caprara and Rizzi recently improved the approximation ratio for breakpoint graph decomposition from to + 1.4348 + , for any positive . In this paper, we extend the techniques of Caprara and Rizzi and incorporate a balancing argument to further improve the approximation ratio to + 1.4193 + , for any positive . These improvements imply improved approximation results for SORTING BY REVERSALS for almost all random permutations.     

Approximation Algorithms for the Multiple Knapsack Problem with Assignment Restrictions

Motivated by a real world application, we study the multiple knapsack problem with assignment restrictions (MKAR). We are given a set of items, each with a positive real weight, and a set of knapsacks, each with a positive real capacity. In addition, for each item a set of knapsacks that can hold that item is specified. In a feasible assignment of items to knapsacks, each item is assigned to at most one knapsack, assignment restrictions are satisfied, and knapsack capacities are not exceeded. We consider the objectives of maximizing assigned weight and minimizing utilized capacity.We focus on obtaining approximate solutions in polynomial computational time. We show that simple greedy approaches yield 1/3-approximation algorithms for the objective of maximizing assigned weight. We give two different 1/2-approximation algorithms: the first one solves single knapsack problems successively and the second one is based on rounding the LP relaxation solution. For the bicriteria problem of minimizing utilized capacity subject to a minimum requirement on assigned weight, we give an (1/3,2)-approximation algorithm.     

Improved Approximation for Breakpoint Graph Decomposition and Sorting by Reversals

Sorting by Reversals (SBR) is one of the most widely studied models of genome rearrangements in computational molecular biology. At present, is the best known approximation ratio achievable in polynomial time for SBR. A very closely related problem, called Breakpoint Graph Decomposition (BGD), calls for a largest collection of edge disjoint cycles in a suitably-defined graph. It has been shown that for almost all instances SBR is equivalent to BGD, in the sense that any solution of the latter corresponds to a solution of the former having the same value. In this paper, we show how to improve the approximation ratio achievable in polynomial time for BGD, from the previously known to for any > 0. Combined with the results in (Caprara, Journal of Combinatorial Optimization, vol. 3, pp. 149–182, 1999b), this yields the same approximation guarantee for n! – O((n – 5)!) out of the n! instances of SBR on permutations with n elements. Our result uses the best known approximation algorithms for Stable Set on graphs with maximum degree 4 as well as for Set Packing where the maximum size of a set is 6. Any improvement in the ratio achieved by these approximation algorithms will yield an automatic improvement of our result.     

一种改进的TSP问题启发式算法

旅行推销商问题(TSP)属于组合优化领域中一个典型的NP Hard问题。本文在最近城市搜索法的基础上,提出一种改进的启发式算法———两端延伸最近城市搜索法,这种方法能够很快得到最优解(近优解),且大大降低了计算复杂度。同时,对TSP问题进行了分类,并给出相应的启发式解法。     

New Approximation Algorithms for Map Labeling with Sliding Labels

In this paper we present approximation algorithm for the following NP-hard map labeling problem: Given a set S of n distinct sites in the plane, one needs to place at each site a uniform square of maximum possible size such that all the squares are along the same direction. This generalizes the classical problem of labeling points with axis-parallel squares and restricts the most general version where the squares can have different orientations. We obtain factor-4 and factor- approximation algorithms for this problem. These algorithms also work for two generalized versions of the problem. We also revisit the problem of labeling each point with maximum uniform axis-parallel square pairs and improve the previous approximation factor of 4 to 3.     

Approximation algorithms and hardness results for labeled connectivity problems

Let G=(V,E) be a connected multigraph, whose edges are associated with labels specified by an integer-valued function ℒ:E→ℕ. In addition, each label ℓ∈ℕ has a non-negative cost c(ℓ). The minimum label spanning tree problem (MinLST) asks to find a spanning tree in G that minimizes the overall cost of the labels used by its edges. Equivalently, we aim at finding a minimum cost subset of labels I⊆ℕ such that the edge set {e∈E:ℒ(e)∈I} forms a connected subgraph spanning all vertices. Similarly, in the minimum label s – t path problem (MinLP) the goal is to identify an s–t path minimizing the combined cost of its labels. The main contributions of this paper are improved approximation algorithms and hardness results for MinLST and MinLP.     

Generalized Steiner Problems and Other Variants

In this paper, we examine combinatorial optimization problems by considering the case where the set N (the ground set of elements) is expressed as a union of a finite number of m nonempty distinct subsets N ₁,...,N _m. The term we use is the generalized Steiner problems coined after the Generalized Traveling Salesman Problem. We have collected a short list of classical combinatorial optimization problems and we have recast each of these problems in this broader framework in an attempt to identify a linkage between these “generalized” problems. In the literature one finds generalized problems such as the Generalized Minimum Spanning Tree (GMST), Generalized Traveling Salesman Problem (GTSP) and Subset Bin-packing (SBP). Casting these problems into the new problem setting has important implications in terms of the time effort required to compute an optimal solution or a “good” solution to a problem. We examine questions like “is the GTSP “harder” than the TSP?” for a number of paradigmatic problems starting with “easy” problems such as the Minimal Spanning Tree, Assignment Problem, Chinese Postman, Two-machine Flow Shop, and followed by “hard” problems such as the Bin-packing, and the TSP.     

The Greedier the Better: An Efficient Algorithm for Approximating Maximum Independent Set

The classical greedy heuristic for approximating maximum independent set is simple and efficient. It achieves a performance ratio of ( + 2)/3, where is the maximum node degree of the input graph. All known algorithms for the problem with better performance ratios are much more complicated and inefficient. In this paper, we propose a natural extension of the greedy heuristic. It is as simple and as efficient as the classical greedy heuristic. By a careful analysis on the structure of the intermediate graphs manipulated by our heuristic, we prove that the performance ratio is improved to ( + 3)/3.25.     

Approximation and Exact Algorithms for Constructing Minimum Ultrametric Trees from Distance Matrices

An edge-weighted tree is called ultrametric if the distances from the root to all the leaves in the tree are equal. For an n by n distance matrix M, the minimum ultrametric tree for M is an ultrametric tree T = (V, E, w) with leaf set {1,..., n} such that d_T(i, j) M[i, j] for all i, j and is minimum, where d_T(i, j) is the distance between i and j on T. Constructing minimum ultrametric trees from distance matrices is an important problem in computational biology. In this paper, we examine its computational complexity and approximability. When the distances satisfy the triangle inequality, we show that the minimum ultrametric tree problem can be approximated in polynomial time with error ratio 1.5(1 + log n), where n is the number of species. We also develop an efficient branch-and-bound algorithm for constructing the minimum ultrametric tree for both metric and non-metric inputs. The experimental results show that it can find an optimal solution for 25 species within reasonable time, while, to the best of our knowledge, there is no report of algorithms solving the problem even for 12 species.     

An Improved Approximation Algorithm for Multicast <Emphasis Type="Italic">k</Emphasis>-Tree Routing

An improved approximation algorithm is presented in this paper for the multicast k-tree routing problem. The algorithm has a worst case performance ratio of (2.4 + ρ), where ρ is the best approximation ratio for the metric Steiner tree problem (and is about 1.55 so far). The previous best approximation algorithm for the multicast k-tree routing problem has a performance ratio of 4. Two techniques, weight averaging and tree partitioning, are developed to facilitate the algorithm design and analysis.Research supported by AICML, CFI, NSERC, PENCE, a Startup Grant from the University of Alberta, and NNSF Grant 60373012.     

Facility Location with Dynamic Distance Functions

Facility location problems have always been studied with theassumption that the edge lengths in the network are static anddo not change over time. The underlying network could be used to model a city street networkfor emergency facility location/hospitals, or an electronic network for locating information centers. In any case, it is clear that due to trafficcongestion the traversal time on links changes with time. Very often, we have estimates as to how the edge lengths change over time, and our objective is to choose a set of locations (vertices) ascenters, such that at every time instant each vertex has a center close to it (clearly, the center close to a vertex may change over time). We also provide approximation algorithms as well as hardness results forthe K-center problem under this model. This is the first comprehensive study regarding approximation algorithmsfor facility location for good time-invariant solutions.     

A New Approximation Algorithm for the Capacitated Vehicle Routing Problem on a Tree

This paper presents a new approximation algorithm for a vehicle routing problem on a tree-shaped network with a single depot. Customers are located on vertices of the tree, and each customer has a positive demand. Demands of customers are served by a fleet of identical vehicles with limited capacity. It is assumed that the demand of a customer is splittable, i.e., it can be served by more than one vehicle. The problem we are concerned with in this paper asks to find a set of tours of the vehicles with minimum total lengths. Each tour begins at the depot, visits a subset of the customers and returns to the depot without violating the capacity constraint. We propose a 1.35078-approximation algorithm for the problem (exactly, ), which is an improvement over the existing 1.5-approximation.     

An Approximation Scheme for Bin Packing with Conflicts

In this paper we consider the following bin packing problem with conflicts. Given a set of items V = {1,..., n} with sizes s₁,..., s (0,1) and a conflict graph G = (V, E), we consider the problem to find a packing for the items into bins of size one such that adjacent items (j, j) E are assigned to different bins. The goal is to find an assignment with a minimum number of bins. This problem is a natural generalization of the classical bin packing problem.We propose an asymptotic approximation scheme for the bin packing problem with conflicts restricted to d-inductive graphs with constant d. This graph class contains trees, grid graphs, planar graphs and graphs with constant treewidth. The algorithm finds an assignment for the items such that the generated number of bins is within a factor of (1 + ) of optimal provided that the optimum number is sufficiently large. The running time of the algorithm is polynomial both in n and in .     

Simple Approximation Algorithms for MAXNAESP and Hypergraph 2-colorability

Hypergraph 2-colorability, also known as set splitting, is a widely studied problem in graph theory. In this paper we study the maximization version of the same. We recast the problem as a special type of satisfiability problem and give approximation algorithms for it. Our results are valid for hypergraph 2-colorability, set splitting and MAX-CUT (which is a special case of hypergraph 2-colorability) because the reductions are approximation preserving. Here we study the MAXNAESP problem, the optimal solution to which is a truth assignment of the literals that maximizes the number of clauses satisfied. As a main result of the paper, we show that any locally optimal solution (a solution is locally optimal if its value cannot be increased by complementing assignments to literals and pairs of literals) is guaranteed a performance ratio of . This is an improvement over the ratio of attributed to another local improvement heuristic for MAX-CUT (C. Papadimitriou, Computational Complexity, Addison Wesley, 1994). In fact we provide a bound of for this problem, where k 3 is the minimum number of literals in a clause. Such locally optimal algorithms appear to subsume typical greedy algorithms that have been suggested for problems in the general domain of satisfiability. It should be noted that the NAESP problem where each clause has exactly two literals, is equivalent to MAX-CUT. However, obtaining good approximation ratios using semi-definite programming techniques (M. Goemans and D.P. Williamson, in Proceedings of the 26th Annual ACM Symposium on Theory of Computing, 1994a, pp. 422–431) appears difficult. Also, the randomized rounding algorithm as well as the simple randomized algorithm both (M. Goemans and D.P. Williamson, SIAM J. Disc. Math, vol. 7, pp. 656–666, 1994b) yield a bound of for the MAXNAESP problem. In contrast to this, the algorithm proposed in this paper obtains a bound of for this problem.     

Approximation and Exact Algorithms for RNA Secondary Structure Prediction and Recognition of Stochastic Context-free Languages

For a basic version (i.e., maximizing the number of base-pairs) of the RNA secondary structure prediction problem and the construction of a parse tree for a stochastic context-free language, O(n³) time algorithms were known. For both problems, this paper shows slightly improved O(n³(log log n)^1/2/(log n)^1/2) time exact algorithms, which are obtained by combining Valiant's algorithm for context-free recognition with fast funny matrix multiplication. Moreover, this paper shows an O(n^2.776 + (1/)^O(1)) time approximation algorithm for the former problem and an O(n^2.976 log n + (1/)^O(1)) time approximation algorithm for the latter problem, each of which has a guaranteed approximation ratio 1 – for any positive constant , where the absolute value of the logarithm of the probability is considered as an objective value in the latter problem. The former algorithm is obtained from a non-trivial modification of the well-known O(n³) time dynamic programming algorithm, and the latter algorithm is obtained by combining Valiant's algorithm with approximate funny matrix multiplication. Several related results are shown too.     

An Edge-Splitting Algorithm in Planar Graphs

For a multigraph G = (V, E), let s V be a designated vertex which has an even degree, and let _G (V – s) denote min{c _G(X) | Ø X V – s}, where c _G(X) denotes the size of cut X. Splitting two adjacent edges (s, u) and (s, v) means deleting these edges and adding a new edge (u, v). For an integer k, splitting two edges e ₁ and e ₂ incident to s is called (k, s)-feasible if _G(V – s) k holds in the resulting graph G. In this paper, we prove that, for a planar graph G and an even k or k = 3 with k _G (V – s), there exists a complete (k, s)-feasible splitting at s such that the resulting graph G is still planar, and present an O(n ³ log n) time algorithm for finding such a splitting, where n = |V|. However, for every odd k 5, there is a planar graph G with a vertex s which has no complete (k, s)-feasible and planarity-preserving splitting. As an application of this result, we show that for an outerplanar graph G and an even integer k the problem of optimally augmenting G to a k-edge-connected planar graph can be solved in O(n ³ log n) time.     

一种改进CLOSET算法

CLOSET算法是一种挖掘频繁闭项集的有效算法。本文分析了CLOSET算法在闭合性检查以及剪枝效率方面的一些不足,并针对这些问题,引入共生项集的概念,利用共生项集的一些性质,提出了一种基于共生项集的改进算法。