A polynomially solvable case of the pooling problem

Answering a question of Haugland, we show that the pooling problem with one pool and a bounded number of inputs can be solved in polynomial time by solving a polynomial number of linear programs of polynomial size. We also give an overview of known complexity results and remaining open problems to further characterize the border between (strongly) NP-hard and polynomially solvable cases of the pooling problem.     

A polynomially solvable class of quadratic semi-assignment problems

The Quadratic Semi-Assignment Problem (QSAP) models a large variety of practical applications. In the present note we will consider a particular class of QSAP that can be solved by determining the maximum cost flow on a network. This class of problems arises in schedule synchronization and in transportation.     

A class of polynomially solvable linear complementarity problems

Although the general linear complementarity problem (LCP) is NP-complete, there are special classes that can be solved in polynomial time. One example is the type where the defining matrix is nondegenerate and for which the n-step property holds. In this paper we consider an extension of the property to the degenerate case by introducing the concept of an extended n-step vector and matrix. It is shown that the LCP defined by such a matrix is polynomially solvable as well.     

The bilinear assignment problem: complexity and polynomially solvable special cases

Mathematical Programming - In this paper we study the bilinear assignment problem (BAP) with size parameters m and n, $$mle n$$ . BAP is a generalization of the well known quadratic assignment...     

An unbounded Sum-of-Squares hierarchy integrality gap for a polynomially solvable problem

In this expository article, we study optimization problems specified via linear and relative entropy inequalities. Such relative entropy programs (REPs) are convex optimization problems as the relative entropy function is jointly convex with respect to both its arguments. Prominent families of convex programs such as geometric programs (GPs), second-order cone programs, and entropy maximization problems are special cases of REPs, although REPs are more general than these classes of problems. We provide solutions based on REPs to a range of problems such as permanent maximization, robust optimization formulations of GPs, and hitting-time estimation in dynamical systems. We survey previous approaches to some of these problems and the limitations of those methods, and we highlight the more powerful generalizations afforded by REPs. We conclude with a discussion of quantum analogs of the relative entropy function, including a review of the similarities and distinctions with respect to the classical case. We also describe a stylized application of quantum relative entropy optimization that exploits the joint convexity of the quantum relative entropy function.     

A solvable case of the variance minimization problem

An algorithm is derived, which solves the completion time variance (CTV) problem with equal processing times in O(n log n) time. This result indicates that the special case formulated by Merten and Muller [1] is well solvable.     

A solvable case of the traveling salesman problem

LetD = d _ij be the distance matrix defining a traveling salesman problem. IfD is upper triangular, i.e.d _ij = 0, fori j, then the traveling salesman problem can be solved with an amount of computation approximately equal to that required for an assignment problem of the same dimension.     

Classes of subcubic planar graphs for which the independent set problem is polynomially solvable

We prove the polynomial solvability of the independent set problem for some family of classes of the planar subcubic graphs.     

A new solvable case of the traveling salesman problem

Mathematical Programming -     

On some polynomially solvable cases and approximate algorithms in the optimal communication tree construction problem

Considering an arbitrary undirected n-vertex graph with nonnegative edge weights, we seek to construct a spanning tree minimizing the sum over all vertices of the maximal weights of the incident edges. We find some particular cases of polynomial solvability and show that the minimal span whose edge weights lie in the closed interval [a, b] is a $\left( {2 - \frac{{2a}} {{a + b + 2b/(n - 2)}}} \right) $ -approximate solution, and the problem of constructing a 1.00048-approximate solution is NP-hard. We propose a heuristic polynomial algorithm and perform its a posteriori analysis.     

A case of imbedding problem with a solvable kernel

Journal of Mathematical Sciences - It is shown for the solution of the imbedding problem of algebraic number fields with a finite solvable kernel one can take a field if the orders of the kernel...     

A class of polynomially solvable 0-1 programming problems and an application

It is well known that general 0-1 programming problems are NP-Complete and their optimal solutions cannot be found with polynomial-time algorithms unless P=NP. In this paper, we identify a specific class of 0-1 programming problems that is polynomially solvable, and propose two polynomial-time algorithms to find its optimal solutions. This class of 0-1 programming problems commits to a wide range of real-world industrial applications. We provide an instance of representative in the field of supply chain man...     

A note on a polynomial time solvable case of the quadratic assignment problem

We identify a class of instances of the Koopmans–Beckmann form of the Quadratic Assignment Problem that are solvable in polynomial time. This class is characterized by a path structure in the flow data and a grid structure in the distance data. Chr18b, one of the test problems in the QAPLIB, is in this class even though this feature of it has not been noticed until now.     

Sequencing jobs that require common resources on a single machine: A solvable case of the TSP

In this paper a one-machine scheduling model is analyzed wheren different jobs are classified intoK groups depending on which additional resource they require. The change-over time from one job to another consists of the removal time or of the set-up time of the two jobs. It is sequence-dependent in the sense that the change-over time is determined by whether or not the two jobs belong to the same group. The objective is to minimize the makespan. This problem can be modeled as an asymmetric Traveling Salesman Problem (TSP) with a specially structured distance matrix. For this problem we give a polynomial time solution algorithm that runs in O(n logn) time. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.     

A local characterization of the johnson scheme

Within the Johnson schemeI(m, d) we find the graphK(m, d) ofd-subsets of anm-set, two such adjacent when disjoint. Among all connected graphs,K(m, d) is characterized by the isomorphism type of its vertex neighborhoods providedm is sufficiently large compared tod. Partial support provided by NSF (USA), SERC (UK), ZWO (NL).     

A new asymmetric pyramidally solvable class of the traveling salesman problem

We present a new method of identifying a class of asymmetric matrices for which an optimal traveling salesman tour exists that is pyramidal. The new class generalizes two previously known classes of matrices and includes some new matrices as well.     

The two-convex-polygons TSP: A solvable case

In this paper, the Travelling Salesman Problem whenm points are on one convex polygonP, andn points are on another convex polygonQ, insideP, is polynomially solved. For this specific case, anO(m ³ n ³) time andO(m ² n ²) space algorithm to obtain the tour with minimum length is provided.     

A mixed-integer linear programming problem which is efficiently solvable

Efficient algorithms are known for the simple linear programming problem where each inequality is of the form x_j − x_i ≤ a_ij. Furthermore, these techniques extend to the integer linear programming variant of the problem. This paper gives an efficient solution to the mixed-integer linear programming variant where some, but not necessarily all, of the unknowns are required to be integers. The algorithm we develop is based on a graph representation of the constraint system and runs in O(|V||E| + |V|²lg|V|) time. It has several applications including optimal retiming of synchronous circuitry, VLSI layout compaction in the presence of power and ground buses, and PERT scheduling with periodic constraints.     

A solvable hyperbolic free boundary problem modelling tumour regrowth

Recently, Tian and Friedman et al. developed a mathematical model on brain tumour recurrence after resection [J.P. Tian, A. Friedman, J. Wang and E.A. Chiocca, Modeling the effects of resection, radiation and chemotherapy in glioblastoma, J. Neuro-Oncol. 91(3) (2009), pp. 287–293]. The model is a free boundary problem with a hyperbolic system of nonlinear partial differential equations. In this article, we conduct a rigorous analysis on this hyperbolic system and prove the local and global existence and uniqueness of the solution. It is well known that most nonlinear free boundary problems are impossible to solve in terms of explicit analytical solutions. In contrast, the free boundary problem in this study is solvable, and the explicit solution is found using the backward characteristic curve method. This explicit solution is then validated by numerical simulation results. An interesting finding in this study is that the problem can be treated as a hyperbolic system defined on an infinite domain where the initial condition has a first-type discontinuity.     

On the similarity problem for polynomially bounded operators on hilbert space

Partial solutions are obtained to Halmos’ problem, whether or not any polynomially bounded operator on a Hilbert spaceH is similar to a contraction. Central use is made of Paulsen’s necessary and sufficient condition, which permits one to obtain bounds on ‖S‖ ‖S ^?1‖, whereS is the similarity. A natural example of a polynomially bounded operator appears in the theory of Hankel matrices, defining $$R_f = \left( {\begin{array}{*{20}c} {S*} \\ 0 \\ \end{array} \begin{array}{*{20}c} {\Gamma _f } \\ S \\ \end{array} } \right)$$ onl ² ⊕l ², whereS is the shift and Γ _f the Hankel operator determined byf withf′ ∈ BMOA. Using Paulsen’s condition, we prove thatR _f is similar to a contraction. In the general case, combining Grothendieck’s theorem and techniques from complex function theory, we are able to get in the finite dimensional case the estimate $$\left\| S \right\|\left\| {S^{ - 1} } \right\| \leqq M^4 log(dim H)$$ whereSTS ^?1 is a contraction and assuming \(\left\| {p\left( T \right)} \right\| \leqq M\left\| p \right\|_\infty \) wheneverp is an analytic polynomial on the disc.