共查询到3条相似文献,搜索用时 0 毫秒
1.
Mikhail Y. Kovalyov Marie-Claude Portmann Ammar Oulamara 《Journal of Combinatorial Optimization》2006,12(3):279-295
We consider a series repairable system that includes n components and assume that it has just failed because exactly one of its components has failed. The failed component is unknown.
Probability of each component to be responsible for the failure is given. Each component can be tested and repaired at given
costs. Both testing and repairing operations are assumed to be perfect, that is, the result of testing a component is a true
information that this component is failed or active (not failed), and the result of repairing is that the component becomes
active. The problem is to find a sequence of testing and repairing operations over the components such that the system is
always repaired and the total expected cost of testing and repairing the components is minimized. We show that this problem
is equivalent to minimizing a quadratic pseudo-boolean function. Polynomially solvable special cases of the latter problem
are identified and a fully polynomial time approximation scheme (FPTAS) is derived for the general case. Computer experiments
are provided to demonstrate high efficiency of the proposed FPTAS. In particular, it is able to find a solution with relative
error ɛ = 0.1 for problems with more than 4000 components within 5 minutes on a standard PC with 1.2 Mhz processor. 相似文献
2.
The objective of the Interconnecting Highways problem is to construct roads of minimum total length to interconnect n given highways under the constraint that the roads can intersect each highway only at one point in a designated interval which is a line segment. We present a polynomial time approximation scheme for this problem by applying Arora's framework (Arora, 1998; also available from http:www.cs.princeton.edu/~arora). For every fixed c > 1 and given any n line segments in the plane, a randomized version of the scheme finds a
-approximation to the optimal cost in O(n
O(c)log(n) time. 相似文献
3.
Maria Liazi Ioannis Milis Fanny Pascual Vassilis Zissimopoulos 《Journal of Combinatorial Optimization》2007,14(4):465-474
The Densest k-Subgraph (DkS) problem asks for a k-vertex subgraph of a given graph with the maximum number of edges. The problem is strongly NP-hard, as a generalization of
the well known Clique problem and we also know that it does not admit a Polynomial Time Approximation Scheme (PTAS). In this paper we focus on
special cases of the problem, with respect to the class of the input graph. Especially, towards the elucidation of the open
questions concerning the complexity of the problem for interval graphs as well as its approximability for chordal graphs,
we consider graphs having special clique graphs. We present a PTAS for stars of cliques and a dynamic programming algorithm
for trees of cliques.
M.L. is co-financed within Op. Education by the ESF (European Social Fund) and National Resources.
V.Z. is partially supported by the Special Research Grants Account of the University of Athens under Grant 70/4/5821. 相似文献