Polynomial time algorithms for some classes of constrained nonconvex quadratic problems

In this paper we consider different classes of noneonvex quadratic problems that can be solved in polynomial time. We present an algorithm for the problem of minimizing the product of two linear functions over a polyhedron P in R ⁿ The complexity of the algorithm depends on the number of vertices of the projection of P onto the R ² space. In the worst-case this algorithm requires an exponential number of steps but its expected computational time complexity is polynomial. In addition, we give a characterization for the number of isolated local minimum areas for problems on this form.

Furthermore, we consider indefinite quadratic problems with variables restricted to be nonnegative. These problems can be solved in polynomial time if the number of negative eigenvalues of the associated symmetric matrix is fixed.     

A polynomial time algorithm to solve the single-item capacitated lot sizing problem with minimum order quantities and concave costs

This paper deals with the single-item capacitated lot sizing problem with concave production and storage costs, and minimum order quantity (CLSP-MOQ). In this problem, a demand must be satisfied at each period t over a planning horizon of T periods. This demand can be satisfied from the stock or by a production at the same period. When a production is made at period t, the produced quantity must be greater to than a minimum order quantity (L) and lesser than the production capacity (U). To solve this problem optimally, a polynomial time algorithm in O(T⁵) is proposed and it is computationally tested on various instances.     

The Hardness of Polynomial Equation Solving

Elimination theory was at the origin of algebraic geometry in the nineteenth century and now deals with the algorithmic solving of multivariate polynomial equation systems over the complex numbers or, more generally, over an arbitrary algebraically closed field. In this paper we investigate the intrinsic sequential time complexity of universal elimination procedures for arbitrary continuous data structures encoding input and output objects of elimination theory (i.e., polynomial equation systems) and admitting the representation of certain limit objects. Our main result is the following: let there be given such a data structure and together with this data structure a universal elimination algorithm, say P, solving arbitrary parametric polynomial equation systems. Suppose that the algorithm P avoids unnecessary branchings and that P admits the efficient computation of certain natural limit objects (as, e.g., the Zariski closure of a given constructible algebraic set or the parametric greatest common divisor of two given algebraic families of univariate polynomials). Then P$ cannot be a polynomial time algorithm. The paper contains different variants of this result and discusses their practical implications.     

Light affine lambda calculus and polynomial time strong normalization

Light Linear Logic (LLL) and Intuitionistic Light Affine Logic (ILAL) are logics that capture polynomial time computation. It is known that every polynomial time function can be represented by a proof of these logics via the proofs-as-programs correspondence. Furthermore, there is a reduction strategy which normalizes a given proof in polynomial time. Given the latter polynomial time “weak” normalization theorem, it is natural to ask whether a “strong” form of polynomial time normalization theorem holds or not. In this paper, we introduce an untyped term calculus, called Light Affine Lambda Calculus (λLA), which corresponds to ILAL. λLA is a bi-modal λ-calculus with certain constraints, endowed with very simple reduction rules. The main property of LALC is the polynomial time strong normalization: any reduction strategy normalizes a given λLA term in a polynomial number of reduction steps, and indeed in polynomial time. Since proofs of ILAL are structurally representable by terms of λLA, we conclude that the same holds for ILAL. This is a full version of the paper [21] presented at LICS 2001.     

Multivariate Polynomial Minimization and Its Application in Signal Processing

We make a conjecture that the number of isolated local minimum points of a 2n-degree or (2n+1)-degree r-variable polynomial is not greater than n ^r when n 2. We show that this conjecture is the minimal estimate, and is true in several cases. In particular, we show that a cubic polynomial of r variables may have at most one local minimum point though it may have 2^r critical points. We then study the global minimization problem of an even-degree multivariate polynomial whose leading order coefficient tensor is positive definite. We call such a multivariate polynomial a normal multivariate polynomial. By giving a one-variable polynomial majored below a normal multivariate polynomial, we show the existence of a global minimum of a normal multivariate polynomial, and give an upper bound of the norm of the global minimum and a lower bound of the global minimization value. We show that the quartic multivariate polynomial arising from broad-band antenna array signal processing, is a normal polynomial, and give a computable upper bound of the norm of the global minimum and a computable lower bound of the global minimization value of this normal quartic multivariate polynomial. We give some sufficient and necessary conditions for an even order tensor to be positive definite. Several challenging questions remain open.     

A polynomial time primal network simplex algorithm for minimum cost flows

Developing a polynomial time primal network simplex algorithm for the minimum cost flow problem has been a long standing open problem. In this paper, we develop one such algorithm that runs in O(min(n ²m lognC, n ²m² logn)) time, wheren is the number of nodes in the network,m is the number of arcs, andC denotes the maximum absolute arc costs if arc costs are integer and ∞ otherwise. We first introduce a pseudopolynomial variant of the network simplex algorithm called the “premultiplier algorithm”. We then develop a cost-scaling version of the premultiplier algorithm that solves the minimum cost flow problem in O(min(nm lognC, nm ² logn)) pivots. With certain simple data structures, the average time per pivot can be shown to be O(n). We also show that the diameter of the network polytope is O(nm logn).     

Polynomial Hulls of Subsets of T 2

This paper investigates the polynomial convexity of subsets of the two-torus. Given a compact subset K of T 2 , we find regions in K which do not contribute to the polynomial hull of K inside the bidisc.     

On Certain Fejér and Tchebychev Type Integrals

Let m and n denote a pair of positive integers. In this paper, we call upon the Hadamard product and computer algebra techniques to evaluate the Fejér integral π ^?1 ∫₀ ^π (sin mθ / sin θ) ²ⁿ dθ. Using symmetry arguments, it is proved that the value of this integral is an odd polynomial in m of degree 2n ? 1. This permits using polynomial curve fitting methods and mathematical software packages to obtain evaluation formulas for n relatively small. Some cases of the above integral with 2n replaced by 2n + 1 are also discussed. A familiar identity shows that these yield evaluations of integrals of powers of certain Tchebychev polynomials.     

Polynomial-time algorithm for fixed points of nontrivial morphisms

A word w is a fixed point of a nontrivial morphism h if w=h(w) and h is not the identity on the alphabet of w. The paper presents the first polynomial algorithm deciding whether a given finite word is such a fixed point. The algorithm also constructs the corresponding morphism, which has the smallest possible number of non-erased letters.     

Polynomial Pell's equation-II

The polynomial Pell's equation is X²−DY²=1, where D is a polynomial with integer coefficients and the solutions X,Y must be polynomials with integer coefficients. Let D=A²+2C be a polynomial in , where . Then for a prime, a necessary and sufficient condition for which the polynomial Pell's equation has a nontrivial solution is obtained. Furthermore, all solutions to the polynomial Pell's equation satisfying the above condition are determined.     

Minimizing the total completion time in a unit-time open shop with release times

We consider the problem of minimizing the total completion time in a unit-time open shop with release times where the number of machines is constant. Brucker and Krämer (1994) proved that this problem is solvable in polynomial time. However, the time complexity of the algorithm presented there is a polynom of a very high degree and, thus, the algorithm is not practicable even for a small number of machines. We give an O(n²) algorithm for the considered problem which is based on dynamic programming. The result is applied to solve a previously open problem with a special resource constraint raised by De Werra et al. (1991).     

Relations between the support of a compactly supported function and the exponential-polynomials spanned by its integer translates

The interrelation between the shape of the support of a compactly supported function and the space of all exponential-polynomials spanned by its integer translates is examined. The results obtained are in terms of the behavior of these exponential-polynomials on certain finite subsets ofZ ^s , which are determined by the support of the given function. Several applications are discussed. Among these is the construction of quasi-interpolants of minimal support and the construction of a piecewise-polynomial whose integer translates span a polynomial space which is not scale-invariant. As to polynomial box splines, it is proved here that in many cases a polynomial box spline admits a certain optimality condition concerning the space of the total degree polynomials spanned by its integer translates: This space is maximal compared with the spaces corresponding to other functions with the same supportCommunicated by Klaus Höllig.     

A faster capacity scaling algorithm for minimum cost submodular flow

We describe an O(n ⁴ hmin{logU,n ²logn}) capacity scaling algorithm for the minimum cost submodular flow problem. Our algorithm modifies and extends the Edmonds–Karp capacity scaling algorithm for minimum cost flow to solve the minimum cost submodular flow problem. The modification entails scaling a relaxation parameter δ. Capacities are relaxed by attaching a complete directed graph with uniform arc capacity δ in each scaling phase. We then modify a feasible submodular flow by relaxing the submodular constraints, so that complementary slackness is satisfied. This creates discrepancies between the boundary of the flow and the base polyhedron of a relaxed submodular function. To reduce these discrepancies, we use a variant of the successive shortest path algorithm that augments flow along minimum cost paths of residual capacity at least δ. The shortest augmenting path subroutine we use is a variant of Dijkstra’s algorithm modified to handle exchange capacity arcs efficiently. The result is a weakly polynomial time algorithm whose running time is better than any existing submodular flow algorithm when U is small and C is big. We also show how to use maximum mean cuts to make the algorithm strongly polynomial. The resulting algorithm is the first capacity scaling algorithm to match the current best strongly polynomial bound for submodular flow. Received: August 6, 1999 / Accepted: July 2001?Published online October 2, 2001     

On the minimum corridor connection problem and other generalized geometric problems

In this paper we discuss the complexity and approximability of the minimum corridor connection problem where, given a rectilinear decomposition of a rectilinear polygon into “rooms”, one has to find the minimum length tree along the edges of the decomposition such that every room is incident to a vertex of the tree. We show that the problem is strongly NP-hard and give a subexponential time exact algorithm. For the special case when the room connectivity graph is k-outerplanar the algorithm running time becomes cubic. We develop a polynomial time approximation scheme for the case when all rooms are fat and have nearly the same size. When rooms are fat but are of varying size we give a polynomial time constant factor approximation algorithm.     

An efficient algorithm for multi-hoist cyclic scheduling with fixed processing times

We consider no-wait production processes, where identical products are processed sequentially on n machines and transported by programmable hoists. We present an O(n⁵) algorithm that determines the minimum number of hoists required for all possible cycle-times; given the number of hoists, it also finds the minimum-time cyclic hoist-schedule.     

Polynomial Processes for Power Prices

ABSTRACT

Polynomial processes have the property that expectations of polynomial functions (of degree n, say) of the future state of the process conditional on the current state are given by polynomials (of degree ≤ n) of the current state. Here we explore the potential of polynomial maps of polynomial processes for modelling energy prices. We focus on the example of Alberta power prices, derive one- and two-factor models for spot prices. We examine their performance in numerical experiments, and demonstrate that the richness of the dynamics they are able to generate makes them well suited for modelling even extreme examples of energy price behaviour.     

A faster algorithm for 2-cyclic robotic scheduling with a fixed robot route and interval processing times

Consider an m-machine production line for processing identical parts served by a mobile robot. The problem is to find the minimum cycle time for 2-cyclic schedules, in which exactly two parts enter and two parts leave the production line during each cycle. This work treats a special case of the 2-cyclic robot scheduling problem when the robot route is given and the operation durations are to be chosen from prescribed intervals. The problem was previously proved to be polynomially solvable in O(m⁸log m) time. This paper proposes an improved algorithm with reduced complexity O(m⁴).     

Determining dimension of the solution component that contains a computed zero of a polynomial system

When the Jacobian of a computed numerical solution of a polynomial system in Cn allows very small singular values, the solution could be isolated with a multiple multiplicity or may belong to a solution component with positive dimension. The algorithm constructed in this article intends to differentiate those cases by determining the dimension of the solution component M in which the solution lies. Of particular interest is the case when dim(M)=0, then the solution is of course isolated. While the proposed algorithm is experimental, it has been tested successfully on the class of problems with the solution in question belonging to a reduced component. Numerical results are provided to illustrate the accuracy of the algorithm.     

On the focus order of planar polynomial differential equations

This paper is devoted to finding the highest possible focus order of planar polynomial differential equations. The results consist of two parts: (i) we explicitly construct a class of concrete systems of degree n, where n+1 is a prime p or a power of a prime pk, and show that these systems can have a focus order n²−n; (ii) we theoretically prove the existence of polynomial systems of degree n having a focus order n²−1 for any even number n. Corresponding results for odd n and more concrete examples having higher focus orders are given too.     

Improved heuristics for the minimum weight triangulation problem

Given a planar point setS, a triangulation ofS is a maximal set of non-intersecting line segments connecting the points. The minimum weight triangulation problem is to find a triangulation ofS such that the sum of the lengths of the line segments in it is the smallest. No polynomial time algorithm is known to produce the optimal or even a constant approximation of the optimal solution, and it is also unknown whether the problem is NP-hard. In this paper, we propose two improved heuristics, which triangulate a set ofn points in a plane inO(n ³) time and never do worse than the minimum spanning tree triangulation algorithm given by Lingas and the greedy spanning tree triangulation algorithm given by Heath and Pemmaraju. These two algorithms both produce an optimal triangulation if the points are the vertices of a convex polygon, and also do the same in some special cases.