共查询到20条相似文献,搜索用时 218 毫秒
1.
This paper investigates, for the first time in the literature, the approximation of min–max (regret) versions of classical problems like shortest path, minimum spanning tree, and knapsack. For a constant number of scenarios, we establish fully polynomial-time approximation schemes for the min–max versions of these problems, using relationships between multi-objective and min–max optimization. Using dynamic programming and classical trimming techniques, we construct a fully polynomial-time approximation scheme for min–max regret shortest path. We also establish a fully polynomial-time approximation scheme for min–max regret spanning tree and prove that min–max regret knapsack is not at all approximable. For a non-constant number of scenarios, in which case min–max and min–max regret versions of polynomial-time solvable problems usually become strongly NP-hard, non-approximability results are provided for min–max (regret) versions of shortest path and spanning tree. 相似文献
2.
We study the approximation of the least core value and the least core of supermodular cost cooperative games. We provide a framework for approximation based on oracles that approximately determine maximally violated constraints. This framework yields a 3-approximation algorithm for computing the least core value of supermodular cost cooperative games, and a polynomial-time algorithm for computing a cost allocation in the 2-approximate least core of these games. This approximation framework extends naturally to submodular profit cooperative games. For scheduling games, a special class of supermodular cost cooperative games, we give a fully polynomial-time approximation scheme for computing the least core value. For matroid profit games, a special class of submodular profit cooperative games, we give exact polynomial-time algorithms for computing the least core value as well as a least core cost allocation. 相似文献
3.
Jesús A. De Loera Raymond Hemmecke Matthias Köppe Robert Weismantel 《Mathematical Programming》2008,115(2):273-290
We show the existence of a fully polynomial-time approximation scheme (FPTAS) for the problem of maximizing a non-negative
polynomial over mixed-integer sets in convex polytopes, when the number of variables is fixed. Moreover, using a weaker notion
of approximation, we show the existence of a fully polynomial-time approximation scheme for the problem of maximizing or minimizing
an arbitrary polynomial over mixed-integer sets in convex polytopes, when the number of variables is fixed.
A conference version of this article, containing a part of the results presented here, appeared in Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms, Miami, FL, January 22–24, 2006, pp. 743–748. The first author gratefully acknowledges support from NSF grant DMS-0608785, a 2003 UC-Davis Chancellor’s fellow award,
the Alexander von Humboldt foundation, and IMO Magdeburg. The remaining authors were supported by the European TMR network
ADONET 504438. 相似文献
4.
We consider a procurement problem where suppliers offer concave quantity discounts. The resulting continuous knapsack problem involves the minimization of a sum of separable concave functions. We identify polynomially solvable special cases of this NP-hard problem, and provide a fully polynomial-time approximation scheme for the general problem. 相似文献
5.
6.
We analyze the asymptotic behavior of the Flow Deviation Method, first presented in 1971 by Fratta, Gerla and Kleinrock, and
show that when applied to packing linear programs such as the maximum concurrent flow problem, it yields a fully polynomial-time
approximation scheme.
Received: December 28, 2000 / Accepted: May 25, 2001?Published online October 2, 2001 相似文献
7.
Approximation algorithms for single machine scheduling with one unavailability period 总被引:2,自引:0,他引:2
In this paper, we investigate the single machine scheduling problem with release dates and tails and a planned unavailability
time period. We show that the problem admits a fully polynomial-time approximation scheme when the tails are equal. We derive
an approximation algorithm for the general case and we show that the worst-case bound of the sequence yielded by Schrage’s
algorithm is equal to 2 and that this bound is tight. Some consequences of this result are also presented.
相似文献
8.
《Operations Research Letters》2020,48(2):109-114
In this note, we consider the capacitated facility location problem when the transportation costs of the instance satisfy the Monge property. We show that a straightforward dynamic program finds the optimal solution when the demands are polynomially bounded. When demands are not polynomially bounded, we give a fully polynomial-time approximation scheme by adapting an algorithm and analysis of Van Hoesel and Wagelmans (2001). 相似文献
9.
《Operations Research Letters》2020,48(6):687-692
We study the assortment optimization problem under the newly proposed cascade browse model. We propose a constant approximate solution to this problem. As a byproduct, we propose the first fully polynomial-time approximation scheme (FPTAS) for the classic assortment optimization problem subject to one capacity constraint and one cardinality constraint. We also studied a joint pricing and sequencing problem under the above model and develop a constant approximate solution to this problem. 相似文献
10.
《Operations Research Letters》2023,51(4):421-424
We study a basic scheduling problem with resource constraints: A number of jobs need to be scheduled on two parallel identical machines with the objective of minimizing the makespan, subject to the constraint that jobs may require a unit of one of the given renewable resources during their execution. For this NP-hard problem, we develop a fully polynomial-time approximation scheme (FPTAS). Our FPTAS makes a novel use of existing algorithms for the subset-sum problem and the open shop scheduling problem. 相似文献
11.
Denis D. Mauá Cassio P. de Campos Marco Zaffalon 《International Journal of Approximate Reasoning》2012,53(8):1183-1199
Credal networks relax the precise probability requirement of Bayesian networks, enabling a richer representation of uncertainty in the form of closed convex sets of probability measures. The increase in expressiveness comes at the expense of higher computational costs. In this paper, we present a new variable elimination algorithm for exactly computing posterior inferences in extensively specified credal networks, which is empirically shown to outperform a state-of-the-art algorithm. The algorithm is then turned into a provably good approximation scheme, that is, a procedure that for any input is guaranteed to return a solution not worse than the optimum by a given factor. Remarkably, we show that when the networks have bounded treewidth and bounded number of states per variable the approximation algorithm runs in time polynomial in the input size and in the inverse of the error factor, thus being the first known fully polynomial-time approximation scheme for inference in credal networks. 相似文献
12.
We consider the parallel-machine scheduling problem in which the processing time of a job is a simple linear increasing function of its starting time. The objective is to minimize the total completion time. We give a fully polynomial-time approximation scheme (FPTAS) for the case with m identical machines, where m is fixed. This study solves an open problem that has been posed in the literature for ten years. 相似文献
13.
《Operations Research Letters》2020,48(5):682-686
In this paper, we consider the joint effects of product substitution and market size endogenization. Under the substitution effects, a product’s demand may be cannibalized by other substitutable products; while the market size, measured by the number of customers who are interested in the products from the same category, may be largely influenced by the product offer set. We establish the computational complexity for the assortment problem under the joint effects, and develop a fully polynomial-time approximation scheme (FPTAS). 相似文献
14.
F. Zeynep Sargut 《Operations Research Letters》2007,35(4):549-557
We study a new class of capacitated economic lot-sizing problems. We show that the problem is NP-hard in general and derive a fully polynomial-time approximation algorithm under mild conditions on the cost functions. Furthermore, we develop a polynomial-time algorithm for the case where all cost functions are concave. 相似文献
15.
A. V. Kel’manov S. M. Romanchenko S. A. Khamidullin 《Numerical Analysis and Applications》2017,10(4):313-323
We consider a strongly NP-hard Euclidean problem of finding a subsequence in a finite sequence. The criterion of the solution is the minimum sum of squared distances from the elements of a sought subsequence to its geometric center (centroid). It is assumed that a sought subsequence contains a given number of elements. In addition, a sought subsequence should satisfy the following condition: the difference between the indices of each previous and subsequent points is bounded with given lower and upper constants.We present an approximation algorithm of solving the problem and prove that it is a fully polynomial-time approximation scheme (FPTAS) when the space dimension is bounded by a constant. 相似文献
16.
DONGHUI CHEN DING-ZHU DU XIAO-DONG HU GUO-HUI LIN LUSHENG WANG GUOLIANG XUE 《Journal of Global Optimization》2000,18(1):17-33
Given n terminals in the Euclidean plane and a positive constant, find a Steiner tree interconnecting all terminals with the minimum number of Steiner points such that the Euclidean length of each edge is no more than the given positive constant. This problem is NP-hard with applications in VLSI design, WDM optical networks and wireless communications. In this paper, we show that (a) the Steiner ratio is 1/ 4, that is, the minimum spanning tree yields a polynomial-time approximation with performance ratio exactly 4, (b) there exists a polynomial-time approximation with performance ratio 3, and (c) there exists a polynomial-time approxi-mation scheme under certain conditions. 相似文献
17.
Hatem Hadda 《Optimization Letters》2012,6(3):559-569
In this paper, we develop a polynomial-time approximation scheme for the two-machine flow shop scheduling problem with several
availability constraints on the first machine, under the resumable scenario. 相似文献
18.
A. A. Ageev V. P. Il’ev A. V. Kononov A. S. Talevnin 《Journal of Applied and Industrial Mathematics》2007,1(1):1-8
The computational complexity of the graph approximation problem is investigated. It is shown that the different variants of this problem are NP-hard both for undirected and directed graphs. A polynomial-time approximation scheme (PTAS) for one of the variants is presented. 相似文献
19.
This paper studies single machine scheduling with a fixed non-availability interval. The processing time of a job is a linear increasing function of its starting time, and each job has a release date. A job is either rejected by paying a penalty cost or accepted and processed on the machine. The objective is to minimize the makespan of the accepted jobs and the total rejection penalties of the rejected jobs. We present a fully polynomial-time approximation scheme for the problem. We also show that the special case without non-availability interval can be solved using the same method with a lower order. 相似文献
20.
This paper presents a hybrid approximation scheme for the Max-SNP-complete minimum-cost target coverage problem in wireless
sensor networks. LP-rounding and set-cover selection are polynomial-time approximations for this problem. Our hybrid scheme
combines these two methods using a crafted convex combination. We show that the hybrid scheme with appropriately chosen coefficients
produces much better approximations than either of the two methods used alone. We show that, through a large number of numerical
experiments, the hybrid scheme never exceeds an approximation ratio of 1.14, providing up to 14.86% improvement over the best
approximations previously known. 相似文献