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 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.
We present approximation algorithms for the metric uncapacitated facility location problem and the metric k-median problem achieving guarantees of 3 and 6 respectively. The distinguishing feature of our algorithms is ...
详细信息
We present approximation algorithms for the metric uncapacitated facility location problem and the metric k-median problem achieving guarantees of 3 and 6 respectively. The distinguishing feature of our algorithms is their low running time: 0(m log m) and 0(m log m(L + log(n))) respectively, where n and m are the: total number of vertices and edges in the underlying complete bipartite graph on cities and facilities. The main algorithmic ideas are a new extension of the primal-dual schema and the use of Lagrangian relaxation to derive approximation algorithms.
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.
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.
We study two generalizations of classic clustering problems called dynamic ordered k -median and dynamic k-supplier, where the points that need clustering evolve over time, and we are allowed to move the cluster cente...
详细信息
We study two generalizations of classic clustering problems called dynamic ordered k -median and dynamic k-supplier, where the points that need clustering evolve over time, and we are allowed to move the cluster centers between consecutive time steps. In these dynamic clustering problems, the general goal is to minimize certain combinations of the service cost of points and the movement cost of centers, or to minimize one subject to some constraints on the other. We obtain a constant-factor approximation algorithm for dynamic ordered k-median under mild assumptions on the input. We give a 3-approximation for dynamic k-supplier and a multi-criteria approximation for its outlier version where some points can be discarded, when the number of time steps is two. We complement the algorithms with almost matching hardness results.(c) 2022 Elsevier Inc. All rights reserved.
Let G=(V,E) be a connected multigraph, whose edges are associated with labels specified by an integer-valued function L : E -> N. In addition, each label rho is an element of N has a non-negative cost c(rho). The m...
详细信息
Let G=(V,E) be a connected multigraph, whose edges are associated with labels specified by an integer-valued function L : E -> N. In addition, each label rho is an element of N has a non-negative cost c(rho). The minimum label spanning tree problem (MinLST) asks to find a spanning tree in G that minimizes the overall cost of the labels used by its edges. Equivalently, we aim at finding a minimum cost subset of labels I subset of N such that the edge set {e is an element of E : L(e) is an element of I} forms a connected subgraph spanning all vertices. Similarly, in the minimum label s - t path problem (MinLP) the goal is to identify an s-t path minimizing the combined cost of its labels. The main contributions of this paper are improved approximation algorithms and hardness results for MinLST and MinLP.
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.
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.
暂无评论