We provide the first nontrivial approximation algorithm for MAXIMUM WEIGHT PLANAR SUBGRAPH, the NP-hard problem of finding a heaviest planar subgraph in an edge-weighted graph G. This problem has applications in circu...
详细信息
We provide the first nontrivial approximation algorithm for MAXIMUM WEIGHT PLANAR SUBGRAPH, the NP-hard problem of finding a heaviest planar subgraph in an edge-weighted graph G. This problem has applications in circuit layout, facility layout, and graph drawing. No previous algorithm for MAXIMUM WEIGHT PLANAR SUBGRAPH had a performance ratio exceeding 1/3, which is obtained by any algorithm that produces a maximum weight spanning tree in G. Based on the Berman-Ramaiyer Steiner tree algorithm, the new algorithm has performance ratio at least 1/3 + 1/72 and at most 5/12. We also show that if G is complete and its edge weights satisfy the triangle inequality, then the performance ratio is at least 3/8. Furthermore, we derive the first nontrivial performance ratio (7/12 instead of 1/2) for the NP-hard MAXIMUM WEIGHT OUTERPLANAR SUBGRAPH problem.
In this paper,we consider the parallel-machine customer order scheduling with delivery time and submodular rejection *** this problem,we are given m dedicated machines in parallel and n customer *** order has a delive...
详细信息
In this paper,we consider the parallel-machine customer order scheduling with delivery time and submodular rejection *** this problem,we are given m dedicated machines in parallel and n customer *** order has a delivery time and consists of m product types and each product type should be manufactured on a dedicated *** order is either rejected,in which case a rejection penalty has to be paid,or accepted and manufactured on the m dedicated *** objective is to find a solution to minimize the sum of the maximum delivery completion time of the accepted orders and the penalty of the rejected orders which is determined by a submodular *** design an LP rounding algorithm with approximation ratio of n+1 for this problem.
Given a graph G = (V, E) with nonnegative costs defined on edges, a positive integer k, and a collection of q terminal sets D = {S-1, S-2, . . . , S-q}, where each S-i is a subset of V(G), the Generalized k-Multicut p...
详细信息
Given a graph G = (V, E) with nonnegative costs defined on edges, a positive integer k, and a collection of q terminal sets D = {S-1, S-2, . . . , S-q}, where each S-i is a subset of V(G), the Generalized k-Multicut problem asks to find a set of edges C subset of E(G) at the minimum cost such that its removal from G cuts at least k terminal sets in D. A terminal subset S-i is cut by C if all terminals in S-i are disconnected from one another by removing C from G. This problem is a generalization of the k-Multicut problem and the Multiway Cut problem. The famous Densest k-Subgraph problem can be reduced to the Generalized k-Multicut problem in trees via an approximation preserving reduction. In this paper, we first give an O(root q)-approximation algorithm for the Generalized k-Multicut problem when the input graph is a tree. The algorithm is based on a mixed strategy of LP-rounding and greedy approach. Moreover, the algorithm is applicable to deal with a class of NP-hard partial optimization problems. As its extensions, we then show that the algorithm can be used to give O(root q log n)-approximation for the Generalized k-Multicut problem in undirected graphs and O(root q)-approximation for the k-Forest problem. (C) 2012 Elsevier B.V. All rights reserved.
Let G = (V, E) be a connected graph such that each edge e is an element of E is weighted by nonnegative real w(e). Let s be a vertex designated as a source, k be a positive integer, and S subset of V be a set of termi...
详细信息
Let G = (V, E) be a connected graph such that each edge e is an element of E is weighted by nonnegative real w(e). Let s be a vertex designated as a source, k be a positive integer, and S subset of V be a set of terminals. The capacitated multicast tree routing problem (CMTR) asks to find a partition {Z(1), Z(2), . . . , Z(l)} of S and a set {T-1, T-2, . . . , T-l} of trees of G such that Z(i) consists of at most k terminals and each Ti spans Z(i) boolean OR {s}. The objective is to minimize Sigma(l)(i=1) w(T-i), where w(T-i) denotes the sum of weights of all edges in T-i. In this paper, we propose a (3/2 + (4/3)rho)-approximation algorithm to the CMTR, where rho is the best achievable approximation ratio for the Steiner tree problem. (C) 2007 Elsevier B.V. All rights reserved.
Edge-Cloud Computing Industrial Internet of Things (ECIIoT) is composed of edge and cloud nodes with Industrial Internet of Things (IIoT) devices to get the service function chain (SFC). The service function chaining ...
详细信息
Edge-Cloud Computing Industrial Internet of Things (ECIIoT) is composed of edge and cloud nodes with Industrial Internet of Things (IIoT) devices to get the service function chain (SFC). The service function chaining placement refers to a series of virtual network functions (VNFs) that are run at edge or cloud nodes in the form of software instances. In the problem of ECIIoT service embedding, the multiple VNFs must be placed for IIoT devices, so how these virtual functions are placed at cloud or edge nodes to minimize the delay is challenging to achieve. In this article, the placement of virtual functions with considering the edge and cloud nodes is proposed. In our model, the cloud server with edge nodes can run the required functions of IIoT devices in the SFC to decrease the imposed delay and use the computation resource in an efficient way. This is formed as an optimization problem to minimize the delay and residual computing resource consumption and reuse the previous functions. The exact solution of this problem is not available in polynomial time, therefore an efficient approximation algorithm is proposed which solves the problem in three stages. First, it linearizes the nonlinear objective function and constraint and approximates them by the convexity of these functions. Then, it solves the relaxed linear problem and finally, it rounds the decision variables in a heuristic way. This solution not only has polynomial time computational complexity but also obtains the near-optimal solution. The simulation results confirm the effectiveness of this approach.
We present a new approximation algorithm for the bin packing problem which has a linear running time and an absolute approximation factor of 3/2. It is known that this approximation factor is the best factor achievabl...
详细信息
We present a new approximation algorithm for the bin packing problem which has a linear running time and an absolute approximation factor of 3/2. It is known that this approximation factor is the best factor achievable, unless P = NP. (C) 2003 Elsevier Science B.V. All rights reserved.
This paper investigates cooperative data uploading and task offloading in heterogeneous Internet of Vehicles (IoV). Specifically, considering the characteristics that different tasks may require common data and can be...
详细信息
This paper investigates cooperative data uploading and task offloading in heterogeneous Internet of Vehicles (IoV). Specifically, considering the characteristics that different tasks may require common data and can be offloaded to heterogeneous nodes, we first present an end-edge-cloud architecture for cooperative data uploading and task offloading. Then, we formulate a Joint Data Uploading and Task Offloading (JDUTO) problem, which aims at minimizing the average service delay by considering common input data, heterogeneous resources, and vehicle mobility. JDUTO is proved as NP-hard by reducing the well-known NP-hard problem Capacitated Vehicle Routing Problem (CVRP) in polynomial time. On this basis, we propose an approximation algorithm. Specifically, we first design an optimal algorithm to select a set of vehicles with common data requirements for data uploading. Second, we adopt Lagrange multiplier method to derive the optimal solution of resource allocation. Third, we design a filter mechanism-based Markov-approximation algorithm for task offloading, where specific initialization and state transition strategy are designed to accelerate convergence. We prove that the gap of the approximation algorithm is 1/beta log |phi|, where beta is a positive constant and phi is the size of solution space. Finally, we build a simulation model based on real trajectories and give comprehensive performance evaluations, which conclusively demonstrate the superiority of the proposed solution.
In this paper, we give the first approximation algorithm for the problem of max-min fair allocation of indivisible goods. An instance of this problem consists of a set of k people and m indivisible goods. Each person ...
详细信息
In this paper, we give the first approximation algorithm for the problem of max-min fair allocation of indivisible goods. An instance of this problem consists of a set of k people and m indivisible goods. Each person has a known linear utility function over the set of goods which might be different from the utility functions of other people. The goal is to distribute the goods among the people and maximize the minimum utility received by them. The approximation ratio of our algorithm is Omega(1/root k log(3) k). As a crucial part of our algorithm, we design and analyze an iterative method for rounding a fractional matching on a tree which might be of independent interest. We also provide better bounds when we are allowed to exclude a small fraction of the people from the problem.
Given an underlying communication network represented as an edge-weighted graph G = (V, E), a source node S is an element of V, a set of destination nodes D subset of V, and a capacity k which is a positive integer, t...
详细信息
Given an underlying communication network represented as an edge-weighted graph G = (V, E), a source node S is an element of V, a set of destination nodes D subset of V, and a capacity k which is a positive integer, the capacitated multicast tree routing problem asks for a minimum cost routing scheme for source s to send data to all destination nodes, under the constraint that in each routing tree at most k destination nodes are allowed to receive the data copies. The cost of the routing scheme is the sum of the costs of all individual routing trees therein. Improving on Our previous approximation algorithm for the problem, we present a new algorithm which achieves a worst case performance ratio of root 2089+77/80 + 5/4 rho, where rho denotes the best known approximation ratio for the Steiner minimum tree problem. Since rho is about 1.55 at the writing of the paper, the ratio achieved by Our new algorithm is less than 3.4713. In comparison, the previously best ratio Was 8/5 + 5/4 rho approximate to 3.5375. (C) 2009 Elsevier B.V. All rights reserved.
We give the first approximation algorithm for the generalized network Steiner problem, a problem in network design. An instance consists of a network with link-costs and, for each pair {i,j} of nodes, an edge-connecti...
详细信息
We give the first approximation algorithm for the generalized network Steiner problem, a problem in network design. An instance consists of a network with link-costs and, for each pair {i,j} of nodes, an edge-connectivity requirement r(ij). The goal is to find a minimum-coir network using the available links and satisfying the requirements. Our algorithm outputs a solution whose cost is within 2[log(2)(r + 1)] of optimal, where r is the highest requirement value. In the course of proving the performance guarantee, we prove a combinatorial minmax approximate equality relating minimum-cost networks to maximum packings of certain kinds of cuts. As a consequence of the proof of this theorem, we obtain an approximation algorithm for optimally packing these cuts;we show that this algorithm has application to estimating the reliability of a probabilistic network.
暂无评论