Logistical planning problems are complicated in practice because planners have to deal with the challenges of demand planning and supply replenishment, while taking into account the issues of (i) inventory perishabili...
详细信息
Logistical planning problems are complicated in practice because planners have to deal with the challenges of demand planning and supply replenishment, while taking into account the issues of (i) inventory perishability and storage charges, (ii) management of backlog and/or lost sales, and (iii) cost saving opportunities due to economies of scale in order replenishment and transportation. It is therefore not surprising that many logistical planning problems are computationally difficult, and finding a good solution to these problems necessitates the development of many ad hoc algorithmic procedures to address various features of the planning problems. In this article, we identify simple conditions and structural properties associated with these logistical planning problems in which the warehouse is managed as a cross-docking facility. Despite the nonlinear cost structures in the problems, we show that a solution that is within epsilon-optimality can be obtained by solving a related piece-wise linear concave cost multi-commodity network flow problem. An immediate consequence of this result is that certain classes of logistical planning problems can be approximated by a factor of (1 + epsilon) in polynomial time. This significantly improves upon the results found in literature for these classes of problems. We also show that the piece-wise linear concave cost network flow problem can be approximated to within a logarithmic factor via a large scale linear programming relaxation. We use polymatroidal constraints to capture the piece-wise concavity feature of the cost functions. This gives rise to a unified and generic LP-based approach for a large class of complicated logistical planning problems. (C) 2009 Wiley Periodicals, Inc. Naval Research Logistics 56: 642-658, 2009
The expansion of a hypergraph, a natural extension of the notion of expansion in graphs, is defined as the minimum over all cuts in the hypergraph of the ratio of the number of the hyperedges cut to the size of the sm...
详细信息
The expansion of a hypergraph, a natural extension of the notion of expansion in graphs, is defined as the minimum over all cuts in the hypergraph of the ratio of the number of the hyperedges cut to the size of the smaller side of the cut. We study the Hypergraph Small-Set Expansion problem, which, for a parameter delta e (0,1/2], asks to compute the cut having the least expansion while having at most delta fraction of the vertices on the smaller side of the cut. We present two algorithms. Our first algorithm gives an O similar to(delta(-) (1) root logn)-approximation. The second algorithm finds a set with expansion O-similar to(delta(-1)(root d(max)r(-1)logr Phi* + Phi*)) in an r-uniform hypergraph with maximum degree d(max) (where Phi* is the expansion of the optimal solution). Using these results, we also obtain algorithms for the Small-Set Vertex Expansion problem: we get an O similar to(sigma(-1)root logn)-approximation algorithm and an algorithm that finds a set with vertex expansion. O-similar to(dagger(-1)root Phi(V)logd(max )+ delta(-1)Phi(V)) (where Phi(V) is the vertex expansion of the optimal solution). For delta = 1/2, Hypergraph Small-Set Expansion is equivalent to the hypergraph expansion problem. In this case, our approximation factor of O(root logn) for expansion in hypergraphs matches the corresponding approximation factor for expansion in graphs due to Arora, Rao, and Vazirani (JACM 2009).
This article addresses an important routing problem that arises in surveillance applications involving two heterogeneous vehicles. As the addressed routing problem is NP-Hard, we develop an approximation algorithm and...
详细信息
This article addresses an important routing problem that arises in surveillance applications involving two heterogeneous vehicles. As the addressed routing problem is NP-Hard, we develop an approximation algorithm and heuristics to solve the problem. Our approach involves solving the routing problem in two main steps: Partitioning and Sequencing. Partitioning involves finding a distinct set of targets to be visited by each vehicle. Sequencing provides the order in which each vehicle must visit the subset of targets assigned to it. The problem of partitioning is tackled by solving a linear program (LP) obtained by relaxing some of the constraints of an integer programming model for the problem. We consider two LP models for partitioning. The first LP model is obtained by mainly relaxing both the integrality and degree constraints, whereas the second model relaxes mainly the integrality constraints. Once the targets are partitioned, the sequencing problem can be solved either by Hoogeveen's algorithm or by the Lin-Kernighan heuristic to yield an approximately optimal solution. Computational results show that the algorithms based on the second LP model, on an average, provided better (closer to the optimum) solutions as compared with those based on the first LP model. We also observed that for both the LP models, the average quality of solutions given by the heuristics were found to be within 4% of the optimum, whereas the average quality of solutions obtained from the approximation algorithms were within 8-20% of the optimum depending on the problem size. Copyright (C) 2011 John Wiley & Sons, Ltd.
作者：
Tan, XuehouWu, Gangs HanTokai Univ
Sch Informat Sci & Technol Hiratsuka Kanagawa 2591292 Japan Nanjing Univ
State Key Lab Novel Software Technol Nanjing 210093 Jiangsu Peoples R China
For a given convex polyhedron P of n vertices inside a sphere Q, we study the problem of cutting P out of Q by a sequence of plane cuts. The cost of a plane cut is the area of the intersection of the plane with Q, and...
详细信息
For a given convex polyhedron P of n vertices inside a sphere Q, we study the problem of cutting P out of Q by a sequence of plane cuts. The cost of a plane cut is the area of the intersection of the plane with Q, and the objective is to find a cutting sequence that minimizes the total cost. We present three approximation solutions to this problem: an O(n log n) time O(log(2) n)-factor approximation, an O(n(1.5) log n) time O(log n)-factor approximation, and an O(1)-factor approximation with exponential running time. Our results significantly improve upon the previous O(n(3)) time O(log(2) n)-factor approximation solution. (C) 2012 Elsevier B.V. All rights reserved.
In this paper we study a variant of the bin packing problem in which the items to be packed are structured as the leaves of a tree. The problem is motivated by document organization and retrieval. We show that the pro...
详细信息
In this paper we study a variant of the bin packing problem in which the items to be packed are structured as the leaves of a tree. The problem is motivated by document organization and retrieval. We show that the problem is NP-hard and we give approximation algorithms for the general case and for the particular case in which all the items have the same size. (C) 2003 Elsevier B.V. All rights reserved.
We consider the problem of time-constrained scheduling of packets in a communication network. Each packet has, in addition to its source and its destination, a release time and a deadline. The goal of an algorithm is ...
详细信息
We consider the problem of time-constrained scheduling of packets in a communication network. Each packet has, in addition to its source and its destination, a release time and a deadline. The goal of an algorithm is to maximize the number of packets that arrive to their destinations by their respective deadlines, given the network constraints. We consider the line network, and a setting where each node has a buffer of size B packets (where B can be finite or infinite), and each edge has capacity Ca parts per thousand yen1. To the best of our knowledge this is the first work to study time-constrained scheduling in a setting when buffers can be of limited size. We give approximation algorithms that achieve expected approximation ratio of O(max {log (au) n-log (au) B,1}+max {log I-au a'log pound (au) C,1}), where n is the length of the line, and I pound is the maximum slack a message can have (the slack is the number of time steps a message can be idle and still arrive within its deadline). A special case of our setting is the setting of buffers of unlimited capacity and edge capacities 1, which has been previously studied by Adler et al. (Theory Comput. Syst. 35(6):599-623, 2002). For this case our results considerably improve upon previous results: We obtain an approximation ratio of O(min{log*n,log*Sigma,log*M}) (where M is the number of messages in the instance), which is a significant improvement upon the results of Adler et al. who obtained a guarantee of O(min {log n,log I pound,log M}).
In this paper, we consider a variant of the knapsack problem. There are two knapsacks with probably different capacities, owned by two agents respectively. Given a set of items, each with a fixed size and a profit. Th...
详细信息
In this paper, we consider a variant of the knapsack problem. There are two knapsacks with probably different capacities, owned by two agents respectively. Given a set of items, each with a fixed size and a profit. The two agents select items and pack them into their own knapsacks under the capacity constraint. Same items can be packed simultaneously to different knapsacks. However, in this case the profit of such items may vary. One agent packs items into his knapsack to maximize the total profit, while another agent can only pack items into his knapsack as well but he cares about the total profits of items packed into two knapsacks. The latter agent is a leader while the former is a follower. We aim at designing an approximation algorithm for the leader assuming that the follower is selfish. For different settings we provide approximation results. (C) 2012 Elsevier B.V. All rights reserved.
The traditional approach for the problems of sorting permutations by rearrangements is to consider that all operations have the same unitary cost. In this case, the goal is to find the minimum number of allowed rearra...
详细信息
The traditional approach for the problems of sorting permutations by rearrangements is to consider that all operations have the same unitary cost. In this case, the goal is to find the minimum number of allowed rearrangements that are needed to sort a given permutation, and numerous efforts have been made over the past years regarding these problems. On the other hand, a long rearrangement (which is in fact a mutation) is more likely to disturb the organism. Therefore, weights based on the length of the segment involved may have an important role in the evolutionary process. In this paper we present the first results regarding problems of sorting permutations by length-weighted operations that consider rearrangement models with prefix and suffix variations of reversals and transpositions, which are the two most common types of genome rearrangements. Our main results are O (lg(2) n)-approximation algorithms for 10 such problems. (C) 2015 Elsevier B.V. All rights reserved.
Several problems that are NP-hard on general graphs are efficiently solvable on graphs with bounded treewidth. Efforts have been made to generalize treewidth and the related notion of pathwidth to digraphs. Directed t...
详细信息
Several problems that are NP-hard on general graphs are efficiently solvable on graphs with bounded treewidth. Efforts have been made to generalize treewidth and the related notion of pathwidth to digraphs. Directed treewidth, DAG-width and Kelly-width are some such notions which generalize treewidth, whereas directed pathwidth generalizes pathwidth. Each of these digraph width measures have an associated decomposition structure. In this paper, we present approximation algorithms for all these digraph width parameters. In particular, we give an 0 root logn)-approximation algorithm for directed treewidth, and an O (log(3/2) n)-approximation algorithm for directed pathwidth, DAG-width and Kelly-width. Our algorithms construct the corresponding decompositions whose widths agree with the above mentioned approximation factors. (C) 2014 Elsevier B.V. All rights reserved.
We study the problem of finding shortest tours/paths for "lawn mowing" and "milling" problems: Given a region in the plane, and given the shape of a "cutter" (typically, a circle or a squ...
详细信息
We study the problem of finding shortest tours/paths for "lawn mowing" and "milling" problems: Given a region in the plane, and given the shape of a "cutter" (typically, a circle or a square), find a shortest tour/path for the cutter such that every point within the region is covered by the cutter at some position along the tour/path. In the milling version of the problem, the cutter is constrained to stay within the region. The milling problem arises naturally in the area of automatic tool path generation for NC pocket machining. The lawn mowing problem arises in optical inspection, spray painting, and optimal search planning. Both problems are NP-hard in general. We give efficient constant-factor approximation algorithms for both problems. In particular, we give a (3 + epsilon)-approximation algorithm for the lawn mowing problem and a 2.5-approximation algorithm for the milling problem. Furthermore, we give a simple 6/5-approximation algorithm for the TSP problem in simple grid graphs, which leads to an 11/5-approximation algorithm for milling simple rectilinear polygons, (C) 2000 Elsevier Science B.V. All rights reserved.
暂无评论