We consider the Max-Buying Problem with Limited Supply, in which there are n items, with copies of each item i, and m consumers such that each consumer b has a valuation for item i. The goal is to find a pricing p and...
详细信息
We consider the Max-Buying Problem with Limited Supply, in which there are n items, with copies of each item i, and m consumers such that each consumer b has a valuation for item i. The goal is to find a pricing p and an allocation of items to consumers that maximize the revenue, with every item allocated to at most consumers, every consumer receives at most one item, and if a consumer b receives item i, then . We present a randomized -approximation for the Max-Buying Problem with Limited Supply and show how to derandomize it, improving the previously known upper bound of 2. The algorithm uses an integer programming formulation with an exponential number of variables to do a probabilistic rounding and it explores some structure of the problem that might be useful when developing approximations for other pricing problems. We also present a PTAS for the price ladder variant, in which the pricing must be non-increasing (that is, ), improving the previously known upper bound of 4.
We consider the problem of multiple sequence alignment under a fixed evolutionary tree: given a tree whose leaves are labeled by sequences, find ancestral sequences to label its internal nodes so as to minimize the to...
详细信息
We consider the problem of multiple sequence alignment under a fixed evolutionary tree: given a tree whose leaves are labeled by sequences, find ancestral sequences to label its internal nodes so as to minimize the total length of the tree, where the length of an edge is the edit distance between the sequences labeling its endpoints. We present a new polynomial-time approximation algorithm for this problem, and analyze its performance on regular d-ary trees with d a constant. On such a tree, the algorithm finds a solution within a factor (d + 1)/(d - 1) of the minimum in O(k(d)T(d, n) + k(2d)n(2)) time, where k is the number of leaves in the tree, n is the length of the longest sequence labeling a leaf, and T(d, n) is the time to compute a Steiner point for d sequences of length at most n. (A Steiner point for a set Y of sequences is a sequence P that minimizes the sum of the edit distances from P to each sequence in Y. The time T(d,n) is O(d2(d)n(d)), given O(ds(d+1))-time preprocessing for an alphabet of size s.) The approximation algorithm is conceptually simple and easy to implement, and actually applies to any metric space in which a Steiner point for any fixed-sized set can be computed in polynomial time. We also introduce a new problem, bottleneck tree-alignment, in which the objective is to label the internal nodes of the tree so as to minimize the length of the longest edge. We describe an exponential-time exact algorithm for the case of unit-cost edit operations, and show there is a simple linear-time approximation algorithm for the general case that finds a solution within a factor O(log k) of the minimum. 1998 Published by Elsevier Science 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.
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.
作者：
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 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.
We analyze approximation algorithms for several variants of the traveling salesman problem with multiple objective functions. First, we consider the symmetric TSP (STSP) with gamma-triangle inequality. For this proble...
详细信息
We analyze approximation algorithms for several variants of the traveling salesman problem with multiple objective functions. First, we consider the symmetric TSP (STSP) with gamma-triangle inequality. For this problem, we present a deterministic polynomial-time algorithm that achieves an approximation ratio of min{1 + gamma, 2 gamma(2)/2 gamma(2) - 2 gamma+1} + epsilon and a randomized approximation algorithm that achieves a ratio of 2 gamma(3)+2 gamma(2)/3 gamma(2)-2 gamma+1 + epsilon. In particular, we obtain a 2 + e approximation for multi-criteria metric STSP. Then we show that multi-criteria cycle cover problems admit fully polynomial-time randomized approximation schemes. Based on these schemes, we present randomized approximation algorithms for STSP with. - triangle inequality ( ratio 1+gamma/1+3 gamma-4 gamma(2) + epsilon), asymmetric TSP (ATSP) with. - triangle inequality ( ratio 1/2 + gamma(3)/1-3 gamma(2) + epsilon), STSP with weights one and two ( ratio 4/3) and ATSP with weights one and two ( ratio 3/2).
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.
暂无评论