bluuebunny/crossref_metadata_2025 huggingface dataset:
On Some Classes of Linear Complementarity Problems with Matrices of Order n and Rank (n − 1)
Authors: Eagambaram N. , Mohan S. R.
Published: October 2008

In this paper we generalize a fundamental result observed by B. C. Eaves on the nature of solutions constructed by Lemke's algorithm applied to solve the linear complementarity problem (q, M) initiating it with the positive vector d ∈ Rn. We use this generalization and identify two subclasses of the class of n × n matrices M of rank (n − 1) for which the set of q ∈ Rn such that the LCP (q, M) has a solution is convex. We also present algorithms to compute a solution to (q, M) if one exists, for these classes of matrices.
Packing, Covering and Partitioning Problems with Strongly Unimodular Constraint Matrices
Authors: Crama Yves , Hammer Peter L. , Ibaraki Toshihide
Published: October 2008

A 0-1 matrix A is called strongly unimodular if all its nonsingular square submatrices are triangular. We present an efficient algorithm for linear programming problems in binary variables, when all constraints are of the packing, covering or partitioning type, and the constraint matrix is strongly unimodular. The algorithm uses a certain decomposition of strongly unimodular matrices into their so-called “restricted unimodular” components, and an efficient optimization algorithm for linear programs with restricted unimodular constraints.
A Class of Euclidean Routing Problems with General Route Cost Functions
Authors: Anily S. , Federgruen A.
Published: October 2008

In most vehicle routing problems, a given set of customers is to be partitioned into a collection of regions each of which is assigned to a single vehicle starting at a depot and returning there after visiting all of the region's customers exactly once in a route. In this paper we consider problem settings where the cost of a route may depend on its length ϑ as well as m, the number of points on the route, according to some general function f(ϑ, m), assumed to be nondecreasing and concave in ϑ.

We describe a class of O(N logN) or O(N2) heuristics and show under mild probabilistic assumptions that the solutions generated are asymptotically optimal. We also show that lower and upper bounds on the system-wide costs may be computed (with even simpler procedures) and that these bounds are asymptotically tight under the same assumptions.
Sensitivity Analysis for Nonlinear Programs and Variational Inequalities with Nonunique Multipliers
Authors: Kyparisis Jerzy
Published: October 2008

We extend the principal sensitivity analysis results for parametric nonlinear programs and variational inequalities by considering problems with nonunique optimal Lagrange multipliers. Specifically, we derive sufficient conditions for the existence, continuity and directional differentiability of a locally unique perturbed solution of a nonlinear program or a variational inequality.
Higher-Order and Average Reward Myopic-Affine Dynamic Models
Authors: Sobel Matthew J.
Published: October 2008

The dynamics and rewards in a higher-order model depend directly on states and actions in earlier periods. Here, the expected values of the single-period reward and of the state in the next period are affine functions of the states in the current and earlier periods. It is shown that computations in higher-order infinite-horizon models with myopic solutions are not essentially harder than in the corresponding first-order models. These results are obtained for discounted and average-reward criteria, and similar conclusions are indicated for sequential games. The results are applied to an aquaculture harvesting model and an advertising model with delayed responses.
Newton's Method for B-Differentiable Equations
Authors: Pang Jong-Shi
Published: October 2008

In this paper, we extend the classical Newton method for solving continuously differentiable systems of nonlinear equations to B-differentiable systems. Such B-differentiable systems of equations provide a unified framework for the nonlinear complementarity, variational inequality and nonlinear programming problems. We establish the local and quadratic convergence of the method and propose a modification for global convergence. Applications of the theory to complementarity, variational inequality and optimization will be explained. In each of these contexts, the resulting method resembles the known Newton methods derived from Robinson's generalized equation formulation, but with a computational advantage. Namely, the new method incorporates a kind of active-set strategy in defining the subproblems. Unlike the previous methods which are only locally convergent, the modified version of the new method provides a descent algorithm which is globally convergent under some mild assumptions.
The Shapes of Polyhedra
Authors: Kannan Ravi , Lovász Lászlo , Scarf Herbert E.
Published: October 2008

Let A be a real matrix of size (n + d + 1) × n. We assume that all n × n submatrices of A are nonsingular and define the condition number C = C(A) to be the ratio of the largest n × n subdeterminant of A to the smallest in absolute value. In addition we assume that there is a positive vector π such that πA = 0. This implies that for any b, the body Kb = {x∣Ax ≤ b} is bounded. Let f(A) be the number of subsets of the rows of A, of cardinality n + 1, for which a positive linear combination equals zero.

The Banach-Mazur distance Ρ(Kb, Kc) for a pair of nonempty full dimensional bodies Kb and Kc is defined as follows: let λ1 be the smallest λ for which Kc ⊆ λ Kb + ξ1 for some ξ1 and λ2 the smallest λ for which Kb ⊆ λ Kc + ξ2 for some ξ2. Then Ρ(Kb, Kc) = log(λ1 ⋅ λ2).

We show that for any ε > 0, there exists a subset of the bodies Kb, of cardinality not larger than f(A)⌈2 log2 (nC)/ε⌉d, such that every body is within distance ε from some member of the subset.
On-Line Optimization of Simulated Markovian Processes
Authors: Pflug G. Ch.
Published: October 2008

Let {Zn} be a Markovian process, the transition of which depends on a control parameter x. Let μx be its invariant law. It is shown that the solution of the optimization problem

F(x) := ∫ H(z, x) dμx(z) = min!, x ∈ S

can be found with a recursive estimation procedure of the stochastic approximation-type. The method consists in finding a stochastic quasigradient of F(x) and in adapting the parameter x in the direction of descent. An a.s. convergence is proved and a practical example is given.
On the Maximum Degree of an LCP Map
Authors: Morris Walter D.
Published: October 2008

The Linear Complementarity Problem can be shown to be equivalent to inverting a certain piecewise linear mapping. We give bounds on the degree of this mapping and present a class of matrices that generates maps of high degree.
Second-Order Necessary Conditions for Nonlinear Optimization Problems in Banach Spaces and Their Application to an Optimal Control Problem
Authors: Maruyama Yukihiro
Published: October 2008

We study second-order necessary conditions for nonlinear optimization problems with equality and set constraints in Banach spaces. The necessary conditions are given in the primal form and the dual form by the use of second-order Neustadt derivative. Moreover we apply the necessary conditions to an optimal control problem without state constraints.
A Centered Projective Algorithm for Linear Programming
Authors: Todd Michael J. , Ye Yinyu
Published: October 2008

We describe a projective algorithm for linear programming that shares features with Karmarkar's projective algorithm and its variants and with the path-following methods of Gonzaga, Kojima-Mizuno-Yoshise, Monteiro-Adler, Renegar, Vaidya and Ye. It operates in a primal-dual setting, stays close to the central trajectories, and converges in O(√n L) iterations like the latter methods. (Here n is the number of variables and L the input size of the problem.) However, it is motivated by seeking reductions in a suitable potential function as in projective algorithms, and the approximate centering is an automatic byproduct of our choice of potential function.
On the Cookie-Cutter Game: Search and Evasion on a Disc
Authors: Danskin John M.
Published: October 2008

In the cookie-cutter game, there is a trapping circle, of radius 1, in which an evader hides. A searcher has a “cookie-cutter”, a disk of radius r < 1. If, when he places the cookie-cutter on the trapping circle, the evader is within it, the evader is caught and the searcher wins. Otherwise the evader wins.

If r = √2/2, the problem is trivial. The evader should choose a point from the uniform distribution on the outer circumference of the trapping circle, and the searcher a point from the uniform distribution on the circle of radius r* = (1 − r2)1/2 concentric to that circle; this choice gives him maximum coverage of the outer circumference.

For the case r ≧ 1/2, an easy and elegant solution was given by Gale and Glassey in 1974. Both players should go to the center with probability 1/7. The minimizer should go to the outer circumference, and the maximizer to r* = √3/2, both with probability 6/7.

For other r the problem is difficult. This paper proves that there are no solutions based on finitely many radii if r < r0 ≐ 0.476, where r0 solves a cubic equation, finds two-point solutions on [r0, r1], where r1 ≐ 0.515 solves a trigonometric equation, and proves qualitative facts for r ∈ (r1, √2/2).
On Generalized Gradients in Optimization Problems with Set-Valued Constraints
Authors: Outrata J. V.
Published: October 2008

We investigate the value function f(x) = inf φ (x, y) where the infimum is over all y ∈ a(x) for some given set-valued map a. Under specified conditions we provide an inner approximation for its generalized gradient. In some cases a full description of this generalized gradient is given. The results are of use in numerical solution of various optimization problems. Illustrative examples are given.
Solving Bargaining Games by Differential Equations
Authors: Furth Dave
Published: October 2008

“Solving Games by Differential Equations”: was the title of a paper by Brown and von Neumann (1950). The idea of solving bargaining games by differential equations goes back to Raiffa (1953). The present paper starts with a solution ϕ of a bargaining game and constructs, by means of solving a set of differential equations, a new solution Cϕ, the continuation of ϕ. A property is called hereditary when it holds for Cϕ whenever it holds for ϕ. Hereditary properties and properties of Cϕ in relation to properties of ϕ are studied. The paper includes a number of open problems.
Convex Resource Allocation Problems on Directed Acyclic Graphs: Duality, Complexity, Special Cases, and Extensions
Authors: Monma Clyde L. , Schrijver Alexander , Todd Michael J. , Wei Victor K.
Published: October 2008

Consider the following resource allocation problem on a directed acyclic graph (the precedence graph). Each vertex has a known work load, and a fixed amount of total resource is available. The time required to process a vertex is inversely proportional to the amount of the resource allocated to it. The time to complete all of the work is the length of (time to complete) a longest chain in the graph. The problem of finding an allocation which minimizes the time required to complete all of the work subject to the limited resource availability can be formulated as a separable convex programming problem.

We use results from Lagrangian duality for convex programs, the length-width inequality, and Dilworth's Theorem for directed acyclic graphs, to obtain a strong relationship between optimal solutions of this problem and its dual. This allows us to obtain closed-form solutions for certain special classes of graphs, and leads to a generalization of the LYM Property for partially ordered sets. The computational complexity of the general problem is an open question. However, the ellipsoid method yields a fully-polynomial approximation scheme, and some light can be shed on the associated decision problem. The results of this paper are shown to extend to resource allocation problems on perfect graphs.
Single-Machine Scheduling Polyhedra with Precedence Constraints
Authors: Queyranne Maurice , Wang Yaoguang
Published: October 2008

We consider nonpreemptive single-machine scheduling subject to precedence constraints. We define feasible schedules by the vector of the job completion times and study the structure of the convex hull of all feasible schedules, called the scheduling polyhedron P. We derive classes of valid inequalities for P, and necessary and sufficient conditions under which they are facet-inducing. Our main result is a complete description of the minimal linear system defining P when the precedence constraints are series-parallel. Moreover, this system consists of two classes of facet-inducing inequalities, associated with series and parallel compositions, respectively. If the precedence constraints are not series-parallel, we present another class of facet-inducing inequalities for P, associated with induced Z-subgraphs. We also show that the convex hull of all preemptive feasible schedules is identical to P if and only if the precedence constraints form an out-forest.
Scenarios and Policy Aggregation in Optimization Under Uncertainty
Authors: Rockafellar R. T. , Wets Roger J.-B.
Published: October 2008

A common approach in coping with multiperiod optimization problems under uncertainty where statistical information is not really enough to support a stochastic programming model, has been to set up and analyze a number of scenarios. The aim then is to identify trends and essential features on which a robust decision policy can be based. This paper develops for the first time a rigorous algorithmic procedure for determining such a policy in response to any weighting of the scenarios. The scenarios are bundled at various levels to reflect the availability of information, and iterative adjustments are made to the decision policy to adapt to this structure and remove the dependence on hindsight.
The D1-Triangulation of Rn for Simplicial Algorithms for Computing Solutions of Nonlinear Equations
Authors: Dang Chuangyin
Published: October 2008

We present a new triangulation of ℝn, which is called the D1-triangulation, for computing zero points or fixed points of nonlinear mappings. The D1-triangulation subdivides the unit cube and is based on very elementary pivot rules. We compare the D1-triangulation to several well-known triangulations of ℝn which triangulate the unit cube. According to several measures of efficiency the new triangulation is superior, such as the number of simplices in the unit cube, the diameter of a triangulation, the average directional density, and the surface density.
The Adequacy of Universal Strategies in Analytic Gambling Problems
Authors: Monticino Michael G.
Published: October 2008

Suppose measurability structures are imposed upon a Dubins and Savage gambling problem. A long-standing question asks whether strategies which are measurable with respect to these structures enable the gambler to maximize his return. Measurable strategies have the advantage over arbitrary strategies in that they induce countably additive probability measures. In this work, we show that measurable strategies are adequate in order to maximize return if and only if the optimal return function is measurable. Using this result, several examples of gambling problems for which measurable strategies are adequate are given.
Light Traffic Approximations in Queues
Authors: Daley D. J. , Rolski T.
Published: October 2008

For a stationary waiting time random variable W ≡ W(S, T) in a GI/G/1 queueing system with generic service and inter-arrival time random variables S and T respectively, with ES < ET, performance characteristics including Pr{W > 0} and EW are studied in light traffic conditions. One way of attaining these conditions, as considered in a previous paper, is to replace T by γT for large γ; another way is to thin the arrival process with small but positive retention probability π. These two approaches are compared, the thinning approach being applied to queues with either a renewal or a periodic Poisson arrival process. Results are also given for GI/M/k and GI/D/k queues. The variety of queueing systems studied is reflected in the different behaviour both of the quantities calculated directly and of the derived quantity E(W | W > 0). The dominant feature of light traffic characteristics is their dependence on the clustering tendency and related properties of the arrival process.
Stochastic Analysis of the Quadratic Assignment Problem
Authors: Rhee Wansoo T.
Published: October 2008

Let A and B be m × m matrices. The aim is to maximize Q(σ) = ∑i, jaijbσ(i)σ(j) over all permutations σ of 1, 2, …, m. We define a simple “greedy” algorithm that constructs a permutation σ* that gives a large Q(σ*). Assuming that the entries of A are i.i.d. with a symmetric distribution, and that the entries of B are independent of A, we show under some weak moment conditions EQ(σ*) ≥ K−1m3/2(log m)1/2, where the constant k does not depend on m. This contrasts with the fact that maxσ ≤ Km3/2(log m)1/2 with overwhelming probability.
A Comparative Study of Multifunction Differentiability with Applications in Mathematical Programming
Authors: Auslender A. , Cominetti R.
Published: October 2008

A unified treatment of various notions of tangency for sets and differentiability for multifunctions is presented. These results are then applied to study first and second order differentiability properties of metric projections and to some applications in mathematical programming.
Domain Contraction in Nonlinear Programming: Minimizing a Quadratic Concave Objective Over a Polyhedron
Authors: Thakur Lakshman S.
Published: October 2008

Using linear underestimating approximations and their dual solutions, we develop new results for the nonconvex problem of minimizing a quadratic concave function under linear constraints. For solving this problem, which has such important management applications as economies of scale, fixed charge, and quadratic assignment problems, some results provide and tighten bounds on the global minimum value, while others identify the domains of the variables which may be excluded from further consideration. This leads to successive reduction of domains containing a global solution, called domain contraction, and ideally, to a solution with the objective value within some acceptable error level. For most results, specific problem instances are provided to establish their use in theory.

In practice, experience with solving the problems presented here indicates that a combination of the proposed domain contraction via linear underestimation and its dual information with the branch and bound approach offers a computational strategy competitive with the currently dominant methods: combinations of branch and bound with (1) cutting planes, (2) relaxation, or (3) domain partitioning. Problems with up to 100 variables and up to 50 linear constraints (50 × 100), comparable in difficulty and size with the largest published in the literature, are solved and included in the initial implementation of the approach.
Discrete Flow Networks: Bottleneck Analysis and Fluid Approximations
Authors: Chen Hong , Mandelbaum Avi
Published: October 2008

We conduct bottleneck analysis of a deterministic dynamic discrete-flow network. The analysis presupposes only the existence of long-run averages, and is based on a continuous fluid approximation to the network in terms of these averages. The results provide functional strong laws-of-large-numbers for stochastic Jackson queueing networks since they apply to their sample paths with probability one.
Relaxation Methods for Problems with Strictly Convex Costs and Linear Constraints
Authors: Tseng Paul , Bertsekas Dimitri P.
Published: October 2008

Consider the problem of minimizing a strictly convex (possibly nondifferentiable and nonseparable) cost subject to linear constraints. We propose a dual coordinate ascent method for this problem that uses inexact line search and either essentially cyclic or Gauss-Southwell order of coordinate relaxation. We show, under very weak conditions, that this method generates a sequence of primal vectors converging to the optimal primal solution. Under an additional regularity assumption, and assuming that the effective domain of the cost function is polyhedral, we show that a related sequence of dual vectors converges in cost to the optimal cost. If the constraint set has an interior point in the effective domain of the cost function, then this sequence of dual vectors is bounded and each of its limit point(s) is an optimal dual solution. When the cost function is strongly convex, we show that the order of coordinate relaxation can become progressively more chaotic. These results significantly improve upon those obtained previously.
On the Fluctuations of the Stochastic Traveling Salesperson Problem
Authors: Rhee Wansoo T.
Published: October 2008

Consider n points X1, …, Xn independently and uniformly distributed on the unit square [0, 1]2. Denote by Tn the length of the shortest tour through X1, …, Xn. We prove that for some universal constant K, we have P(|Tn − E(Tn)| ≥ t) ≥ K−1 exp(−t2 K) whenever t ≤ K−1n1/2.
Multidimensional Optimal Bin Packing with Items of Random Size
Authors: Rhee Wansoo T. , Talagrand Michel
Published: October 2008

Consider a probability measure μ on [0, 1]d, and independent random variables X⃗1, …, X⃗n distributed according to μ. Let Vn = Vn(X⃗1, …, X⃗n) (resp. Rn = Rn(X⃗1, …, X⃗n)) be the minimal number of unit size d-dimensional bins needed to pack items of size X⃗1, …, X⃗n in the vector packing (resp. rectangular packing) problem. For a large class of distributions μ, we characterize v(μ) = limn→∞ Vn/n and r(μ) = limn→∞ Rn/n.
Minimizing Separable Convex Objectives on Arbitrarily Directed Trees of Variable Upper Bound Constraints
Authors: Jackson Peter L. , Roundy Robin O.
Published: October 2008

An extension of the Economic Order Quantity (EOQ) model to multi-stage production-distribution systems and the isotonic regression problem are known to be equivalent and to be solvable in O(N4) time. The following specializations of the model are solvable in O(N log N) time: joint replenishment systems, pure assembly systems, nested policies in pure distribution systems, nonnested policies in one-warehouse multi-retailer systems, nested policies in multi-item, one-warehouse, multi-retailer systems, and systems in which the underlying network is a series-parallel digraph. We show here that a generalization of this problem is solvable in O(N log N) time whenever the undirected version of the underlying network is a tree. The algorithm we propose is used as a subroutine in an algorithm solving the EOQ problem on general circuitless directed graphs, the subject of a companion paper.
Exact Computation of Optimal Inventory Policies Over an Unbounded Horizon
Authors: Hassin Refael , Megiddo Nimrod
Published: October 2008

An inventory scheduling model with forbidden time intervals is analyzed. The objective is to minimize the long-term average cost per time unit. Unlike most of the literature on inventory theory, no restrictive assumptions are made a priori about the nature of optimal solutions. Rather it is proved that optimal policies exist, and that some of them are cyclic with cycles of a particular structure. It is then shown that such optimal policies can be computed and an algorithm is given.
Efficient Algorithms for Solving Systems of Nonlinear Equations with a Block Diagonal Structure
Authors: Kamiya Kazuya
Published: October 2008

The purpose of this paper is to present efficient algorithms for computing solutions to systems of nonlinear equations with a block diagonal structure. The special structure of the systems, which arises in economic models, allows us to use the decomposition of the problems.
Simplicial Algorithm to Find Zero Points of a Function with Special Structure on a Simplotope
Authors: Kamiya K. , Talman A. J. J.
Published: October 2008

In this paper we introduce a variable dimension simplicial algorithm on a cartesian product of unit simplices to find a zero point of a continuous function with special structure. The special structure of the function allows us to perform the linear programming pivot steps of the algorithm in a small system of equations. Moreover, a specific simplicial subdivision of the simplotope underlies the algorithm. The path of points generated by the algorithm approximately follows a piecewise smooth path in the simplotope. The latter path can be interpreted as being generated by an adjustment process. We discuss two applications, an international trade economy and an economy with increasing returns to scale. In both applications the zero points of the function induce equilibria in the economies.
Homotopy Continuation Methods for Nonlinear Complementarity Problems
Authors: Kojima Masakazu , Megiddo Nimrod , Noma Toshihito
Published: October 2008

A complementarity problem with a continuous mapping f from Rn into itself can be written as the system of equations F(x, y) = 0 and (x, y) ≥ 0. Here F is the mapping from R2n into itself defined by F(x, y) = (x1y1, x2y2, …, xnyn, y − f(x)). Under the assumption that the mapping f is a P0-function, we study various aspects of homotopy continuation methods that trace a trajectory consisting of solutions of the family of systems of equations F(x, y) = t(a, b) and (x, y) ≥ 0 until the parameter t ≥ 0 attains 0. Here (a, b) denotes a 2n-dimensional constant positive vector. We establish the existence of a trajectory which leads to a solution of the problem, and then present a numerical method for tracing the trajectory. We also discuss the global and local convergence of the method.
A Method for the Parametric Center Problem, with a Strictly Monotone Polynomial-Time Algorithm for Linear Programming
Authors: Freund Robert M. , Tan Kok-Choon
Published: October 2008

Given a system of linear inequalities Ax ≤ b + dt and equalities Mx = g + ht, where the right-hand sides are parametrically deformed over the scalar t, the parametric center problem is to trace the parametric family of approximate solutions x̄(t) to the center problems P(t), where P(t) is the problem: maximize ∑i=1m ln(bi + dit − Aix) subject to Ax < b + dt and Mx = g + ht. We present an algorithm for tracing the parametric family of solutions x̄(t) over some given range. At the kth iterate of the algorithm, the point x̄(tk) is an approximate solution to the center problem P(tk) (in an appropriate measure of approximation). The value of tk is increased to tk+1, and a Newton step is used to generate x̄(tk+1) which is an approximate solution to the center problem P(tk+1). The sequence of values of t exhibit at least one of the following geometric rates of change:

(TMAX − tk + 1) ≤ (TMAX − tk)(1 − 1/(128m))

(tk + 1 − TMIN) ≥ (tk − TMIN)(1 + 1/(128m))

where TMIN (TMAX) is the maximum (minimum) number t such that Ax ≤ b + dt, Mx = g + ht has a solution. Thus the iterates exhibit either linear growth away from TMIN or linear convergence toward TMAX, with a rate of change of 1/(128m), where m is the number of inequality constraints.

When applied to the linear programming problem, the algorithm is an O(mL) iteration algorithm for linear programming, that strictly improves the primal objective value at each iteration, and requires no dual feasible solution (or even dual feasibility) to start. After O(mL) iterations, the algorithm either detects primal unboundedness or produces an interior solution that can be rounded to an optimal solution to the linear program.
Relaxation Method for Large Scale Linear Programming Using Decomposition
Authors: Tseng Paul
Published: October 2008

We propose a new decomposition method for large-scale linear programming. This method dualizes an (arbitrary) subset of the constraints and then maximizes the resulting dual functional by dual ascent. The ascent directions are chosen from a finite set and are generated by a truncated version of the painted index algorithm of Rockafellar. Central to this method is the novel notion of (ε, δ)-complementary slackness (ε ≥ 0, δ ∈ [0, 1]) which allows each Lagrangian subproblem to be solved only approximately with O(εδ) accuracy and provides a lower bound of Ω(ε(1 − δ)) on the amount of improvement per dual ascent. By dynamically adjusting ε, the subproblems can be solved with increasing accuracy. We show that (i) the method terminates finitely, provided that ε and δ are bounded away from 0 and 1, respectively, (ii) the final solution produced by the method is feasible and is within O(ε) in cost of the optimal cost, and (iii) the final solution produced by the method is optimal for all ε sufficiently small.
Complete Convergence of the Directed TSP
Authors: Talagrand Michel
Published: October 2008

Consider the random directed graph Gn whose vertices X1, …, Xn are independent uniformly distributed over [0, 1]2. For 1 ≤ i < j ≤ n, the orientation of the edge XiXj is selected at random, independently for each edge and independently of the Xi's. Denote by Un the length of the shortest path through Gn. Then for some constant β > 0 and all ε > 0 we have ∑n≥1P(|n−1/2Un − β| > ε) < ∞.
Information Theoretic Approach to Geometric Programming
Authors: Brockett P. , Charnes A.
Published: October 2008

This paper shows how the fundamental geometric inequality lemma of geometric programming can be obtained immediately from information theoretic methods. This results in a drastic simplification of the proof and points the way to other connections between information theory and geometric programming.
Monotonicity in Generalized Semi-Markov Processes
Authors: Glasserman Paul , Yao David D.
Published: October 2008

We establish stochastic monotonicity of the event epoch sequences of generalized semi-Markov processes through the structure of the generalized semi-Markov schemes on which they are based. Our main condition states, roughly, that the occurrence of more events in the short run never leads to the activation of less events in the long run. We consider monotonicity with respect to two types of inputs: clock times (which translate to, e.g., service and interarrival times in queueing systems), and structural parameters (which translate to, e.g., buffer size, number of servers, and job population). For the second type of comparison, we replace a structural change with an equivalent change in clock times to reduce the comparison to one of the first type. When applied to queueing systems, our results yield new comparisons and also unify several existing results previously established using special properties of individual systems.
On the Convergence of Algorithms with Implications for Stochastic and Nondifferentiable Optimization
Authors: Higle Julia L. , Sen Suvrajeet
Published: October 2008

Studies of the convergence of algorithms often revolve around the existence of a function with respect to which monotonic descent is required. In this paper, we show that under relatively lenient conditions, “stage-dependent descent” (not necessarily monotonic) is sufficient to guarantee convergence. This development also provides the impetus to examine optimization algorithms. We show that one of the important avenues in the study of convergence, namely, the theory of epi-convergence imposes stronger conditions than are necessary to establish the convergence of an optimization algorithm. Working from a relaxation of epi-convergence, we introduce the notion of ∂-compatibility, and prove several results that permit relaxations of conditions imposed by previous approaches to algorithmic convergence. Finally, to illustrate the usefulness of the concepts, we combine stage-dependent descent with results derivable from ∂-compatibility to provide a basis for the convergence of a general algorithmic statement that might be used for stochastic and nondifferentiable optimization.
Bounds on the Sensitivity of Generalised Semi-Markov Processes with a Single Generally Distributed Lifetime
Authors: Coyle A. J. , Taylor P. G.
Published: October 2008

In this paper we present a method for finding bounds on the sensitivity of Generalised Semi-Markov Processes with a single generally distributed lifetime. This method gives upper and lower bounds for the value of a function of the stationary distribution as the distribution of the general lifetime ranges over a set of distributions with fixed mean. The method is applied to some simple queueing systems.
Jackson's Rule for Single-Machine Scheduling: Making a Good Heuristic Better
Authors: Hall Leslie A. , Shmoys David B.
Published: October 2008

We consider the scheduling problem in which jobs with release dates and delivery times are to be scheduled on one machine. We present a 4/3-approximation algorithm for the problem with precedence constraints among the jobs, and two polynomial approximation schemes for the problem without precedence constraints. At the core of each of the algorithms presented is Jackson's Rule—a simple but seemingly robust heuristic for the problem.
On the Continuous Trajectories for a Potential Reduction Algorithm for Linear Programming
Authors: Monteiro Renato D. C.
Published: October 2008

For a possibly degenerate linear program minx{cTx; Ax = b, x ≥ 0} (A is an m × n real matrix, b ∈ Rm and c ∈ Rn), whose optimal value is 0, we study the limiting behavior of the trajectories of the family of vector fields

Φq(x) ≡ −XPAX [Xc − q≡1(cTx) 1].

for all values of q ≥ n, where X is the diagonal matrix associated with x and PAX is the projection operator onto the null space of AX. A polynomial algorithm based on the directions Φq(x) has been presented by Gonzaga [6] when q = n or q = n + √n. We show that all trajectories of Φq(x) converge to the unique “center” of the optimal face of the given linear program. When this face consists of a unique vertex, it is shown that any trajectory of Φq(x) approaches this vertex along the same direction. When the optimal face consists of more than one point, we show that there is a threshold value τ > 0 such that: for q > τ, “most” of the trajectories of Φq(x) converge to the “center” tangentially to the optimal face and that the direction of approach of a trajectory of Φq(x) depends on the initial condition: for q < τ (q = τ), the trajectories of Φq(x) converge to the “center” along a unique direction (along several directions which depend on the initial condition) forming a positive angle with the optimal face.
Approximation Schemes for the Restricted Shortest Path Problem
Authors: Hassin Refael
Published: October 2008

This note contains two fully polynomial approximation schemes for the shortest path problem with an additional constraint. The main difficulty in constructing such algorithms arises since no trivial lower and upper bounds on the solution value, whose ratio is polynomially bounded, are known. In spite of this difficulty, one of the algorithms presented here is strongly polynomial. Applications to other problems are also discussed.
Sensitivity Analysis for Variational Inequalities
Authors: Qiu Yuping , Magnanti Thomas L.
Published: October 2008

In this paper we study the behavior of the local solutions of perturbed variational inequalities, governed by perturbations to both the variational inequality function and the feasible region. Assuming appropriate second-order and regularity conditions, we show that the perturbed local solution set is Lipschitz continuous and directionally differentiable. Even when the directional differentiability is not guaranteed, we are still able to describe and characterize first-order information concerning the perturbed local solution set. We also discuss relations to nonlinear programming sensitivity analysis.
On Solution Stability of the Linear Complementarity Problem
Authors: Gowda M. Seetharama , Pang Jong-Shi
Published: October 2008

In the paper [5], C. D Ha introduced the notion of stability of a linear complementarity problem at a solution point and established several sufficient conditions for stability to hold. In the present paper, we derive some new stability results which significantly improve Ha's results. Included in these new results are (i) a complete characterization of the stability condition under a nonsingularity assumption, and (ii) further characterizations of solution stability in the case of a linear complementarity problem with a fully semimonotone matrix.
Solving Convex Programs by Means of Ordinary Differential Equations
Authors: Flåm Sjur D.
Published: October 2008

Within a Hilbert space we consider nonsmooth convex programs with sharp constraints. Examples include all problem instances that are bounded and strictly feasible. To solve such programs we pursue an absolutely continuous trajectory generated by a differential inclusion of subgradient type. Whenever this inclusion offers some freedom of choice, we select a steepest descent direction. It is shown that the proposed algorithm converges to an optimal solution in finite time.
The Crown Inequalities for the Symmetric Traveling Salesman Polytope
Authors: Naddef D. , Rinaldi G.
Published: October 2008

We define a new family of valid inequalities for the Symmetric Traveling Salesman Polytope (STSP(n)), that is, the convex hull of the incidence vectors of all Hamiltonian cycles of a complete graph with n nodes. The smallest value of n for which the inequalities are defined is 8. We call these inequalities crown inequalities and we prove that they are facet-inducing for STSP(n), for n ≥ 8. We describe some extensions of the crown inequalities and we prove that they induce facets of STSP(n), as well. Finally, we discuss some issues on the possible applications of these inequalities in a polyhedral cutting-plane algorithm.
On Stationary Strategies in Borel Dynamic Programming
Authors: Feinberg Eugene A.
Published: October 2008

We consider a discrete time Markov decision model with Borel state and action spaces. It is proved that the supremum of the expected total rewards under all randomized stationary strategies is equal to the supremum of these rewards under all (nonrandomized) stationary strategies.
A Polyhedral Intersection Theorem for Capacitated Spanning Trees
Authors: Hall Leslie A. , Magnanti Thomas L.
Published: October 2008

In a two-capacitated spanning tree of a complete graph with a distinguished root vertex v, every component of the induced subgraph on V\{v} has at most two vertices. We give a complete, nonredundant characterization of the polytope defined by the convex hull of the incidence vectors of two-capacitated spanning trees. This polytope is the intersection of the spanning tree polytope on the given graph and the matching polytope on the subgraph induced by removing the root node and its incident edges. This result is one of very few known cases in which the intersection of two integer polyhedra yields another integer polyhedron. We also give a complete polyhedral characterization of a related polytope, the 2-capacitated forest polytope.
Gillies and Miller's Subrelations of a Relation over an Infinite Set of Alternatives: General Results and Applications to Voting Games
Authors: Bordes Georges , Le Breton Michel , Salles Maurice
Published: October 2008

In this paper, we have investigated two subrelations of a domination relation which is the classical collective relation in voting games. These two subrelations, due to Gillies and Miller, have some nice properties; in particular, they are transitive. From these subrelations one can define obvious solution concepts by taking their maximal elements. If the set of social states is infinite, however, the existence of maximal elements is far from obvious, due to the lack of continuity. We have assumed that the set of social states was a compact metric space. We have adopted a measure-theoretic analysis. In the case of Gillies' subrelation, we have obtained very general existence theorems. In the case of Miller's subrelation (the uncovered set), though our theorem is still more general than what can be found in the literature, it is still far from being at the same level of generality.
Existence of Stationary Correlated Equilibria with Symmetric Information for Discounted Stochastic Games
Authors: Nowak A. S. , Raghavan T. E. S.
Published: October 2008

The following theorem is proved: Every nonzero-sum discounted stochastic game in countably generated measurable state space with compact metric action spaces admits a stationary correlated equilibrium point with symmetric (public) information whenever the immediate rewards and transition densities are measurable with respect to the state variable and continuous with respect to joint actions.
Neighbors of the Origin for Four by Three Matrices
Authors: Shallcross David
Published: October 2008

Scarf has defined a neighborhood system for families of integer programs where the right-hand side is allowed to vary. This system depends on a matrix A of constraint and objective function coefficients of the integer programs.

This paper characterizes the set of neighbors of the origin when A is four by three, showing that it may be described as the set of integer vectors in a union of two-dimensional polyhedra, where the number of polyhedra is quadratic in the bit size of A.
Generalized Precedence-Based Queueing Systems
Authors: Liu Zhen , Baccelli François
Published: October 2008

A general K-server queueing model with precedence constraints on customer services is considered. Such a system is characterized by bulk arrivals of size K, with one customer for each server, and synchronization constraints between them and some of the previously arrived customers: Customer k (1 ≤ k ≤ K) of the nth (n ≥ 0) bulk arrival has to wait for the service completion of customer j (1 ≤ j ≤ K) of the mth (0 ≤ m ≤ n) arrival before starting its service, if there exists a precedence relation between these two customers. Such queueing systems arise naturally when modeling database concurrency control mechanisms based on “static” locking, as well as parallel computations where some processes may need results obtained by other processes for beginning their execution. Several performance aspects of this class of queueing systems are considered under various statistical assumptions. The stability condition, which yields the maximal system throughput, is analyzed together with the waiting and response times of individual customers, and the response times of bulks. These results are obtained from a set of recursive evolution equations which captures both the queueing and the synchronization mechanisms of the system. The stability condition is derived from a generalization of the schema of Loynes for G/G/1 queues. Integral functional equations are provided for both the transient and stationary distributions of the waiting and response times under renewal type assumptions. Various upper and lower bounds on the moments of these quantities are derived using either modifications of the precedence function or stochastic ordering techniques.
Normal Maps Induced by Linear Transformations
Authors: Robinson Stephen M.
Published: October 2008

We study a certain piecewise linear manifold, which we call the normal manifold, associated with a polyhedral convex set, and a family of continuous functions, called normal maps, that are induced on this manifold by continuous functions from Rn to Rn. These normal maps occur frequently in optimization and equilibrium problems, and the subclass of normal maps induced by linear transformations plays a key role.

Our main result is that the normal map induced by a linear transformation is a Lipschitzian homeomorphism if and only if the determinant of the map in each n-cell of the normal manifold has the same (nonzero) sign.
A New Lower Bound Via Projection for the Quadratic Assignment Problem
Authors: Hadley S. W. , Rendl F. , Wolkowicz H.
Published: October 2008

New lower bounds for the quadratic assignment problem QAP are presented. These bounds are based on the orthogonal relaxation of QAP. The additional improvement is obtained by making efficient use of a tractable representation of orthogonal matrices having constant row and column sums. The new bound is easy to implement and often provides high quality bounds under an acceptable computational effort.
The Generalized Basis Reduction Algorithm
Authors: Lovász László , Scarf Herbert E.
Published: October 2008

Let F(x) be a convex function defined in Rn, which is symmetric about the origin and homogeneous of degree 1, and let L be the lattice of integers Zn. A definition of a reduced basis, b1, …, bn, of the lattice with respect to the distance function F is presented, and we describe an algorithm which yields a reduced basis in polynomial time, for fixed n. In the special case in which the bodies {x: F(x) ≤ t} are ellipsoids, the definition of a reduced basis is identical with that given by Lenstra, Lenstra and Lovász (1982) and the algorithm is the well-known basis reduction algorithm.

We show that the basis vector b1, in a reduced basis, is an approximation to a shortest nonzero lattice point with respect to F and relate the basis vectors bi to Minkowski's successive minima. The results lead to an algorithm for integer programming which executes in polynomial time for fixed n, but which avoids the ellipsoidal approximations required by Lenstra's algorithm. We also discuss the properties of a Korkine-Zolotarev basis for the lattice.
Weak Approachability
Authors: Vieille N.
Published: October 2008

In this paper, we study repeated games with vector payoffs. Following Blackwell [2], we define weak approachability and its dual property, weak excludability. We use results from differential games with fixed duration to prove that every set is either weakly approachable or weakly excludable.
The Binested Inequalities for the Symmetric Traveling Salesman Polytope
Authors: Naddef Denis
Published: October 2008

In this paper we define a family of valid inequalities for the Symmetric Travelling Salesman Polytope which are defined on two nested sets of vertices of the graph. These inequalities generalize the comb inequalities of Chvàtal, Grötschel and Padberg, the clique tree inequalities of Grötschel and Pulleyblank, the path inequalities of Cornuéjols, Fonlupt and Naddef and the hyperstar inequalities of Fleischman. This is the largest known family of valid inequalities known so far. Facet inducing inequalities for the Symmetric Travelling Salesman Polytope contained in this class and in no other one are given proving that this is a proper generalization of the previously mentioned families.
Optimal Stationary Policies in General State Space Markov Decision Chains with Finite Action Sets
Authors: Ritt Robert K. , Sennott Linn I.
Published: October 2008

The result of Sennott [9] on the existence of optimal stationary policies in countable state Markov decision chains with finite action sets is generalized to arbitrary state space Markov decision chains. The assumption of finite action sets occurring in a global countable action space allows a particularly simple theoretical structure for the general state space Markov decision chain. Two examples illustrate the results. Example 1 is a system of parallel queues with stochastic work requirements, a movable server with controllable service rate, and a reject option. Example 2 is a system of parallel queues with stochastic controllable inputs, a movable server with fixed service rates, and a reject option.
Utility as an Additive Set Function
Authors: Fishburn Peter C.
Published: October 2008

Foundations for additive models of subset evaluation are stated by axioms for a preference relation on a family S of subsets of X that cover X. The axiomatizations include cases in which S is arbitrary, S contains only finite subsets of X, and S is the set of all subsets of X. Expected utility with subsets as outcomes is also considered.
The Optimal Reward Operator in Negative Dynamic Programming
Authors: Maitra A. , Sudderth W.
Published: October 2008

We consider the negative dynamic programming model of Strauch [12] and prove that the optimal reward function can be obtained by a transfinite iteration of the optimal reward operator. We show that a player loses nothing by restricting himself to measurable policies, if the returns from nonmeasurable policies are evaluated by lower integrals.