We consider the problem of finding a spanning tree that maximizes the number of leaves (MaxLeaf). We provide a 3/2-approximation algorithm for this problem when restricted to cubic graphs, improving on the previous 5/...
详细信息
We consider the problem of finding a spanning tree that maximizes the number of leaves (MaxLeaf). We provide a 3/2-approximation algorithm for this problem when restricted to cubic graphs, improving on the previous 5/3-approximation for this class. To obtain this approximation we define a graph parameter x(G) and construct a tree with at least (n - x(G) + 4)/3 leaves, and we prove that no tree with more than (n- x(G)+ 2)/2 leaves exists. In contrast to previous approximation algorithms for MaxLeaf, our algorithm works with connected dominating sets instead of by constructing a tree directly. The algorithm also yields a 4/3-approximation for the minimum connected dominating set problem in cubic graphs.
The Selective Single-Sink Buy-at-Bulk problem was proposed by Awerbuch and Azar (FOCS 1997). For a long time, the only known non-trivial approach to approximate this problem is the tree-embedding method initiated by B...
详细信息
The Selective Single-Sink Buy-at-Bulk problem was proposed by Awerbuch and Azar (FOCS 1997). For a long time, the only known non-trivial approach to approximate this problem is the tree-embedding method initiated by Bartal (FOCS 1996). In this paper, we give a thoroughly different approximation approach for the problem with approximation ratio , where q is the number of source terminals in the problem instance. Our approach is based on a mixed strategy of LP-rounding and the greedy method. When the number q (which is always at most n) is relatively small (say, q=o(log(2) n)), our approximation ratio is better than the currently known best ratio O(logn), where n is the number of vertices in the input graph.
The k-facility location problem is a common generalization of the facility location and the k-median problems. For the metric uncapacitated k-facility location problem, we propose a polynomial-time 2 + root 3 + epsilo...
详细信息
The k-facility location problem is a common generalization of the facility location and the k-median problems. For the metric uncapacitated k-facility location problem, we propose a polynomial-time 2 + root 3 + epsilon-approximation algorithm using the local search approach, which significantly improves the previously known approximation ratio 4, given by Jain et al. using the greedy method [K. Jain, M. Mahdian, E. Markakis, A. Saberi, V. Vazirani, Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP, Journal of the ACM 50 (2003) 795-824]. (c) 2007 Elsevier B.V. All rights reserved.
The Malleable Parallel Task Scheduling problem (MPTS) is an extension of one of the most classic scheduling problems (P parallel to C-max). The only difference is that for MPTS, each task can be processed simultaneous...
详细信息
The Malleable Parallel Task Scheduling problem (MPTS) is an extension of one of the most classic scheduling problems (P parallel to C-max). The only difference is that for MPTS, each task can be processed simultaneously by more than one processor. Such flexibility could dramatically reduce the makespan, but greatly increase the difficulty for solving the problem. By carefully analyzing some existing algorithms for MPTS, we find each of them suitable for some specific cases, but none is effective enough for all cases. Based on such observations, we introduce some optimization algorithms and improving techniques for MPTS, with their performance analyzed in theory. Combining these optimization algorithms and improving techniques gives rise to our novel scheduling algorithm OCM (Optimizations Combined for MPTS), a 2-approximation algorithm for MPTS. Extensive simulations on random datasets and SPLASH-2 benchmark reveal that for all cases, schedules produced by OCM have smaller makespans, compared with other existing algorithms. (C) 2012 Elsevier Inc. All rights reserved.
In a widely-studied class of multi-parametric optimization problems, the objective value of each solution is an affine function of real-valued parameters. Then, the goal is to provide an optimal solution set, i.e., a ...
详细信息
In a widely-studied class of multi-parametric optimization problems, the objective value of each solution is an affine function of real-valued parameters. Then, the goal is to provide an optimal solution set, i.e., a set containing an optimal solution for each nonparametric problem obtained by fixing a parameter vector. For many multi-parametric optimization problems, however, an optimal solution set of minimum cardinality can contain super-polynomially many solutions. Consequently, no polynomial-time exact algorithms can exist for these problems even if P = NP. We propose an approximation method that is applicable to a general class of multi-parametric optimization problems and outputs a set of solutions with cardinality polynomial in the instance size and the inverse of the approximation guarantee. This method lifts approximation algorithms for non-parametric optimization problems to their parametric version and provides an approximation guarantee that is arbitrarily close to the approximation guarantee of the approximation algorithm for the non-parametric problem. If the non-parametric problem can be solved exactly in polynomial time or if an FPTAS is available, our algorithm is an FPTAS. Further, we show that, for any given approximation guarantee, the minimum cardinality of an approximation set is, in general, not l-approximable for any natural number l less or equal to the number of parameters, and we discuss applications of our results to classical multi-parametric combinatorial optimizations problems. In particular, we obtain an FPTAS for the multi-parametricminimum s-t-cut problem, an FPTAS for the multi-parametric knapsack problem, as well as an approximation algorithm for the multi-parametric maximization of independence systems problem.
The problem of Minimum Congestion Hypergraph Embedding in a Cycle (MCHEC) is to embed the hyperedges of a hypergraph as adjacent paths around a cycle, such that the maximum congestion over any physical link in the cyc...
详细信息
The problem of Minimum Congestion Hypergraph Embedding in a Cycle (MCHEC) is to embed the hyperedges of a hypergraph as adjacent paths around a cycle, such that the maximum congestion over any physical link in the cycle is minimized. The problem is NP-complete in general, but solvable in polynomial time when all hyperedges contain exactly two vertices. In this paper, we first formulate the problem as an Integer Linear Program (ILP). Then, a solution with approximation bound of 1: 5(opt + 1) is presented by using a clockwise (2/3)-rounding algorithm, where opt denotes the optimal value of maximum congestion. To our knowledge, this is the best approximation bound known for the MCHEC problem.
This paper deals with cooperative competition in facility location problems in which potential players (investors) are in competition (or conflict) over acquiring suitable sites and clients. In order to formulate the ...
详细信息
This paper deals with cooperative competition in facility location problems in which potential players (investors) are in competition (or conflict) over acquiring suitable sites and clients. In order to formulate the problem, a game-theoretical multi-objective model with the objective of maximizing investor utility is presented. In the proposed method, an acceptance threshold constraint is applied to facility allocation that is based on a combination of distance between a facility and clients, and investors' product prices. Since the common solution methods for multi-objective optimization, such as weighted sums, epsilon-constraints, multi-objective meta-heuristic algorithms, etc. are not efficient enough, and cannot guarantee achieving Nash equilibrium points, a new approach is developed to solve the presented problem. Moreover, according to the computational complexity of the problem, an approximation algorithm is introduced for large-sized problems. Finally, the computational results demonstrate that the proposed algorithm performs efficiently in obtaining Nash equilibrium points. (C) 2017 Elsevier Ltd. All rights reserved.
For a continuous multi-objective optimization problem, it is usually not a practical approach to compute all its nondominated points because there are infinitely many of them. For this reason, a typical approach is to...
详细信息
For a continuous multi-objective optimization problem, it is usually not a practical approach to compute all its nondominated points because there are infinitely many of them. For this reason, a typical approach is to compute an approximation of the nondominated set. A common technique for this approach is to generate a polyhedron which contains the nondominated set. However, often these approximations are used for further evaluations. For those applications a polyhedron is a structure that is not easy to handle. In this paper, we introduce an approximation with a simpler structure respecting the natural ordering. In particular, we compute a box-coverage of the nondominated set. To do so, we use an approach that, in general, allows us to update not only one but several boxes whenever a new nondominated point is found. The algorithm is guaranteed to stop with a finite number of boxes, each being sufficiently thin.
The input of the universal facility location problem includes a set of clients and a set of facilities. Our goal is to find an assignment such that each client is assigned while the total connection and facility cost ...
详细信息
The input of the universal facility location problem includes a set of clients and a set of facilities. Our goal is to find an assignment such that each client is assigned while the total connection and facility cost is minimized. Here the connection cost is proportional to the distance between each client and its assigned facility, thus metric. The facility cost is a nondecreasing function with respect to the total number of clients assigned to the facility. The universal facility location problem is NP-hard since it generalizes several classical facility location problems. Our work considers the universal facility location problem with linear penalties, a generalized version of the universal facility location problem. Here each client can be rejected for service with certain penalty cost. Thus we have to consider penalty cost other than total connection and facility cost in our objective function. Based on local search method, we present a (5.83+is an element of)-approximation algorithm for this problem. (C) 2017 Elsevier B.V. All rights reserved.
Multiprocessor job scheduling problem has become increasingly interesting, for both theoretical study and practical applications. Theoretical study of the problem has made significant progress recently, which, however...
详细信息
Multiprocessor job scheduling problem has become increasingly interesting, for both theoretical study and practical applications. Theoretical study of the problem has made significant progress recently, which, however, seems not to imply practical algorithms for the problem, yet. Practical algorithms have been developed only for systems with three processors and the techniques seem difficult to extend to systems with more than three processors. This paper offers new observations and introduces new techniques for the multiprocessor job scheduling problem on systems with four processors. A very simple and practical linear time approximation algorithm of ratio bounded by 1.5 is developed for the multi-processor job scheduling problem P (4)|fix|C (max), which significantly improves previous results. Our techniques are also useful for multiprocessor job scheduling problems on systems with more than four processors.
暂无评论