It is well-known that the multiple knapsack problem is NP-hard, and does not admit an FPTAS even for the case of two identical knapsacks. Whereas the 0-1 knapsack problem with only one knapsack has been intensively st...
详细信息
It is well-known that the multiple knapsack problem is NP-hard, and does not admit an FPTAS even for the case of two identical knapsacks. Whereas the 0-1 knapsack problem with only one knapsack has been intensively studied, and some effective exact or approximation algorithms exist. A natural approach for the multiple knapsack problem is to pack the knapsacks successively by using an effective algorithm for the 0-1 knapsack problem. This paper considers such an approximation algorithm that packs the knapsacks in the nondecreasing order of their capacities. We analyze this algorithm for 2 and 3 knapsack problems by the worst-case analysis method and give all their error bounds.
A space-efficient approximation algorithm for the grammar-based compression problem, which requests for a given string to find a smallest context-free grammar deriving the string, is presented. For the input length it...
详细信息
A space-efficient approximation algorithm for the grammar-based compression problem, which requests for a given string to find a smallest context-free grammar deriving the string, is presented. For the input length it and an optimum CFG size g, the algorithm consumes only O(g log g) space and O(n log*n) time to achieve O((log*n) log n) approximation ratio to the optimum compression, where log*n is the maximum number of logarithms satisfying log log...log n > 1. This ratio is thus regarded to almost O(log n), which is the currently best approximation ratio. While g depends on the string, it is known that g = Omega(log n) and g = O(n/log(k)n) for strings from k-letter alphabet [12].
Given a graph G, an integer k, and a demand set D = {(s(1), t(1)),..., (s(1), t(1))}, the k-Steiner Forest problem finds a forest in graph G to connect at least k demands in D such that the cost of the forest is minim...
详细信息
Given a graph G, an integer k, and a demand set D = {(s(1), t(1)),..., (s(1), t(1))}, the k-Steiner Forest problem finds a forest in graph G to connect at least k demands in D such that the cost of the forest is minimized. This problem was proposed by Hajiaghayi and Jain in SODA'06. Thereafter, using a Lagrangian relaxation technique, Segev et al. gave the first approximation algorithm to this problem in ESA'06, with performance ratio O(n(2/3) log l). We give a simpler and faster approximation algorithm to this problem with performance ratio O(n(2/3) log k) via greedy approach, improving the previously best known ratio in the literature. (C) 2008 Elsevier B.V. All rights reserved.
Given a complete k-partite graph G = (V-1, V-2,..., V-k;E) satisfying vertical bar V-1 vertical bar = vertical bar V-2 vertical bar = ... = vertical bar V-k vertical bar = n and weights of all k-cliques of G, the k-di...
详细信息
Given a complete k-partite graph G = (V-1, V-2,..., V-k;E) satisfying vertical bar V-1 vertical bar = vertical bar V-2 vertical bar = ... = vertical bar V-k vertical bar = n and weights of all k-cliques of G, the k-dimensional assignment problem finds a partition of vertices of G into a set of(pairwise disjoint) n k-cliques that minimizes the sum total of weights of the chosen cliques. In this paper, we consider a case in which the weight of a clique is defined by the sum of given weights of edges induced by the clique. Additionally, we assume that vertices of G are embedded in the d-dimensional space Q(d) and a weight of an edge is defined by the square of the Euclidean distance between its two endpoints. We describe that these problem instances arise from a multidimensional Gaussian model of a data-association problem. We propose a second-order cone programming relaxation of the problem and a polynomial time randomized rounding procedure. We show that the expected objective value obtained by our algorithm is bounded by (5/2 - 3/k) times the optimal value. Our result improves the previously known bound (4 - 6/k) of the approximation ratio. (C) 2007 Elsevier B.V. All rights reserved.
Motivated by recent applications in robust optimization and in sign-constrained linear-quadratic control, we study in this paper a new class of optimization problems called separated continuous conic programming (SCCP...
详细信息
Motivated by recent applications in robust optimization and in sign-constrained linear-quadratic control, we study in this paper a new class of optimization problems called separated continuous conic programming (SCCP). Focusing on a symmetric primal-dual pair, we develop a strong duality theory for the SCCP. Our idea is to use discretization to connect the SCCP and its dual to two ordinary conic programs. We show if the latter are strongly feasible and with finite optimal values, a condition that is readily veri. able, then the strong duality holds for the SCCP. This approach also leads to a polynomial-time approximation algorithm that solves the SCCP to any required accuracy.
We study the minimum weight dominating set problem in weighted unit disk graph, and give a polynomial time algorithm with approximation ratio 5 + epsilon, improving the previous best result of 6 + epsilon in [Yaochun ...
详细信息
We study the minimum weight dominating set problem in weighted unit disk graph, and give a polynomial time algorithm with approximation ratio 5 + epsilon, improving the previous best result of 6 + epsilon in [Yaochun Huang, Xiaofeng Gao, Zhao Zhang, Weili Wu, A better constant-factor approximation for weighted dominating set in unit disk graph, J. Comb. Optim. (ISSN: 1382-6905) (2008) 1573-2886. (Print) (Online)]. Combining the common technique used in the above mentioned reference, we can compute a minimum weight connected dominating set with approximation ratio 9 + epsilon, beating the previous best result of 10 + epsilon in the same work. (C) 2008 Elsevier B.V. All rights reserved.
In this paper. we consider the asymmetric traveling salesman problem with the gamma- parameterized triangle inequality for gamma is an element of |1/2, 1|. That means the edge weights in the given complete graph G = (...
详细信息
In this paper. we consider the asymmetric traveling salesman problem with the gamma- parameterized triangle inequality for gamma is an element of |1/2, 1|. That means the edge weights in the given complete graph G = (V, E, omega) satisfy omega(u, w) <= gamma . (omega(u, v) + omega(v, w)) for all distinct nodes u, v, w is an element of V. L.S. Chandran and L.S. Ram gave the first constant factor approximation algorithm with polynomial running time for this problem. They achieve performance ratio. gamma/1-gamma. M. Blaser, B. Manthey and J. Sgall obtain a 1+gamma/2-gamma-gamma(3)-approximation algorithm. We devise an approximation algorithm with performance ratio max{1 + gamma(3)/1-gamma(2), gamma+gamma(2)+1/2 + gamma(3)/1(-)gamma(2)}, which is better than both 1+gamma/2-gamma-gamma(3) and gamma/1-gamma for almost all gamma is an element of |1/2, 1|. (c) 2008 Elsevier Inc. All rights reserved.
The vertex cover problem is a classical NP-complete problem for which the best worst-case approximation ratio is 2-o(1). In this paper, we use a collection of simple graph transformations, each of which guarantees an ...
详细信息
The vertex cover problem is a classical NP-complete problem for which the best worst-case approximation ratio is 2-o(1). In this paper, we use a collection of simple graph transformations, each of which guarantees an approximation ratio of 3/2, to find approximate vertex covers for a large collection of randomly generated graphs and test graphs from various sources. The graph reductions are extremely fast, and even though they by themselves are not guaranteed to find a vertex cover, we manage to find a 3/2-approximate vertex cover for almost every single graph in our collection. The few graphs that we cannot solve have specific structure: they are triangle-free, with a minimum degree of at least 3, a lower bound of n/2 on the optimal vertex cover, and are unlikely to have a large bipartite subgraph.
We consider the single vehicle scheduling problem in which the customers are located at the vertices of a tree or a cycle, and have release and service time requirements. The objective is to minimize the makespan. In ...
详细信息
We consider the single vehicle scheduling problem in which the customers are located at the vertices of a tree or a cycle, and have release and service time requirements. The objective is to minimize the makespan. In the tour-version the makespan means the time when the vehicle returns to its initial location after serving all customers. While in the path-version the makespan refers to the maximum completion time of all customers. For the problem on a tree, we present a 9/5-approximation algorithm for the tour-version and a 27/14-approximation algorithm for the path-version. For the problem on a cycle, we present 12/7-approximation algorithms for both versions. (C) 2012 Elsevier B.V. All rights reserved.
Given a finite set of straight line segments S in R-2 and some k is an element of N, is there a subset V of points on segments in S with vertical bar V vertical bar <= k such that each segment of S contains at leas...
详细信息
Given a finite set of straight line segments S in R-2 and some k is an element of N, is there a subset V of points on segments in S with vertical bar V vertical bar <= k such that each segment of S contains at least one point in V? This is a special case of the set covering problem where the family of subsets given can be taken as a set of intersections of the straight line segments in S. Requiring that the given subsets can be interpreted geometrically this way is a major restriction on the input, yet we have shown that the problem is still strongly NP-complete [5]. In light of this result, we studied the accuracy of two polynomial-time approximation algorithms along with a third heuristic based algorithm which return segment coverings. We obtain certain theoretical results, and in particular we show that the performance ratio for each of these algorithms is unbounded, in general. Despite this, our experimental results suggest that the cases where this ratio exceeds 2 are rare for "reasonable" methods of placing segments. This is evidence that these polynomial-time algorithms solve the problem accurately in practice. Published by Elsevier B.V.
暂无评论