The asymptotic performance ratio of an on-line algorithm for uniform parallel machine scheduling with release dates

Jobs arriving over time must be non-preemptively processed on one of m parallel machines, each running at its own speed, so as to minimize a weighted sum of the job completion times. In this on-line environment, the processing requirement and weight of a job are not known before the job arrives. The Weighted Shortest Processing Requirement (WSPR) heuristic is a simple extension of the well known WSPT heuristic, which is optimal for the single machine problem without release dates. According to WSPR, whenever a machine completes a job, the next job assigned to it is the one with the least ratio of processing requirement to weight among all jobs available for processing at this point in time. We analyze the performance of this heuristic and prove that its asymptotic competitive ratio is one for all instances with bounded job processing requirements and weights. This implies that the WSPR algorithm generates a solution whose relative error approaches zero as the number of jobs increases. Our proof does not require any probabilistic assumption on the job parameters and relies extensively on properties of optimal solutions to a single machine relaxation of the problem. Research supported in part by ONR Contracts N00014-90-J-1649 and N00014-95-1-0232, NSF Contracts DDM-9322828, DMI-9732795, DMI-0085683 and DMI-0245352, NUS Academic Research Grant R314-000-046-112, and a research grant from the Natural Sciences and Research Council of Canada (NSERC).     

Portfolio theory for the recourse certainty equivalent maximizing investor

The portfolio selection problem with one safe andn risky assets is analyzed via a new decision theoretic criterion based on the Recourse Certainty Equivalent (RCE). Fundamental results in portfolio theory, previously studied under the Expected Utility criterion (EU), such as separation theorems, comparative static analysis, and threshold values for inclusion or exclusion of risky assets in the optimal portfolio, are obtained here. In contrast to the EU model, our results for the RCE maximizing investor do not impose restrictions on either the utility function or the underlying probability laws. We also derive a dual portfolio selection problem and provide it with a concrete economic interpretation.Research partly supported by ONR Contracts N0014-81-C-0236 and N00014-82-K-0295, and NSF Grant SES-8408134 with the Center for Cybernetic Studies, The University of Texas at Austin.Partly supported by NSF Grant DDM-8896112.Partly supported by AFOSR Grant 0218-88 and NSF Grant ECS-8802239 at the University of Maryland, Baltimore Campus.     

Solving singularly constrained generalized network problems

The singularly constrained generalized network problem represents a large class of capacitated linear programming (LP) problems. This class includes any LP problem whose coefficient matrix, ignoring single upper bound constraints, containsm + 1 rows which may be ordered such that each column has at most two non-zero entries in the firstm rows. The paper describes efficient procedures for solving such problems and presents computational results which indicate that, on large problems, these procedures are at least twenty-five times more efficient than the state of the art LP systemapex-iii.This research was partly supported by ONR Contract N00014-76-C-0383 with Decision Analysis and Research Institute and by Project NR047-021, ONR Contracts N00014-75-C-0616 and N00014-75-C-0569 with the Center for Cybernetic Studies, The University of Texas. Reproduction in whole or in part is permitted for any purpose of the United States Government.     

Further properties of nonzero-sum differential games

The general nonzero-sum differential game hasN players, each controlling a different set of inputs to a single nonlinear dynamic system and each trying to minimize a different performance criterion. These general games have several interesting features which are absent in the two bestknown special cases (the optimal control problem and the two-person, zero-sum differential game). This paper considers some of the difficulties which arise in attempting to generalize ideas which are well known in optimal control theory, such as theprinciple of optimality and the relation betweenopen-loop andclosed-loop controls. Two types of solutions are discussed: theNash equilibrium and thenoninferior set. Some simple multistage discrete games are used to illustrate phenomena which also arise in the continuous formulation.This research was supported by Joint Services Electronics Contracts Nos. N00014-67-A-0298-0006, 0005, 0008 and by NASA Grant No. NGR 22-007-068.     

Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality

The problem of integer programming in bounded variables, over constraints with no more than two variables in each constraint is NP-complete, even when all variables are binary. This paper deals with integer linear minimization problems inn variables subject tom linear constraints with at most two variables per inequality, and with all variables bounded between 0 andU. For such systems, a 2-approximation algorithm is presented that runs in time O(mnU ² log(Un ² m)), so it is polynomial in the input size if the upper boundU is polynomially bounded. The algorithm works by finding first a super-optimal feasible solution that consists of integer multiples of 1/2. That solution gives a tight bound on the value of the minimum. It furthermore has an identifiable subset of integer components that retain their value in an integer optimal solution of the problem. These properties are a generalization of the properties of the vertex cover problem. The algorithm described is, in particular, a 2-approximation algorithm for the problem of minimizing the total weight of true variables, among all truth assignments to the 2-satisfiability problem.This paper is dedicated to Phil Wolfe on the occasion of his 65th birthday.Research supported in part by ONR contracts N00014-88-K-0377 and N00014-91-J-1241.Research supported in part by ONR contract N00014-91-C-0026.Part of this work was done while the author was visiting the International Computer Science Institute in Berkeley, CA and DIMACS, Rutgers University, New Brunswick, NJ.     

Local Minima and Convergence in Low-Rank Semidefinite Programming

The low-rank semidefinite programming problem LRSDP_r is a restriction of the semidefinite programming problem SDP in which a bound r is imposed on the rank of X, and it is well known that LRSDP_r is equivalent to SDP if r is not too small. In this paper, we classify the local minima of LRSDP_r and prove the optimal convergence of a slight variant of the successful, yet experimental, algorithm of Burer and Monteiro [5], which handles LRSDP_r via the nonconvex change of variables X=RR^T. In addition, for particular problem classes, we describe a practical technique for obtaining lower bounds on the optimal solution value during the execution of the algorithm. Computational results are presented on a set of combinatorial optimization relaxations, including some of the largest quadratic assignment SDPs solved to date.This author was supported in part by NSF Grant CCR-0203426.This author was supported in part by NSF Grants CCR-0203113 and INT-9910084 and ONR grant N00014-03-1-0401.     

A primal-dual approximation algorithm for generalized steiner network problems

We present the first polynomial-time approximation algorithm for finding a minimum-cost subgraph having at least a specified number of edges in each cut. This class of problems includes, among others, the generalized Steiner network problem, also called the survivable network design problem. Ifk is the maximum cut requirement of the problem, our solution comes within a factor of 2k of optimal. Our algorithm is primal-dual and shows the importance of this technique in designing approximation algorithms.Research supported by an NSF Graduate Fellowship, DARPA contracts N00014-91-J-1698 and N00014-92-J-1799, and AT&T Bell Laboratories.Research supported in part by Air Force contract F49620-92-J-0125 and DARPA contract N00014-92-J-1799.Part of this work was done while the author was visiting AT&T Bell Laboratories and Bellcore.     

Optimal design of pitched laminated wood beams

The optimal design of a pitched laminated wood beam is considered. An engineering formulation is given in which the volume of the beam is minimized. The problem is then reformulated and solved as a generalized geometric (signomial) program. Sample designs are presented.This research was partially supported by the Office of Naval Research under Contracts Nos. N00014-75-C-0267 and N00014-75-C-0865; by the US Energy Research and Development Administration Contract No. E(04-3)-326 PA-18; and by the National Science Foundation, Grant No. DCR75-04544 at Stanford University. This work was carried out during the first author's stay at the Management Science Division of the University of British Columbia and the Systems Optimization Laboratory of Stanford University. The authors are indebted to Mr. S. Liu and Mrs. M. Ratner for their assistance in performing the computations.     

First-order conditions for isolated locally optimal solutions

There are well-known first-order sufficient conditions for a pointx ₀ to be a strict locally optimal solution of a nonlinear programming problem. In this paper, we show that these conditions also guarantee thatx ₀ is an isolated stationary point of the considered program provided a constraint qualification holds. This result has an interesting application to finite convergence of algorithms along the lines suggested by Al-Khayyal and Kyparisis.This research was supported in part by National Science Foundation Grant DDM-91-14489.     

Optimal design of efficient acoustic antenna arrays

Minimax optimal design of sonar transducer arrays can be formulated as a nonlinear program with many convex quadratic constraints and a nonconvex quadratic efficiency constraint. The variables of this problem are a scaling and phase shift applied to the output of each sensor. This problem is solved by applying Lagrangian relaxation to the convex quadratic constraints. Extensive computational experience shows that this approach can efficiently find near-optimal solutions of problems with up to 391 variables and 579 constraints. This work was supported by ONR Contracts N00014-83-C-0437 and N00014-82-C-824.     

Polyhedral sets having a least element

For a fixedm × n matrixA, we consider the family of polyhedral setsX _b ={x|Ax b}, b R ^m , and prove a theorem characterizing, in terms ofA, the circumstances under which every nonemptyX _b has a least element. In the special case whereA contains all the rows of ann × n identity matrix, the conditions are equivalent toA ^T being Leontief. Among the corollaries of our theorem, we show the linear complementarity problem always has a unique solution which is at the same time a least element of the corresponding polyhedron if and only if its matrix is square, Leontief, and has positive diagonals.This research was supported by the National Science Foundation under Grants GK-18339 and GP-25738, by the Office of Naval Research under Contracts N00014-67-A-0112-0050 (NR-042-264) and N00014-67-A-0112-0011, and by the IBM Corporation. Part of the second author's contribution to this paper was made while he was on sabbatical leave in 1968–9 as a consultant to the IBM Research Center. Reproduction in whole or in part is permitted for any purpose of the United States Government.     

Intersections ofk-element sets

LetF be a collection ofk-element sets with the property that the intersection of no two should be included in a third. We show that such a collection of maximum size satisfies .2715k+o(k)≦≦log₂ |F|≦.7549k+o(k) settling a question raised by Erdős. The lower bound is probabilistic, the upper bound is deduced via an entropy argument. Some open questions are posed. This research has been supported in part by the Office of Naval Research under Contract N00014-76-C-0366. Supported in part by a NSF postdoctoral Fellowship.     

A branch and bound algorithm for the generalized assignment problem

This paper describes what is termed the generalized assignment problem. It is a generalization of the ordinary assignment problem of linear programming in which multiple assignments of tasks to agents are limited by some resource available to the agents. A branch and bound algorithm is developed that solves the generalized assignment problem by solving a series of binary knapsack problems to determine the bounds. Computational results are cited for problems with up to 4 000 0–1 variables, and comparisons are made with other algorithms.This research was partly supported by ONR Contracts N00014-67-A-0126-0008 and N00014-67-A-0126-0009 with the Center for Cybernetic Studies, The University of Texas.     

Energetic reasoning and bin-packing problem, for bounding a parallel machine scheduling problem

This paper deals with an extension of energetic reasoning, using some efficient lower bounds of the bin-packing problem, to get tight lower bounds for the P|r _i , q _i |C _max. The link between P||C _max and bin-packing problem is well-known. Our purpose is to extend the use of efficient lower bounds of the bin-packing problem to P|r _i , q _i |C _max. We focus on some time-intervals, to compute the mandatory parts of activities within this time-interval and then to deduce an associated bin-packing instance. Thus, lower bounds of the bin-packing problem are used to get new satisfiability tests for the parallel machine problem. We also propose to extend the classical time-bound adjustments of release dates and deadlines to efficiently use bin-packing lower bounds. Experimental results that prove the efficiency of our approach on several kind of instances are reported.     

A note on the prize collecting traveling salesman problem

We study the version of the prize collecting traveling salesman problem, where the objective is to find a tour that visits a subset of vertices such that the length of the tour plus the sum of penalties associated with vertices not in the tour is as small as possible. We present an approximation algorithm with constant bound. The algorithm is based on Christofides' algorithm for the traveling salesman problem as well as a method to round fractional solutions of a linear programming relaxation to integers, feasible for the original problem.Research supported in part by ONR contract N00014-90-J-1649 and NSF contract DDM-8922712.     

Discrimination with respect to a Gaussian process

Summary Let (N _t) and (Y _t), t in [0,1], be stochastic processes on (, , P). Suppose that (N _t) is Gaussian, m.s. continuous, zero mean, and vanishes a.s. at t=0. Let v _Y and v _N be the induced measures on ^[0,1]. Conditions are obtained for v _Y to be absolutely continuous w.r.t. v _N. Expressions for the Radon-Nikodym derivative are derived. Further results on these problems are obtained for measures induced on L ₂[0, 1] and on C[0, 1].Research supported by ONR Contracts N 00014-75-C-0491 and N 00014-81-K-0373     

Generalized convexity and concavity of the optimal value function in nonlinear programming

In this paper we consider generalized convexity and concavity properties of the optimal value functionf ^* for the general parametric optimization problemP(_ε) of the form min _x f(x, ε) s.t.x∈R(ε). Many results on convexity and concavity characterizations off ^* were presented by the authors in a previous paper. Such properties off ^* and the solution set mapS ^* form an important part of the theoretical basis for sensitivity, stability and parametric analysis in mathematical optimization. We give sufficient conditions for several types of generalized convexity and concavity off ^*, in terms of respective generalized convexity and concavity assumptions onf and convexity and concavity assumptions on the feasible region point-to-set mapR. Specializations of these results to the parametric inequality-equality constrained nonlinear programming problem are provided. Research supported by Grant ECS-8619859, National Science Foundation and Contract N00014-86-K-0052, Office of Naval Research.     

The average-case analysis of some on-line algorithms for bin packing

In this paper we give tighter bounds than were previously known for the performance of the bin packing algorithms Best Fit and First Fit when the inputs are uniformly distributed on [0, 1]. We also give a general lower bound for the performance of any on-line bin packing algorithm on this distribution. We prove these results by analyzing optimal matchings on points randomly distributed in a unit square. We give a new lower bound for the up-right matching problem. A preliminary version of this paper appeared inProc. 25th IEEE Symposium on Foundations of Computer Science, 193–200. This research was done while the author was at the Massachusetts Institute of Technology Dept. of Mathematics and was supported by a NSF Graduate Fellowship and by Air Force grant OSR-82-0326.     

Simplified Voronoi diagrams

We are interested in Voronoi diagrams as a tool in robot path planning, where the search for a path in anr-dimensional space may be simplified to a search on an (r–1)-dimensional Voronoi diagram. We define a Voronoi diagramV based on a measure of distance which is not a true metric. This formulation has lower algebraic complexity than the usual definition, which is a considerable advantage in motion-planning problems with many degrees of freedom. In its simplest form, the measure of distance between a point and a polytope is the maximum of the distances of the point from the half-spaces which pass through faces of the polytope. More generally, the measure is defined in configuration spaces which represent rotation. The Voronoi diagram defined using this distance measure is no longer a strong deformation retract of free space, but it has the following useful property: any path through free space which starts and ends on the diagram can be continuously deformed so that it lies entirely on the diagram. Thus it is still complete for motion planning, but it has lower algebraic complexity than a diagram based on the Euclidean metric.This report describes research done at the Artificial Intelligence Laboratory of the Massachusetts Institute of Technology. Support for the Laboratory's Artificial Intelligence research is provided in part by the Office of Naval Research under Office of Naval Research Contract N00014-81-K-0494 and in part by the Advanced Research Projects Agency under Office of Naval Research Contracts N00014-85-K-0124 and N00014-82-K-0334. John Canny was supported by an IBM fellowship. Bruce Donald was funded in part by a NASA fellowship administered by the Jet Propulsion Laboratory.     

Fitting ideals and the Gorenstein property

Let p be a prime number and G be a finite commutative group such that p ² does not divide the order of G. In this note we prove that for every finite module M over the group ring Z _p [G], the inequality #M  ￡  #Z_p[G]/Fit_Zp[G](M){\#M\,\leq\,\#{\bf Z}_{p}[G]/{{\rm Fit}}_{{\bf Z}_{p}[G]}(M)} holds. Here, Fit_Zp[G](M){\rm Fit}_{{\bf Z}_{p}[G]}(M) is the Z _p [G]-Fitting ideal of M.