共查询到20条相似文献,搜索用时 31 毫秒
1.
Stefan Porschen 《Discrete Applied Mathematics》2007,155(11):1408-1419
In this paper the class of mixed Horn formulas is introduced that contain a Horn part and a 2-CNF (conjunctive normal form) (also called quadratic) part. We show that SAT remains NP-complete for such instances and also that any CNF formula can be encoded in terms of a mixed Horn formula in polynomial time. Further, we provide an exact deterministic algorithm showing that SAT for mixed Horn formulas containing n variables is solvable in time O(20.5284n). A strong argument showing that it is hard to improve a time bound of O(2n/2) for mixed Horn formulas is provided. We also obtain a fixed-parameter tractability classification for SAT restricted to mixed Horn formulas C of at most k variables in its positive 2-CNF part providing the bound O(∥C∥20.5284k). We further show that the NP-hard optimization problem minimum weight SAT for mixed Horn formulas can be solved in time O(20.5284n) if non-negative weights are assigned to the variables. Motivating examples for mixed Horn formulas are level graph formulas [B. Randerath, E. Speckenmeyer, E. Boros, P. Hammer, A. Kogan, K. Makino, B. Simeone, O. Cepek, A satisfiability formulation of problems on level graphs, ENDM 9 (2001)] and graph colorability formulas. 相似文献
2.
A drawback to using local search algorithms to address NP-hard discrete optimization problems is that many neighborhood functions have an exponential number of local optima that are not global optima (termed L-locals). A neighborhood function η is said to be stable if the number of L-locals is polynomial. A stable neighborhood function ensures that the number of L-locals does not grow too large as the instance size increases and results in improved performance for many local search algorithms. This paper studies the complexity of stable neighborhood functions for NP-hard discrete optimization problems by introducing neighborhood transformations. Neighborhood transformations between discrete optimization problems consist of a transformation of problem instances and a corresponding transformation of solutions that preserves the ordering imposed by the objective function values. In this paper, MAX Weighted Boolean SAT (MWBS), MAX Clause Weighted SAT (MCWS), and Zero-One Integer Programming (ZOIP) are shown to be NPO-complete with respect to neighborhood transformations. Therefore, if MWBS, MCWS, or ZOIP has a stable neighborhood function, then every problem in NPO has a stable neighborhood function. These results demonstrate the difficulty of finding effective neighborhood functions for NP-hard discrete optimization problems.This research is supported in part by the Air Force Office of Scientific Research (F49620-01-1-0007, FA9550-04-1-0110). 相似文献
3.
On the complexity of a class of combinatorial optimization problems with uncertainty 总被引:2,自引:0,他引:2
Igor Averbakh 《Mathematical Programming》2001,90(2):263-272
We consider a robust (minmax-regret) version of the problem of selecting p elements of minimum total weight out of a set of m elements with uncertainty in weights of the elements. We present a polynomial algorithm with the order of complexity O((min {p,m-p})2
m) for the case where uncertainty is represented by means of interval estimates for the weights. We show that the problem is
NP-hard in the case of an arbitrary finite set of possible scenarios, even if there are only two possible scenarios. This
is the first known example of a robust combinatorial optimization problem that is NP-hard in the case of scenario-represented
uncertainty but is polynomially solvable in the case of the interval representation of uncertainty.
Received: July 1998 / Accepted: May 2000?Published online March 22, 2001 相似文献
4.
In this paper we study multiprocessor and open shop scheduling problems from several points of view. We explore a tight dependence
of the polynomial solvability/intractability on the number of allowed preemptions. For an exhaustive interrelation, we address
the geometry of problems by means of a novel graphical representation. We use the so-called preemption and machine-dependency
graphs for preemptive multiprocessor and shop scheduling problems, respectively. In a natural manner, we call a scheduling
problem acyclic if the corresponding graph is acyclic. There is a substantial interrelation between the structure of these
graphs and the complexity of the problems. Acyclic scheduling problems are quite restrictive; at the same time, many of them
still remain NP-hard. We believe that an exhaustive study of acyclic scheduling problems can lead to a better understanding
and give a better insight of general scheduling problems.
We show that not only acyclic but also a special non-acyclic version of periodic job-shop scheduling can be solved in polynomial
(linear) time. In that version, the corresponding machine dependency graph is allowed to have a special type of the so-called
parti-colored cycles. We show that trivial extensions of this problem become NP-hard. Then we suggest a linear-time algorithm
for the acyclic open-shop problem in which at most m−2 preemptions are allowed, where m is the number of machines. This result is also tight, as we show that if we allow one less preemption, then this strongly
restricted version of the classical open-shop scheduling problem becomes NP-hard. In general, we show that very simple acyclic
shop scheduling problems are NP-hard. As an example, any flow-shop problem with a single job with three operations and the
rest of the jobs with a single non-zero length operation is NP-hard. We suggest linear-time approximation algorithm with the
worst-case performance of
(
, respectively) for acyclic job-shop (open-shop, respectively), where
(‖ℳ‖, respectively) is the maximal job length (machine load, respectively). We show that no algorithm for scheduling acyclic
job-shop can guarantee a better worst-case performance than
. We consider two special cases of the acyclic job-shop with the so-called short jobs and short operations (restricting the
maximal job and operation length) and solve them optimally in linear time. We show that scheduling m identical processors with at most m−2 preemptions is NP-hard, whereas a venerable early linear-time algorithm by McNaughton yields m−1 preemptions. Another multiprocessor scheduling problem we consider is that of scheduling m unrelated processors with an additional restriction that the processing time of any job on any machine is no more than the
optimal schedule makespan C
max *. We show that the (2m−3)-preemptive version of this problem is polynomially solvable, whereas the (2m−4)-preemptive version becomes NP-hard. For general unrelated processors, we guarantee near-optimal (2m−3)-preemptive schedules. The makespan of such a schedule is no more than either the corresponding non-preemptive schedule
makespan or max {C
max *,p
max }, where C
max * is the optimal (preemptive) schedule makespan and p
max is the maximal job processing time.
E.V. Shchepin was partially supported by the program “Algebraical and combinatorial methods of mathematical cybernetics” of
the Russian Academy of Sciences.
N. Vakhania was partially supported by CONACyT grant No. 48433. 相似文献
5.
The complexity of searching minimum difference covers, both in Z+ and in Zn, is studied. We prove that these two optimization problems are NP-hard. To obtain this result, we characterize those sets—called extrema—having themselves plus zero as minimum difference cover. Such a combinatorial characterization enables us to show that testing whether sets are not extrema, both in Z+ and in Zn, is NP-complete. However, for these two decision problems we exhibit pseudo-polynomial time algorithms. 相似文献
6.
Anthony Man-Cho So 《Mathematical Programming》2011,129(2):357-382
Due to their fundamental nature and numerous applications, sphere constrained polynomial optimization problems have received
a lot of attention lately. In this paper, we consider three such problems: (i) maximizing a homogeneous polynomial over the
sphere; (ii) maximizing a multilinear form over a Cartesian product of spheres; and (iii) maximizing a multiquadratic form
over a Cartesian product of spheres. Since these problems are generally intractable, our focus is on designing polynomial-time
approximation algorithms for them. By reducing the above problems to that of determining the L
2-diameters of certain convex bodies, we show that they can all be approximated to within a factor of Ω((log n/n)
d/2–1) deterministically, where n is the number of variables and d is the degree of the polynomial. This improves upon the currently best known approximation bound of Ω((1/n)
d/2–1) in the literature. We believe that our approach will find further applications in the design of approximation algorithms
for polynomial optimization problems with provable guarantees. 相似文献
7.
《Optimization》2012,61(6):906-918
The paper is dedicated to the computation complexity of multi-objective optimization problems on graphs. The classes of multi-objective problems with polynomial complexity or being polynomially reduced to be NP-hard are marked out. The unsolvability of a series of combinatorial multi-objective problems has been set up by means of linear convolution algorithm. The sufficient conditions under which these algorithms are statistically efficient have also been obtained. 相似文献
8.
Sanjeev Arora 《Mathematical Programming》2003,97(1-2):43-69
Traveling Salesman, Steiner Tree, and many other famous geometric optimization problems are NP-hard. Since we do not expect
to design efficient algorithms that solve these problems optimally, researchers have tried to design approximation algorithms,
which can compute a provably near-optimal solution in polynomial time.
We survey such algorithms, in particular a new technique developed over the past few years that allows us to design approximation
schemes for many of these problems. For any fixed constant c> 0, the algorithm can compute a solution whose cost is at most (1 + c) times the optimum. (The running time is polynomial for every fixed c> 0, and in many cases is even nearly linear.) We describe how these schemes are designed, and survey the status of a large
number of problems.
Received: December 2, 2002 / Accepted: April 28, 2003
Published online: May 28, 2003
Supported by a David and Lucile Packard Fellowship, NSF grant CCR-0098180, NSF ITR grant CCR-0205594 相似文献
9.
Ilya Kapovich Alexei Myasnikov Paul Schupp Vladimir Shpilrain 《Advances in Mathematics》2005,190(2):91-359
We investigate the average-case complexity of decision problems for finitely generated groups, in particular, the word and membership problems. Using our recent results on “generic-case complexity”, we show that if a finitely generated group G has word problem solvable in subexponential time and has a subgroup of finite index which possesses a non-elementary word-hyperbolic quotient group, then the average-case complexity of the word problem of G is linear time, uniformly with respect to the collection of all length-invariant measures on G. This results applies to many of the groups usually studied in geometric group theory: for example, all braid groups Bn, all groups of hyperbolic knots, many Coxeter groups and all Artin groups of extra-large type. 相似文献
10.
The integer equal flow problem is an NP-hard network flow problem, in which all arcs in given sets R1,…,Rℓ must carry equal flow. We show that this problem is effectively inapproximable, even if the cardinality of each set Rk is two. When ℓ is fixed, it is solvable in polynomial time. 相似文献
11.
问题的复杂性概念起源于离散的图灵计算机理论的研究,在离散优化问题的研究中被广泛的接受.近期连续优化领域的很多文章中提及NP难这个概念.从而来对比介绍离散优化和连续优化研究中这两个概念的差异. 相似文献
12.
In this paper, reference variable methods are proposed for solving nonlinear Minmax optimization problems with unconstraint
or constraints for the first time, it uses reference decision vectors to improve the methods in Vincent and Goh (J Optim Theory
Appl 75:501–519, 1992) such that its algorithm is convergent. In addition, a new method based on KKT conditions of min or
max constrained optimization problems is also given for solving the constrained minmax optimization problems, it makes the
constrained minmax optimization problems a problem of solving nonlinear equations by a complementarily function. For getting
all minmax optimization solutions, the cost function f(x, y) can be constrained as M
1 < f(x, y) < M
2 by using different real numbers M
1 and M
2. To show effectiveness of the proposed methods, some examples are taken to compare with results in the literature, and it
is easy to find that the proposed methods can get all minmax optimization solutions of minmax problems with constraints by
using different M
1 and M
2, this implies that the proposed methods has superiority over the methods in the literature (that is based on different initial
values to get other minmax optimization solutions). 相似文献
13.
Dorit S. Hochbaum 《Annals of Operations Research》2007,153(1):257-296
Nonlinear optimization algorithms are rarely discussed from a complexity point of view. Even the concept of solving nonlinear
problems on digital computers is not well defined. The focus here is on a complexity approach for designing and analyzing
algorithms for nonlinear optimization problems providing optimal solutions with prespecified accuracy in the solution space.
We delineate the complexity status of convex problems over network constraints, dual of flow constraints, dual of multi-commodity,
constraints defined by a submodular rank function (a generalized allocation problem), tree networks, diagonal dominant matrices,
and nonlinear knapsack problem’s constraint. All these problems, except for the latter in integers, have polynomial time algorithms
which may be viewed within a unifying framework of a proximity-scaling technique or a threshold technique. The complexity of many of these algorithms is furthermore best possible in that it matches lower bounds on the
complexity of the respective problems.
In general nonseparable optimization problems are shown to be considerably more difficult than separable problems. We compare
the complexity of continuous versus discrete nonlinear problems and list some major open problems in the area of nonlinear
optimization.
An earlier version of this paper appeared in 4OR, 3:3, 171–216, 2005. 相似文献
14.
Stanley Burris 《Mathematical Logic Quarterly》1995,41(2):173-182
We have two polynomial time results for the uniform word problem for a quasivariety Q: (a) The uniform word problem for Q can be solved in polynomial time iff one can find a certain congruence on finite partial algebras in polynomial time. (b) Let Q* be the relational class determined by Q. If any universal Horn class between the universal closure S(Q*) and the weak embedding closure S?(Q*) of Q* is finitely axiomatizable then the uniform word problem for Q is solvable in polynomial time. This covers Skolem's 1920 solution to the uniform word problem for lattices and Evans' 1953 applications of the weak embeddability property for finite partial V algebras. 相似文献
15.
The problem tackled in this paper deals with products of a finite number of triangular matrices in Max-Plus algebra, and more precisely with an optimization problem related to the product order. We propose a polynomial time optimization algorithm for 2×2 matrices products. We show that the problem under consideration generalizes numerous scheduling problems, like single machine problems or two-machine flow shop problems. Then, we show that for 3×3 matrices, the problem is NP-hard and we propose a branch-and-bound algorithm, lower bounds and upper bounds to solve it. We show that an important number of results in the literature can be obtained by solving the presented problem, which is a generalization of single machine problems, two- and three-machine flow shop scheduling problems. The branch-and-bound algorithm is tested in the general case and for a particular case and some computational experiments are presented and discussed. 相似文献
16.
Dorit S. Hochbaum 《4OR: A Quarterly Journal of Operations Research》2005,3(3):171-216
Nonlinear optimization algorithms are rarely discussed from a complexity point of view. Even the concept of solving nonlinear
problems on digital computers is not well defined. The focus here is on a complexity approach for designing and analyzing
algorithms for nonlinear optimization problems providing optimal solutions with prespecified accuracy in the solution space.
We delineate the complexity status of convex problems over network constraints, dual of flow constraints, dual of multi-commodity,
constraints defined by a submodular rank function (a generalized allocation problem), tree networks, diagonal dominant matrices,
and nonlinear Knapsack problem's constraint. All these problems, except for the latter in integers, have polynomial time algorithms
which may be viewed within a unifying framework of a proximity-scaling technique or a threshold technique. The complexity of many of these algorithms is furthermore best possible in that it matches lower bounds on the
complexity of the respective problems.
In general nonseparable optimization problems are shown to be considerably more difficult than separable problems. We compare
the complexity of continuous versus discrete nonlinear problems and list some major open problems in the area of nonlinear
optimization.
MSC classification:
90C30, 68Q25 相似文献
17.
S. V. Ivanov 《Geometriae Dedicata》2008,131(1):1-26
We study the computational complexity of basic decision problems of 3-dimensional topology, such as to determine whether a
triangulated 3-manifold is irreducible, prime, ∂-irreducible, or homeomorphic to a given 3-manifold M. For example, we prove that the problem to recognize whether a triangulated 3-manifold is homeomorphic to a 3-sphere, or
to a 2-sphere bundle over a circle, or to a real projective 3-space, or to a handlebody of genus g, is decidable in nondeterministic polynomial time (NP) of size of the triangulation. We also show that the problem to determine whether a triangulated orientable 3-manifold is
irreducible (or prime) is in PSPACE and whether it is ∂-irreducible is in coNP. The proofs improve and extend arguments of prior author’s article on the recognition problem for the 3-sphere.
相似文献
18.
Beth Novick 《Discrete Applied Mathematics》2009,157(8):1831-1839
In this paper we introduce a new class of clustering problems. These are similar to certain classical problems but involve a novel combination of ?p-statistics and ?q norms. We discuss a real world application in which the case p=2 and q=1 arises in a natural way. We show that, even for one dimension, such problems are NP-hard, which is surprising because the same 1-dimensional problems for the ‘pure’ ?2-statistic and ?2 norm are known to satisfy a ‘string property’ and can be solved in polynomial time. We generalize the string property for the case p=q. The string property need not hold when q≤p−1 and we show that instances may be constructed, for which the best solution satisfying the string property does arbitrarily poorly. We state some open problems and conjectures. 相似文献
19.
Friedrich Otto 《Semigroup Forum》1986,33(1):331-356
Two decision problems that are related to the properties of right-cancellativity and left-cancellativity, respectively, of
the monoidm
T defined by a presentation (Σ;T), are investigated. It is shown that these problems are undecidable in general. In fact, they
remain undecidable, even when they are restricted to presentations involving finite Church-Rosser Thue systems. On the other
hand, if only finite presentations involving monadic Church-Rosser Thue systems are considered, then these two problems become
decidable in polynomial space. 相似文献
20.
We generalize the concept of a break by considering pairs of arbitrary rounds. We show that a set of home-away patterns minimizing the number of generalized breaks cannot be found in polynomial time, unless P=NP. When all teams have the same break set, the decision version becomes easy; optimizing remains NP-hard. 相似文献