共查询到20条相似文献,搜索用时 15 毫秒
1.
F. Afrati 《Discrete Applied Mathematics》2006,154(4):622-639
We review approximability and inapproximability results for MIN-SUM scheduling problems and we focus on techniques for designing polynomial time approximation schemes for this class of problems. We present examples which illustrate the efficient use of the ratio partitioning and time partitioning techniques. 相似文献
2.
3.
We study complexity and approximation of min weighted node coloring in planar, bipartite and split graphs. We show that this problem is NP-hard in planar graphs, even if they are triangle-free and their maximum degree is bounded above by 4. Then, we prove that min weighted node coloring is NP-hard in P8-free bipartite graphs, but polynomial for P5-free bipartite graphs. We next focus on approximability in general bipartite graphs and improve earlier approximation results by giving approximation ratios matching inapproximability bounds. We next deal with min weighted edge coloring in bipartite graphs. We show that this problem remains strongly NP-hard, even in the case where the input graph is both cubic and planar. Furthermore, we provide an inapproximability bound of 7/6−ε, for any ε>0 and we give an approximation algorithm with the same ratio. Finally, we show that min weighted node coloring in split graphs can be solved by a polynomial time approximation scheme. 相似文献
5.
We prove the first inapproximability bounds to study approximation hardness for a min-max k-tree cover problem and its variants. The problem is to find a set of k trees to cover vertices of a given graph with metric edge weights, so as to minimize the maximum total edge weight of any of the k trees. Our technique can also be applied to improve inapproximability bounds for min-max problems that use other covering objectives, such as stars, paths, and tours. 相似文献
6.
M. Locatelli 《Journal of Optimization Theory and Applications》2009,140(1):93-102
We discuss the complexity of a class of highly structured global optimization problems, namely the maximization of separable
functions, with each one-dimensional component convex and nondecreasing, over polytopes defined by a 0-1 constraint matrix
with at most two variables involved in each constraint. In particular, we prove some inapproximability and approximability
results. 相似文献
7.
We give the first polynomial time approximability characterization of denseweighted instances of MAX‐CUT, and some other dense weighted 𝒩𝒫‐hard problems in terms of their empirical weight distributions. This also gives the first almost sharp characterization of inapproximability of unweighted 0, 1 MAX‐BISECTION instances in terms of their density parameter. © 2000 John Wiley & Sons, Inc. Random Struct. Alg., 16: 314–332, 2000 相似文献
8.
S. Guillemot 《Discrete Optimization》2011,8(1):50-60
We introduce the Longest Compatible Sequence () problem. This problem deals with p-sequences, which are strings on a given alphabet where each letter occurs at most once. The problem takes as input a collection of -sequences on a common alphabet of size , and seeks a -sequence on which respects the precedence constraints induced by each input sequence, and is of maximal length with this property. We investigate the parameterized complexity and the approximability of the problem. As a by-product of our hardness results for the problem, we derive new hardness results for the Longest Common Subsequence problem and other problems that are hard for the -hierarchy. 相似文献
9.
《Journal of Discrete Algorithms》2008,6(4):627-650
Suppose that each vertex of a graph G is either a supply vertex or a demand vertex and is assigned a positive real number, called the supply or the demand. Each demand vertex can receive “power” from at most one supply vertex through edges in G. One thus wishes to partition G into connected components by deleting edges from G so that each component C either has no supply vertex or has exactly one supply vertex whose supply is at least the sum of demands in C, and wishes to maximize the fulfillment, that is, the sum of demands in all components with supply vertices. This maximization problem is known to be NP-hard even for trees having exactly one supply vertex and strongly NP-hard for general graphs. In this paper, we focus on the approximability of the problem. We first show that the problem is MAXSNP-hard and hence there is no polynomial-time approximation scheme (PTAS) for general graphs unless . We then present a fully polynomial-time approximation scheme (FPTAS) for series-parallel graphs having exactly one supply vertex. 相似文献
10.
Michael O Albertson 《Journal of Combinatorial Theory, Series B》1976,20(1):84-93
A subset of the vertices of a graph is independent if no two vertices in the subset are adjacent. The independence number α(G) is the maximum number of vertices in an independent set. We prove that if G is a planar graph on N vertices then . 相似文献
11.
We give a -approximation algorithm for minimizing total weighted completion time on a single machine under release time and precedence constraints. This settles a recent conjecture on the approximability of this scheduling problem (Skutella, 2016). 相似文献
12.
Miroslav Chlebík 《Discrete Applied Mathematics》2007,155(2):172-179
The MINIMUM 2SAT-DELETION problem is to delete the minimum number of clauses in a 2SAT instance to make it satisfiable. It is one of the prototypes in the approximability hierarchy of minimization problems Khanna et al. [Constraint satisfaction: the approximability of minimization problems, Proceedings of the 12th Annual IEEE Conference on Computational Complexity, Ulm, Germany, 24-27 June, 1997, pp. 282-296], and its approximability is largely open. We prove a lower approximation bound of , improving the previous bound of by Dinur and Safra [The importance of being biased, Proceedings of the 34th Annual ACM Symposium on Theory of Computing (STOC), May 2002, pp. 33-42, also ECCC Report TR01-104, 2001]. For highly restricted instances with exactly four occurrences of every variable we provide a lower bound of . Both inapproximability results apply to instances with no mixed clauses (the literals in every clause are both either negated, or unnegated).We further prove that any k-approximation algorithm for the MINIMUM 2SAT-DELETION problem polynomially reduces to a (2-2/(k+1))-approximation algorithm for the MINIMUM VERTEX COVER problem.One ingredient of these improvements is our proof that the MINIMUM VERTEX COVER problem is hardest to approximate on graphs with perfect matching. More precisely, the problem to design a ρ-approximation algorithm for the MINIMUM VERTEX COVER on general graphs polynomially reduces to the same problem on graphs with perfect matching. This improves also on the results by Chen and Kanj [On approximating minimum vertex cover for graphs with perfect matching, Proceedings of the 11st ISAAC, Taipei, Taiwan, Lecture Notes in Computer Science, vol. 1969, Springer, Berlin, 2000, pp. 132-143]. 相似文献
13.
Tomás Domínguez Benavides 《Journal of Mathematical Analysis and Applications》1985,105(1):176-186
Let X be a Banach space, C a bounded closed subset of X, A a convex closed subset of X, a complete metric space formed by all α-nonexpansive mappings fC → A and a complete metric space formed by α-nonexpansive differentiable mappings fC → X. The following assertions are proved in this paper: (1) Properness of I ? f is a generic property in (2)the subset of formed by all α-contractive mappings is of Baire first category in ; and (3) for every y?X, the functional equation x ? f(x) = y has generically a finite number of solutions for f in . Some applications to the fixed point theory and calculation of the topological degree are given. 相似文献
14.
Melvyn B. Nathanson 《Journal of Number Theory》1974,6(4):324-333
An asymptotic basis of order h is minimal if no proper subset of is an asymptotic basis of order h. Examples are constructed of minimal asymptotic bases, and also of an asymptotic basis of order two no subset of which is minimal.If is a set of nonnegative integers which is not a basis (resp. asymptotic basis) of order h, but such that every proper superset of is a basis (resp. asymptotic basis) of order h, then is a maximal nonbasis (resp. maximal asymptotic nonbasis) of order h. Examples of such sets are constructed, and it is proved that every set not a basis of order h is a subset of a maximal nonbasis of order h. 相似文献
15.
16.
We consider the general Cauchy problem with initial data in a Hilbert space and with a formal dissipative linear generator. A complete parametrization is known of the (abstract) boundary conditions which make this problem well set. We exhibit a distinguished subset E of the set of boundary conditions and demonstrate explicitly that the evolution associated with each B in can be represented as a (time independent) average over the evolutions associated with B′ in E. Applications are discussed to Schrödinger equations in bounded regions or with singular potentials. 相似文献
17.
P.C Trombi 《Journal of Functional Analysis》1978,30(1):83-105
Let G be a real reductive Lie group of class , and suppose that the split rank of G is one. We show that the asymptotic expansions of the Eisenstein integrals given in Harish-Chandra (1) give uniform approximation off of a certain naturally defined compact subset of , the unitary dual of A; G = KAN being an Iwasawa decomposition of G. 相似文献
18.
We consider the problem of finding a strictly fundamental cycle basis of minimum weight in the cycle space associated with an undirected connected graph G, where a nonnegative weight is assigned to each edge of G and the total weight of a basis is defined as the sum of the weights of all the cycles in the basis. Several heuristics have been proposed to tackle this NP-hard problem, which has some interesting applications. In this paper we show that this problem is APX-hard, even when restricted to unweighted graphs, and hence does not admit a polynomial-time approximation scheme, unless P=NP. Using a recent result on the approximability of lower-stretch spanning trees (Elkin et al. (2005) [7]), we obtain that the problem is approximable within O(log2nloglogn) for arbitrary graphs. We obtain tighter approximability bounds for dense graphs. In particular, the problem restricted to complete graphs admits a polynomial-time approximation scheme. 相似文献
19.
Elie Sanchez 《Fuzzy Sets and Systems》1984,12(3):237-248
Assuming that 1 is any operation defined on a product set X × Y and taking values on a set Z, it can be extended to fuzzy sets by means of Zadeh's extension principle. Given a fuzzy subset C of Z, it is here shown how to solve the equation (or ) when a fuzzy subset A of X (or a fuzzy subset B of Y) is given. The methodology we provide includes, as a special case, the resolution of fuzzy arithmetical operations, i.e. when 1 stands for +, ?, × or ÷, extended to fuzzy numbers (fuzzy subsets of the real line). The paper is illustrated with several examples in fuzzy arithmetic. 相似文献
20.
Let be the set of all n × n real matrices which have a positive determinant. We show here that at least 2n ? 1 matrices are needed to “see” each matrix in . Also, any finite subset of can be “seen” from a class of at most 2n ? 1 matrices in . 相似文献