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. PUBLICATION ABSTRACT
Liveness of an extended S 3PR Liu, Ding; Li, ZhiWu; Zhou, MengChu
Automatica (Oxford),
2010, Volume:
46, Issue:
6
Journal Article
Peer reviewed
Most existing prevention methods tackle the deadlock issue arising in flexible manufacturing systems modeled with Petri nets by adding monitors and arcs. Instead, this paper presents a new one based ...on a characteristic structure of WS
3PR, an extension of System of Simple Sequential Processes with Resources (S
3PR) with weighted arcs. The numerical relationships among weights, and between weights and initial markings are investigated based on simple circuits of resource places, which are the simplest structure of circular wait, rather than siphons. A WS
3PR satisfying a proposed restriction is inherently deadlock-free and live by configuring its initial markings. A set of polynomial algorithms are developed to implement the proposed method. Several examples are used to illustrate them.
Quality of service (
QoS
) routing is known to be an NP-hard problem in case of two or more additive constraints, and several exact algorithms and heuristics have been proposed to address this issue. ...In this paper, we consider a particular two-constrained quality of service routing problem maximizing path stability with a limited path length in the quest of improving routability in dynamic multi-hop mobile wireless ad hoc networks. First, we propose a novel exact algorithm to solve the optimal weight-constrained path problem. We instantiate our algorithm to solve the most stable path not exceeding a certain number of hops, in polynomial time. This algorithm is then applied to the practical case of proactive routing in dynamic multi-hop wireless ad hoc networks. In these networks, an adequate compromise between route stability and its length in hops is essential for appropriately mitigating the impact of the network dynamics on the validity of established routes. Secondly, we set up a common framework for the comparison between three families of proactive routing: the shortest path-based routing, the most stable path-based routing and our proposed most stable constrained path routing. We show then through extensive simulations that routing based on our proposed algorithm selects appropriate stable paths yielding a very high routability with an average path length just above that of the shortest paths.
It is shown that the discount factor needed to solve an undiscounted mean payoff stochastic game to optimality is exponentially close to 1, even in one-player games with a single random node and ...polynomially bounded rewards and transition probabilities. For the class of the so-called irreducible games with perfect information and a constant number of random nodes, we obtain a pseudo-polynomial algorithm using discounts.
In this note we give an easier proof of the known result that the car sequencing problem is NP-hard, and point out that it is NP-hard in the strong sense. We show that a previous claim of ...NP-completeness is incorrect, and instead we give a sufficient condition of membership of NP. We also provide a pseudo-polynomial algorithm for a special case.
The Maximum Weight Independent Set (MWIS) Problem on graphs with vertex weights asks for a set of pairwise nonadjacent vertices of maximum total weight. Being one of the most investigated problem on ...graphs, it is well known to be NP-complete and hard to approximate. Several graph classes for which MWIS can be solved in polynomial time have been introduced in the literature. This note shows that MWIS can be solved in polynomial time for (P6,co-banner)-free graphs – where a P6 is an induced path of 6 vertices and a co-banner is a graph with vertices a,b,c,d,e and edges ab,bc,cd,ce,de – so extending different analogous known results for other graph classes, namely, P4-free, 2K2-free, (P5,co-banner)-free, and (P6,triangle)-free graphs. The solution algorithm is based on an idea/algorithm of Farber (1989) 10, leading to a dynamic programming approach for MWIS, and needs none of the aforementioned known results as sub-procedure.
► The note deals with the Maximum Weight Independent Set (MWIS) Problem. ► It shows that MWIS can be efficiently solved for (P6,co-banner)-free graphs. ► It extends different analogous known results for other graph classes. ► It needs none of the aforementioned known results as sub-procedure. ► It is based on a previous idea of Martin Farber.
We consider a robust location–allocation problem with uncertainty in demand coefficients. Specifically, for each demand point, only an interval estimate of its demand is known and we consider the ...problem of determining where to locate a new service when a given fraction of these demand points must be served by the utility. The optimal solution of this problem is determined by the “minimax regret” location, i.e., the point that minimizes the worst-case loss in the objective function that may occur because a decision is made without knowing which state of nature will take place. For the case where the demand points are vertices of a network we show that the robust location–allocation problem can be solved in O(min{
p,
n
−
p}
n
3
m) time, where
n is the number of demand points,
p (
p
<
n) is the fixed number of demand points that must be served by the new service and
m is the number of edges of the network.
List partitions generalize list colorings and list homomorphisms. (We argue that they may be called list "semihomomorphisms.") Each symmetric matrix M over 0,1,* defines a list partition problem. ...Different choices of the matrix M lead to many well-known graph theoretic problems, often related to graph perfection, including the problem of recognizing split graphs, finding homogeneous sets, clique cutsets, stable cutsets, and so on. The recent proof of the strong perfect graph theorem employs three kinds of decompositions that can be viewed as list partitions. We develop tools which allow us to classify the complexity of many list partition problems and, in particular, yield the complete classification for small matrices M. Along the way, we obtain a variety of specific results, including generalizations of Lovasz's communication bound on the number of clique-versus-stable-set separators, polynomial time algorithms to recognize generalized split graphs, a polynomial algorithm for the list version of the clique cutset problem, and the first subexponential algorithm for the skew cutset problem of Chvatal. We also show that the dichotomy (NP-complete versus polynomial time solvable), conjectured for certain graph homomorphism problems, would, if true, imply a slightly weaker dichotomy (NP-complete versus quasi-polynomial) for our list partition problems.
PDF
