An instance of the Connected Maximum Cut problem consists of an undirected graph G = (V, E) and the goal is to find a subset of vertices S subset of V that maximizes the number of edges in the cut delta(S) such that t...
详细信息
An instance of the Connected Maximum Cut problem consists of an undirected graph G = (V, E) and the goal is to find a subset of vertices S subset of V that maximizes the number of edges in the cut delta(S) such that the induced graph G[S] is connected. We present the first non-trivial Omega(1/log n) approximation algorithm for the Connected Maximum Cut problem in general graphs using novel techniques. We then extend our algorithm to edge weighted case and obtain a poly-logarithmic approximation algorithm. Interestingly, in contrast to the classical Max-Cut problem that can be solved in polynomial time on planar graphs, we show that the Connected Maximum Cut problem remains NP-hard on unweighted, planar graphs. On the positive side, we obtain a polynomial time approximation scheme for the Connected Maximum Cut problem on planar graphs and more generally on bounded genus graphs. (C) 2020 Elsevier B.V. All rights reserved.
This paper addresses a real-life unidimensional cutting stock problem. The objective is not only to minimize trim loss, as in traditional cutting stock problems, but also to minimize cutting time. A variety of technic...
详细信息
This paper addresses a real-life unidimensional cutting stock problem. The objective is not only to minimize trim loss, as in traditional cutting stock problems, but also to minimize cutting time. A variety of technical constraints are taken into account. These constraints often arise in the iron and steel cutting industry. Since cutting stock problems are well known to be NP-hard, it is prohibitive to obtain optimal solutions. We develop approximation algorithms for different purposes: quick response algorithms for individual customer requirement planning to build a quotation, and elaborate algorithms to provide a production plan for the next day. These latter algorithms are submitted to less strict computation time limitations. Computational results show that our algorithms improve by 8% the performance of our partner company where the cutting plan had been carried out manually by very experienced people. Numerical comparison for small sized problems shows that these algorithms provide solutions very close to optimal. These algorithms have been implemented in the company.
Given a graph with k greater than or equal to 2 different nonnegative weights associated with each edge e and a cost function c: R-k --> R+, consider the problem of finding a minimum-cost edge subset possessing a c...
详细信息
Given a graph with k greater than or equal to 2 different nonnegative weights associated with each edge e and a cost function c: R-k --> R+, consider the problem of finding a minimum-cost edge subset possessing a certain property P. We prove that this problem is weakly NP-hard for a wide class of properties P and costs c, including paths, spanning trees, cuts, joins, etc. We suggest a simple approximation algorithm for this problem and find its performance guarantee. (C) 2002 Elsevier Science B.V. All rights reserved.
We consider a problem of allocating limited quantities of M types of resources among N independent activities that evolve over T epochs. In each epoch, we assign to each activity a task which consumes resources, gener...
详细信息
We consider a problem of allocating limited quantities of M types of resources among N independent activities that evolve over T epochs. In each epoch, we assign to each activity a task which consumes resources, generates utility, and determines the subsequent state of the activity. We study the complexity of, and approximation algorithms for, maximizing average utility. (c) 2005 Elsevier B.V. All rights reserved.
The exposure of a path p in a sensor field is a measure of the likelihood that an object traveling along p is detected by at least one sensor from a network of sensors, and is formally defined as an integral over all ...
详细信息
The exposure of a path p in a sensor field is a measure of the likelihood that an object traveling along p is detected by at least one sensor from a network of sensors, and is formally defined as an integral over all points x of p of the sensibility (the strength of the signal coming from x) times the element of path length. The minimum exposure path (MEP) problem is, given a pair of points x and y inside a sensor field, to find a path between x and y of minimum exposure. In this article we introduce the first rigorous treatment of the problem, designing an approximation algorithm for the MEP problem with guaranteed performance characteristics. Given a convex polygon P of size n with O(n) sensors inside it and any real number epsilon > 0, our algorithm finds a path in P whose exposure is within an 1 + epsilon factor of the exposure of the MEP, in time O(n/epsilon(2)psi log n), where. is a geometric characteristic of the field. We also describe a framework for a faster implementation of our algorithm, which reduces the time by a factor of approximately Theta(1/epsilon), while keeping the same approximation ratio.
Constant-factor, polynomial-time approximation algorithms are presented for two variations of the traveling salesman problem with time windows. In the first variation, the traveling repairman problem, the goal is to f...
详细信息
Constant-factor, polynomial-time approximation algorithms are presented for two variations of the traveling salesman problem with time windows. In the first variation, the traveling repairman problem, the goal is to find a path that visits the maximum possible number of locations during their time windows. In the second variation, the speeding deliveryman problem, the goal is to find a path that uses the minimum possible speedup to visit all locations during their time windows. For both variations, the time windows are of unit length, and the distance metric is based on a weighted, undirected graph. algorithms with improved approximation ratios are given for the case when the input is defined on a tree rather than a general graph. The algorithms are also extended to handle time windows whose lengths fall in any bounded range.
We introduce and study a generalization of the classic sequential testing problem, asking to identify the correct state of a given series system that consists of independent stochastic components. In this setting, cos...
详细信息
We introduce and study a generalization of the classic sequential testing problem, asking to identify the correct state of a given series system that consists of independent stochastic components. In this setting, costly tests are required to examine the state of individual components, which are sequentially tested until the correct system state can be uniquely identified. The goal is to propose a policy that minimizes the expected testing cost, given a-priori probabilistic information on the stochastic nature of each individual component. Unlike the classic setting, where variables are tested one after the other, we allow multiple tests to be conducted simultaneously, at the expense of incurring an additional set-up cost. The main contribution of this article consists in showing that the batch testing problem can be approximated in polynomial time within factor 6.829 + epsilon, for any fixed epsilon epsilon (0, 1). In addition, we explain how, in spite of its highly nonlinear objective function, the batch testing problem can be formulated as an approximate integer program of polynomial size, while blowing up its expected cost by a factor of at most 1 + epsilon. Finally, we conduct extensive computational experiments, to demonstrate the practical effectiveness of these algorithms as well as to evaluate their limitations. (C) 2016 Wiley Periodicals, Inc.
The achromatic number for a graph G = dropV,E drop is the largest integer m such that there is a partition of V into disjoint independent sets {V-1,. . . , V-m} such that for each pair of distinct sets V-i,V-J,V- V-i ...
详细信息
The achromatic number for a graph G = dropV,E drop is the largest integer m such that there is a partition of V into disjoint independent sets {V-1,. . . , V-m} such that for each pair of distinct sets V-i,V-J,V- V-i boolean OR V-j is not an independent set in G. Yannakakis and Gavril (1980, SIAM J. Appl. Math. 38, 364-372) proved that determining this value for general graphs is NP-complete. For n-vertex graphs we present the first o(n) approximation algorithm for this problem. We also present an O(n(5/12)) approximation algorithm for graphs with girth at least 5 and a constant approximation algorithm for trees. (C) 2001 Elsevier Science.
We propose a 2-approximation algorithm for the maximum independent set problem for a unit disk graph. The time and space complexities are O(n(3)) and O(n(2)), respectively. For a penny graph, our proposed 2-approximat...
详细信息
We propose a 2-approximation algorithm for the maximum independent set problem for a unit disk graph. The time and space complexities are O(n(3)) and O(n(2)), respectively. For a penny graph, our proposed 2-approximation algorithm works in O(n logn) time using O(n) space. We also propose a polynomial-time approximation scheme (PTAS) for the maximum independent set problem for a unit disk graph. Given an integer k > 1, it produces a solution of size 1/(1+1/k)(2) vertical bar OPT vertical bar in O(k(4)n(sigma k) (logk) + nlogn) time and O(n + klogk) space, where OPT is the subset of disks in an optimal solution and ak sigma k <= 2. For a penny graph, the proposed PTAS produces a solution of size 1/(1+1/k) vertical bar OPT vertical bar in O(2(2 sigma k)nk + nlogn) time using O(2(2 sigma k)+n) space. (C) 2014 Elsevier B.V. All rights reserved.
We address a variant of the classical knapsack problem in which an upper bound is imposed on the number of items that can be selected. This problem arises in the solution of real-life cutting stock problems by column ...
详细信息
We address a variant of the classical knapsack problem in which an upper bound is imposed on the number of items that can be selected. This problem arises in the solution of real-life cutting stock problems by column generation, and may be used to separate cover inequalities with small support within cutting-plane approaches to integer linear programs. We focus our attention on approximation algorithms for the problem, describing a linear-storage Polynomial Time approximation Scheme (PTAS) and a dynamic-programming based Fully Polynomial Time approximation Scheme (FPTAS). The main ideas contained in our PTAS are used to derive PTAS's for the knapsack problem and its multi-dimensional generalization which improve on the previously proposed PTAS's. We finally illustrate better PTAS's and FPTAS's for the subset sum case of the problem in which profits and weights coincide. (C) 2000 Elsevier Science B.V. All rights reserved.
暂无评论