Polynomial dual network simplex algorithms

We show how to use polynomial and strongly polynomial capacity scaling algorithms for the transshipment problem to design a polynomial dual network simplex pivot rule. Our best pivoting strategy leads to an O(m ² logn) bound on the number of pivots, wheren andm denotes the number of nodes and arcs in the input network. If the demands are integral and at mostB, we also give an O(m(m+n logn) min(lognB, m logn))-time implementation of a strategy that requires somewhat more pivots.Research supported by AFOSR-88-0088 through the Air Force Office of Scientific Research, by NSF grant DOM-8921835 and by grants from Prime Computer Corporation and UPS.Research supported by NSF Research Initiation Award CCR-900-8226, by U.S. Army Research Office Grant DAAL-03-91-G-0102, and by ONR Contract N00014-88-K-0166.Research supported in part by a Packard Fellowship, an NSF PYI award, a Sloan Fellowship, and by the National Science Foundation, the Air Force Office of Scientific Research, and the Office of Naval Research, through NSF grant DMS-8920550.     

Approximation algorithms for scheduling unrelated parallel machines

We consider the following scheduling problem. There arem parallel machines andn independent jobs. Each job is to be assigned to one of the machines. The processing of jobj on machinei requires timep _ij . The objective is to find a schedule that minimizes the makespan.Our main result is a polynomial algorithm which constructs a schedule that is guaranteed to be no longer than twice the optimum. We also present a polynomial approximation scheme for the case that the number of machines is fixed. Both approximation results are corollaries of a theorem about the relationship of a class of integer programming problems and their linear programming relaxations. In particular, we give a polynomial method to round the fractional extreme points of the linear program to integral points that nearly satisfy the constraints.In contrast to our main result, we prove that no polynomial algorithm can achieve a worst-case ratio less than 3/2 unlessP = NP. We finally obtain a complexity classification for all special cases with a fixed number of processing times.A preliminary version of this paper appeared in theProceedings of the 28th Annual IEEE Symposium on the Foundations of Computer Science (Computer Society Press of the IEEE, Washington, D.C., 1987) pp. 217–224.     

A polynomial-time simplex method for the maximumk-flow problem

A generalization of the maximum-flow problem is considered in which every unit of flow sent from the source to the sink yields a payoff of $k. In addition, the capacity of any arce can be increased at a per-unit cost of $c _e . The problem is to determine how much arc capacity to purchase for each arc and how much flow to send so as to maximize the net profit. This problem can be modeled as a circulation problem. The main result of this paper is that this circulation problem can be solved by the network simplex method in at mostkmn pivots. Whenc _e = 1 for each arce, this yields a strongly polynomial-time simplex method. This result uses and extends a result of Goldfarb and Hao which states that the standard maximum-flow problem can be solved by the network simplex method in at mostmn pivots.Research partially supported by Office of Naval Research Grant N00014-86-K-0689 at Purdue University.     

Algorithms for the optimum communication spanning tree problem

Optimum Communication Spanning Tree Problem is a special case of the Network Design Problem. In this problem given a graph, a set of requirements r _ij and a set of distances d _ij for all pair of nodes (i,j), the cost of communication for a pair of nodes (i,j), with respect to a spanning tree T is defined as r _ij times the length of the unique path in T, that connects nodes i and j. Total cost of communication for a spanning tree is the sum of costs for all pairs of nodes of G. The problem is to construct a spanning tree for which the total cost of communication is the smallest among all the spanning trees of G. The problem is known to be NP-hard. Hu (1974) solved two special cases of the problem in polynomial time. In this paper, using Hu’s result the first algorithm begins with a cut-tree by keeping all d _ij equal to the smallest d _ij . For arcs (i,j) which are part of this cut-tree the corresponding d _ij value is increased to obtain a near optimal communication spanning tree in pseudo-polynomial time. In case the distances d _ij satisfy a generalised triangle inequality the second algorithm in the paper constructs a near optimum tree in polynomial time by parametrising on the r _ij .     

Updating an optimal structured scheme

An optimal structured schedule at time t is considered for a set of jobs Z with given start and due date [d _i ,D _i ] volumes V_i (volume is defined as the number of homogeneous independent elementary operations of unit length that comprise the job), and penalty functions. The penalty for selecting an element of jobiZ at timet is _i (t). The schedule penalty is the total penalty of all the elements of all the jobs. An optimal schedule is a minimum-penalty schedule. We investigate the impact of changing the volume of a job from the setZ on the structure of the optimal schedule. Algorithms are proposed for handling the modified job set with both reduced and enlarged job volumes. These algorithms require ck computer operations, where k is the number of jobs in the original set, is the change in job volume (expressed by the number of units), andC is a constant.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 111, pp. 151–161, 1981.In conclusion, I would like to acknowledge the valuable attention of K. V. Shakhbazyan.     

Improved bounds on the max-flow min-cut ratio for multicommodity flows

In this paper we consider the worst case ratio between the capacity of min-cuts and the value of max-flow for multicommodity flow problems. We improve the best known bounds for the min-cut max-flow ratio for multicommodity flows in undirected graphs, by replacing theO(logD) in the bound byO(logk), whereD denotes the sum of all demands, andk demotes the number of commodities. In essence we prove that up to constant factors the worst min-cut max-flow ratios appear in problems where demands are integral and polynomial in the number of commodities.Klein, Rao, Agrawal, and Ravi have previously proved that if the demands and the capacities are integral, then the min-cut max-flow ratio in general undirected graphs is bounded byO(logClogD), whereC denotes the sum of all the capacities. Tragoudas has improved this bound toO(lognlogD), wheren is the number of nodes in the network. Garg, Vazirani and Yannakakis further improved this toO(logklogD). Klein, Plotkin and Rao have proved that for planar networks, the ratio isO(logD).Our result improves the bound for general networks toO(log² k) and the bound for planar networks toO(logk). In both cases our result implies the first non-trivial bound that is independent of the magnitude of the numbers involved. The method presented in this paper can be used to give polynomial time approximation algorithms to the minimum cuts in the network up to the above factors.Preliminary version appeared in Proceedings of the 25th Annual ACM Symposium on the Theory of Computing, 1993, 691-697.Research supported by U.S. Army Research Office Grant DAAL-03-91-G-0102, and by a grant from Mitsubishi Electric Laboratories.Research supported in part by a Packard Fellowship, an NSF PYI award, a Sloan Fellowship, and by the National Science Foundation, the Air Force Office of Scientific Research, and the Office of Naval Research, through NSF grant DMS-8920550.     

New steps in the amazing world of sequences and schedules

In this paper we consider classical shop problems:n jobs have to be processed onm machines. The processing timep _i,j of jobi on machinej is given for all operations (i, j). Each machine can process at most one job at a time and each job can be processed at most on one machine at a given time. The machine orders are fixed (job-shop) or arbitrary (open-shop). We have to determine a feasible combination of machine and job orders, a so-called sequence, which minimizes the makespan. We introduce a partial order on the set of sequences with the property that there exists at least one optimal sequence in the set of minimal elements of this partial order independent of the given processing times. The set of minimal elements (set of irreducible sequences) can be in detail described in the case of the two machine open-shop problem. The cardinality is calculated. We will show which sequences are generated by the well-known polynomial algorithms for the construction of optimal schedules. Furthermore, we investigate the problemO∥C _max on an operation set with spanning tree structure. Supported by Deutsche Forschungsgemeinschaft, Project ScheMA     

Quadratic programming with one negative eigenvalue is NP-hard

We show that the problem of minimizing a concave quadratic function with one concave direction is NP-hard. This result can be interpreted as an attempt to understand exactly what makes nonconvex quadratic programming problems hard. Sahni in 1974 [8] showed that quadratic programming with a negative definite quadratic term (n negative eigenvalues) is NP-hard, whereas Kozlov, Tarasov and Haijan [2] showed in 1979 that the ellipsoid algorithm solves the convex quadratic problem (no negative eigenvalues) in polynomial time. This report shows that even one negative eigenvalue makes the problem NP-hard.This author's work supported by the Applied Mathematical Sciences Program (KC-04-02) of the Office of Energy Research of the U.S. Department of Energy under grant DE-FG02-86ER25013. A000 and in part by the National Science Foundation, the Air Force Office of Scientific Research, and the Office of Naval Research, through NSF grant DMS 8920550.     

Asymptotic behavior of eigenvalues and random updating schemes

For a stochastic matrix (Q _ij ^T ) _i,j=1 ^M withQ _ij ^T exp(–U(ij)/T) at the off-diagonal positions, we develop an algorithm to evaluate the asymptotic convergence rate of all eigenvalues ofQ _ij ^T asT 0 using Ventcel's optimal graphs. As an application we can compare the convergence rates of some random updating schemes used in image processing.This research was partially supported by the National Science Council, Taiwan and Air Force Office of Scientific Research Contract No. F49620 S5C 0144, and was completed while Tzuu-Shuh Chiang was visiting the Center for Stochastic Processes, Department of Statistics, University of North Carolina, Chapel Hill, NC 27599-3260, USA.     

Approximating Scheduling Unrelated Parallel Machines in Parallel

We show how to approximate in NC the problem of scheduling unrelated parallel machines, for a fixed number of machines in which the makespan C _max is the objective function to minimize. We develop an approximate NC algorithm which finds a schedule whose length is at most (1+o(1))(C^* _max + 3 C^* _maxln(2n(n-1)/)), where C*_max denotes the optimal schedule, n the total number of jobs and a small positive constant. Our approach shows how to relate the linear program obtained by relaxing the integer programming formulation of the problem with a linear program formulation that is positive and in the packing/covering form. The established relationship enables us to transfer approximate fractional solutions from the later formulation that is known to be approximable in NC. Then, we show how to obtain an integer approximate solution, i.e. a schedule, from the fractional one, using the randomized rounding technique. We stress that our analysis assumes that the length of the schedule is (ln n) and that the min p _ij and max p _ij values are not too disparate (where p _ij is the time to run job j on machine i).Finally, we show that the same technique can be applied to the general assignment problem with a fixed number of machines and makespan T.     

On solutions of the Ricci curvature equation and the Einstein equation

We consider the pseudo-Euclidean space (R ⁿ , g), with n ≥ 3 and g _ij = δ _ij ε _i , ε _i = ±1, where at least one ε _i = 1 and nondiagonal tensors of the form T = Σ _ij f _ij dx _i dx _j such that, for i ≠ j, f _ij (x _i , x _j ) depends on x _i and x _j . We provide necessary and sufficient conditions for such a tensor to admit a metric ḡ, conformal to g, that solves the Ricci tensor equation or the Einstein equation. Similar problems are considered for locally conformally flat manifolds. Examples are provided of complete metrics on R ⁿ , on the n-dimensional torus T ⁿ and on cylinders T ^k ×R ^n-k , that solve the Ricci equation or the Einstein equation. Partially supported by CAPES/PROCAD. Partially Supported By Cnpq, Capes/Procad.     

On Some Optimal Constructions of Chess Tournament Combinations

An optimal solution for the following “chess tournament” problem is given. Let n, r be positive integers such that r<n. Put N=2n, R=2r+1. Let X_N,R be the set of all ordered pairs (T, A) of matrices of degree N such that T=(t_ij) is symmetric, A=(a_ij) is skew-symmetric, t_ij ∈,{0, 1, 2,…, R), a_ij ∈{0,1,–1}. Moreover, suppose t_ii=a_ii=0 (1?i?N). t_ij = t_ik>0 implies j=k, t_ij=0 is equivalent to a_ij=0, and |a_i1|+|a_i2|+…+|a_iN|=R (1?i?N). Let p(T, A) be the number of i such that 1?i?N and a_i1 + a_i2 + … + a_iN >0. The main result of this note is to show that max p(T, A) for (T, A)∈X_{N, R} is equal to [n(2r+1)/(r+1)], and a pair (T₀, A₀) satisfying p(T₀, A₀)=[n(2r+1)/(r+1)] is also given.     

How good are SPT schedules for fair optimality criteria

We consider the following scheduling setting: a set of n tasks have to be executed on a set of m identical machines. It is well known that shortest processing time (SPT) schedules are optimal for the problem of minimizing the total sum of completion times of the tasks. In this paper, we measure the quality of SPT schedules, from an approximation point of view, with respect to the following optimality criteria: sum of completion times per machine, global fairness, and individual fairness.     

Unitary dilations and theC* algebra0 2

LetH be an infinite-dimensional separable Hilbert space, and letS=(S _ij)∈teB(H)⊗M ₂ be a unitary 2 × 2 matrix with operator entries. We study theC*-algebra generated by the operatorsS _ij, and show that the study of unitary dilations of isometriesT inH reduces to the special case whereS ₁₁ =T, andS ₂₁ = 0. We useC*-algebraic techniques to obtain detailed results about the set of all unitary dilations ofT. Work supported in part by NSF.     

Exact controllability for the wave equation with variable coefficients

We consider in this paper the evolution systemy″−Ay=0, whereA =∂ _i(a_ij∂_j) anda _ij ∈C ¹ (ℝ⁺;W ^1,∞ (Ω)) ∩W ^1,∞ (Ω × ℝ⁺), with initial data given by (y ₀,y ₁) ∈L ²(Ω) ×H ⁻¹ (Ω) and the nonhomogeneous conditiony=v on Γ ×]0,T[. Exact controllability means that there exist a timeT>0 and a controlv such thaty(T, v)=y′(T, v)=0. The main result of this paper is to prove that the above system is exactly controllable whenT is “sufficiently large”. Moreover, we obtain sharper estimates onT.     

Sharpening the LYM inequality

The level sequence of a Sperner familyF is the sequencef(F)={f _i (F)}, wheref _i (F) is the number ofi element sets ofF . TheLYM inequality gives a necessary condition for an integer sequence to be the level sequence of a Sperner family on ann element set. Here we present an indexed family of inequalities that sharpen theLYM inequality.Research supported in part by Alexander v. Humboldt-StiftungResearch supported in part by NSF under grant DMS-86-06225 and AFOSR grant OSR-86-0078Research supported in part by NSF grant CCR-8911388Research supported in part by OTKA 327 0113     

Departures from queues with changeover times

We consider the M/M ^ij /1 queue as a model of queues with changeover times, i.e., the service is exponential with parameter _ij depending on the previous job type (i) and the current job type (j). It is shown that the departure process is renewal and Poisson iff _ij = (constant). In this case, types of departures are dependent renewal processes. Crosscovariance and crosscorrelations are given.     

Relative continuum mechanics in general relativity

Summary An axiomatic approach to the study of relative continuum mechanics in curved space-time is proposed. The explicit assumptions are: a) existence of the energy-momentum tensor T^ij, satisfying the equations of motion T^ij _‖j=0, and b) existence of the congruence of stream-lines of the given continuum. The argument relies on a relativistic extension of the Lagrangian viewpoint, and involves the analysis of the relative dynamical behaviour of an arbitrary infinitestimal globule Δ of continuum in a given frame of reference [Γ]. The plan is fulfilled in two steps:1) geometrical theory of the Lagrangian viewpoint, valid for any type of continua satisfying the stated requirements;2) physical applications, illustrating the general theory in the case of an energy-momentum tensor of the form T^ij=μ ₀ VⁱV^j—S^ij. Entrata in Redazione il 22 novembre 1977. Lavoro eseguito nell'ambito dell'attività del Gruppo Nazionale per la Fisica Matematica del C.N.R.     

Conservative loads on shells

Generalized load vectorsp and edge load vectorsF are denned in terms of the body force and surface on a shell. Necessary and sufficient conditions are derived forp andF, and therefore the body force and the surface force, to be conservative. It is shown for example thatp must satisfyp _i=P _ijk q _j,1 q _k,2+Q _ij ¹ q _j,2–Q _ij ² q _j,1+R _i whereq is the generalized position vector andP _ijk, Q_i,j ¹ and Q_ij ² are skew tensors.The case of hydrostatic pressure is examined in detail.This work was supported in part by NSF grant MSM 8618657.     

Disjoint homotopic paths and trees in a planar graph

In this paper we describe a polynomial-time algorithm for the following problem:given: a planar graphG embedded in ℝ², a subset {I ₁, …,I _p} of the faces ofG, and pathsC ₁, …,C _k inG, with endpoints on the boundary ofI ₁ ∪ … ∪I _p; find: pairwise disjoint simple pathsP ₁, …,P _k inG so that, for eachi=1, …,k, P _i is homotopic toC _i in the space ℝ²\(I ₁ ∪ … ∪I _p). Moreover, we prove a theorem characterizing the existence of a solution to this problem. Finally, we extend the algorithm to disjoint homotopic trees. As a corollary we derive that, for each fixedp, there exists a polynormial-time algorithm for the problem:given: a planar graphG embedded in ℝ² and pairwise disjoint setsW ₁, …,W _k of vertices, which can be covered by the boundaries of at mostp faces ofG;find: pairwise vertex-disjoint subtreesT ₁, …,T _k ofG whereT _i (i=1, …, k).