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 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.     

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.     

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.     

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.     

A survey of the machine interference problem

This paper surveys the research published on the machine interference problem, also called the machine repairman problem, in which machines interfere with each other’s service. Our emphasis is on work that has appeared since the 1985 review by Stecke and Aronson. After describing the basic model and the scope of our study, we discuss the literature along several dimensions. We describe some of the more interesting papers, and offer some suggestions for topics holding particular promise for future studies. We conclude with comments about how the research has evolved over the past two decades.     

A problem in machine breakdown

Summary Consider a machine subject to breakdown. The machine, if working, performs a certain kind of task and the probability of completion of a task in time intervalt ist+o (t). The running time, set-up time (that elapses before repair starts) and the repair time are independent random variables, each following exponential distribution. Explicit expressions are derived for quantities of interest, for example (i) the variance of the number of tasks completed in an arbitrary time interval and (ii) the covariance between the number of tasks completed in two successive non-overlapping time intervals. Each result is presented in a slightly more general form obtained by considering that each task may consist of one or more pieces, the number of pieces in each task has a distribution with finite mean and variance.

---

Zusammenfassung Betrachtet wird eine Maschine unter Berücksichtigung technischer Störungen. Wenn die Maschine läuft, führt sie gewisse Arbeitsgänge durch. Die Wahrscheinlichkeit, daß ein Arbeitsgang in einem Zeitintervall der Länget beendet wird, beträgtt+o (t). Die Arbeitszeit, Wartezeit (Zeitspanne bis Reparaturbeginn bei Störung) und die Reparaturzeit sind unabhängige, exponentialverteilte Zufallsgrößen. Für gewisse interessierende Größen werden explizite Ausdrücke hergeleitet, z. B. (1) für die Varianz der Anzahl der durchgeführten Arbeitsgänge in einem gegebenen Zeitintervall und (2) für die Kovarianz zwischen den Anzahlen der durchgeführten Arbeitsgänge in zwei aufeinanderfolgenden disjunkten Zeitintervallen. Jedes Ergebnis wird in einer etwas allgemeineren Form dargestellt, die dadurch entsteht, daß angenommen wird, jeder Arbeitsgang bestünde aus mehreren Teilen, deren Anzahl einer Verteilung mit endlichem Mittelwert und endlicher Varianz genügt.

---

---

This research was conducted under Grant received from the University of Alabama Research Committee, Project No. 525, dated May 10, 1966.

---

Vorgel. v.:J. Nitsche.     

A unified formulation of the machine scheduling problem

A wide class of machine scheduling problems can be formulated as ILP problems and solved by branch and bound using the out-of-kilter algorithm for the solution of the subproblems.