The S-connectivity lambda(S)(G)(u,nu) of (u,nu)in a graph G is the maximum number of uv-paths that no two of them have an edge or a node in S - {u, nu} in common. The corresponding Connectivity Augmentation (CA) probl...
详细信息
The S-connectivity lambda(S)(G)(u,nu) of (u,nu)in a graph G is the maximum number of uv-paths that no two of them have an edge or a node in S - {u, nu} in common. The corresponding Connectivity Augmentation (CA) problem is: given a graph G(0) = (V, E-0), S subset of V, and requirements r(u, nu) on V x V, find a minimum size set F of new edges (any edge is allowed) so that lambda(S)(G0+F)(u, nu) >= r(u, nu) for all u,nu is an element of V. Extensively studied particular choices of S are the edge-CA (when S = phi) and the node-CA (when S = V). A. Frank gave a polynomial algorithm for undirected edge-CA and observed that the directed case even with rooted {0, 1}-requirements is at least as hard as the Set-Cover problem (in rooted requirements there is s is an element of V - S so that if r(u, v) > 0 then: u = s for directed graphs, and u = s or nu = s for undirected graphs). Both directed and undirected node-CA have approximation threshold Omega(2log(1-epsilon) n). The only polylogarithmic approximation ratio known for CA was for rooted requirements-O(logn . logr(max)) = O(log(2)n), where r(max) = max(u,nu is an element of V) r(u, nu). No nontrivial approximation algorithms were known fordirected CA even forr(u, nu) is an element of {0, 1}, nor for undirected CA with S arbitrary. We give an approximation algorithm for the general case that matches the known approximation thresholds. For both directed and undirected CA with arbitrary requirements our approximation ratio is: O(logn) for S not equal V arbitrary, and O(r(max) . log n) for S = V. (c) 2007 Published by Elsevier Inc.
In this paper, we consider the uniform capacitated k-means problem (UC-k-means), an extension of the classical k-means problem (k-means) in machine learning. In the UC-k-means, we are given a set D of n points in d-di...
详细信息
In this paper, we consider the uniform capacitated k-means problem (UC-k-means), an extension of the classical k-means problem (k-means) in machine learning. In the UC-k-means, we are given a set D of n points in d-dimensional space and an integer k. Every point in the d-dimensional space has an uniform capacity which is an upper bound on the number of points in D that can be connected to this point. Every twopoint pair in the space has an associated connecting cost, which is equal to the square of the distance between these two points. We want to find at most k points in the space as centers and connect every point in D to some center without violating the capacity constraint, such that the total connecting costs is minimized. Based on the technique of local search, we present a bi-criteria approximation algorithm, which has a constant approximation guarantee and violates the cardinality constraint within a constant factor, for the UC-k-means.
作者：
Yang, HYe, YYZhang, JWStanford Univ
Sch Engn Dept Management Sci & Engn Stanford CA 94305 USA Tsinghua Univ
Dept Automat State Key Lab Intelligent Technol & Syst Beijing 100084 Peoples R China Stanford Univ
Sch Engn Dept Management Sci & Engn Stanford CA 94305 USA
We consider the problem of scheduling n independent jobs on two identical parallel machines, with a limit on the number of jobs that can be assigned to each single machine, so as to minimize the total weighted complet...
详细信息
We consider the problem of scheduling n independent jobs on two identical parallel machines, with a limit on the number of jobs that can be assigned to each single machine, so as to minimize the total weighted completion time of the jobs. We study a semidefinite programming-based approximation algorithm for solving this problem and prove that the algorithm has a worst case ratio at most 1.1626. (C) 2002 Elsevier B.V. All rights reserved.
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.
We define the multiple-vehicle collection for processing problem (mCfPP) as a vehicle routing and scheduling problem in which items that accumulate at customer sites over time should be transferred by a series of tour...
详细信息
We define the multiple-vehicle collection for processing problem (mCfPP) as a vehicle routing and scheduling problem in which items that accumulate at customer sites over time should be transferred by a series of tours to a processing facility. We show that this problem with the makespan objective (mCfPP()) is NP-hard using an approximation preserving reduction from a two-stage, hybrid flowshop scheduling problem. We develop a polynomial-time, constant-factor approximation algorithm to solve mCfPP(). The problem with a single site is analyzed as a special case with two purposes. First, we identify the minimum number of vehicles required to achieve a lower bound on the makespan, and second, we characterize the optimal makespan when a single vehicle is utilized.
We consider the maximum vertex-weighted matching problem (MVM) for non-bipartite graphs in which non-negative weights are assigned to the vertices of a graph and a matching that maximizes the sum of the weights of the...
详细信息
We consider the maximum vertex-weighted matching problem (MVM) for non-bipartite graphs in which non-negative weights are assigned to the vertices of a graph and a matching that maximizes the sum of the weights of the matched vertices is desired. In earlier work we have described a 2/3-approximation algorithm for the MVM on bipartite graphs (Florin Dobrian et al., 2019). Here we show that a 2/3-approximation algorithm for MVM on non-bipartite graphs can be obtained by restricting the length of augmenting paths to at most three. The algorithm has time complexity O(m log + n log n), where n is the number of vertices, m is the number of edges, and is the maximum degree of a vertex. The approximation ratio of the algorithm is obtained by considering failed vertices, i.e., vertices that the approximation algorithm fails to match but the exact algorithm does. We show that there are two distinct heavier matched vertices that we can charge each failed vertex to. Our proof techniques characterize the structure of augmenting paths in a novel way. We have implemented the 2/3-approximation algorithm and show that it runs in under a minute on graphs with tens of millions of vertices and hundreds of millions of edges. We compare its performance with five other algorithms: an exact algorithm for MVM, an exact algorithm for the maximum edge-weighted matching (MEM) problem, as well as three approximation algorithms. The approximation algorithms include a 1/2 approximation algorithm for MVM, and (2/3 - E)-and (1 - E)-approximation algorithms for the MEM. In our test set of nineteen problems, there are graphs on which the exact algorithms fail to terminate in 100 hours. In addition, the new 2/3-approximation algorithm for MVM outperforms the other approximation algorithms by either being faster (often by orders of magnitude) or obtaining better weights. (c) 2019 The Authors. Published by Elsevier B.V. This is an open access article under the CC BY-NC-ND license (http://creativecommons
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.
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 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.
暂无评论