bluuebunny/crossref_metadata_2025 huggingface dataset:
Facets of the Asymmetric Traveling Salesman Polytope
Authors: Fischetti Matteo
Published: October 2008

In this paper we consider the Asymmetric Traveling Salesman polytope, Pn, defined as the convex hull of the incidence vectors of tours in a complete digraph with n vertices, and its monotonization, P̃n. Several classes of valid inequalities for both there polytopes have been introduced in the literature which are not known to define facets of Pn or P̃n. We describe a general technique which can often be used to prove that a given inequality defines a facet of Pn. The method is applied to prove that the so-called Dk+, Dk−, C3, comb and C2 inequalities define facets of Pn, thus solving open problems. As for the monotone polytope, a necessary and sufficient condition for a facet-defining inequality of Pn to define a facet of P̃n as well, is introduced which applies to the Dk+, Dk−, C3, comb and C2 inequalities. In addition, a simple procedure for transforming any facet-defining inequality of Pn into an equivalent one which also defines a facet of P̃n, is given.
Probabilistic Analysis of the Held and Karp Lower Bound for the Euclidean Traveling Salesman Problem
Authors: Goemans Michel X. , Bertsimas Dimitris J.
Published: October 2008

We analyze probabilistically the classical Held-Karp lower bound derived from the 1-tree relaxation for the Euclidean traveling salesman problem (ETSP). We prove that, if n points are identically and independently distributed according to a distribution with bounded support and absolutely continuous part f(x)dx over the d-cube, the Held-Karp lower bound on these n points is almost surely asymptotic to

βHK(d)n(d−1)/d ∫ f(x)(d−1)/d dx,

where βHK(d) is a constant independent of n. The result suggests a probabilistic explanation of the observation that the lower bound is very close to the length of the optimal tour in practice, since the ETSP is almost surely asymptotic to

βTSP(d)n(d−1)/d ∫ f(x)(d−1)/d dx.

The techniques we use exploit the polyhedral description of the Held-Karp lower bound and the theory of subadditive Euclidean functionals.
A Heavy Traffic Limit Theorem for Networks of Queues with Multiple Customer Types
Authors: Peterson William P.
Published: October 2008

The central result of this paper is a heavy traffic limit theorem for the vector of total station workloads in an open network of queues with multiple customer types, under first-come-first-served and priority disciplines. The limit process is a regulated Brownian motion on the nonnegative orthant, with parameters specified from the first two moments of the interarrival and service time distributions and a matrix of reduced routing information. Through the phenomenon of state space collapse, associated limit results for queue length, workload and sojourn time processes by customer type are obtained jointly as simple transformations of the total workload limit process. Diffusion approximations based on the theorem are discussed.
Small Travelling Salesman Polytopes
Authors: Boyd Sylvia C. , Cunningham William H.
Published: October 2008

We introduce a new class of valid inequalities for the polytope of the symmetric travelling salesman problem. We also gave complete characterizations of the polytope for 6 and 7 cities. For the latter case, the new inequalities are needed. These results are related to work of R. Z. Norman in the 1950's.
An Implicit-Function Theorem for a Class of Nonsmooth Functions
Authors: Robinson Stephen M.
Published: October 2008

In this paper we introduce the concept of strong approximation of functions, and a related concept of strong Bouligand (B-) derivative, and we employ these ideas to prove an implicit-function theorem for nonsmooth functions. This theorem provides the same kinds of information as does the classical implicit-function theorem, but with the classical hypothesis of strong Fréchet differentiability replaced by strong approximation, and with Lipschitz continuity replacing Fréchet differentiability of the implicit function. Therefore it is applicable to a considerably wider class of functions than is the classical theorem.

In the last part of the paper we apply this implicit function result to analyze local solvability and stability of perturbed generalized equations.
On the Number of Iterations of Piyavskii's Global Optimization Algorithm
Authors: Hansen P. , Jaumard B. , Lu S.-H.
Published: October 2008

Piyavskii's algorithm maximizes a univariate function f satisfying a Lipschitz condition. We compare the numbers of iterations needed by Piyavskir's algorithm (nP) to obtain a bounding function whose maximum value is within ε of the (unknown) globally optimal value with that required by the best possible algorithm (nB). The main result is that: nP ≤ 2nB + 1 and that this bound is sharp. We also show that the number of iterations needed by Piyavskii's algorithm to obtain a globally ε-optimal value together with a corresponding point (nPY) satisfies nPY ≤ 4nB + 1 and that this bound is again sharp. Lower and upper bounds on nB are obtained as functions of f(x), ε, L0, and L1, where L0 is the smallest valid Lipschitz constant and L1 the Lipschitz constant used. Several properties of nB and of the distribution of evaluation points are deduced from these bounds.
Multivariate Stochastic Dominance and Moments
Authors: O'Brien George L. , Scarsini Marco
Published: October 2008

The sequence ≥nd of nth degree stochastic dominances for d-dimensional distribution functions is defined. It is shown that, under some regularity conditions, ≥nd implies ≥nd−1 for the (d − 1)-dimensional marginals. Also some necessary conditions for ≥nd are established. These conditions, which involve moments, are analogous to the ones proved by Fishburn (1980b) and O'Brien (1984) for univariate distributions.
The Characterization of the Stationary Distribution of the Supplemented Self-Clocking Jump Process
Authors: Miyazawa Masakiyo
Published: October 2008

We introduce a Self-Clocking Jump Process (SCJP), which is a natural generalization of a generalized semi-Markov process and applies to a large class of queueing models. As a stochastic process, a SCJP is a special case of a process with an embedded marked point process. We characterize the stationary distribution of the supplemented SCJP and discuss some properties of it. We also give a mathematical base to the usual approach of Kolmogorov differential equations. We use an operator theoretic argument but most of the proofs are elementary.
An Analysis of Stochastic Shortest Path Problems
Authors: Bertsekas Dimitri P. , Tsitsiklis John N.
Published: October 2008

We consider a stochastic version of the classical shortest path problem whereby for each node of a graph, we must choose a probability distribution over the set of successor nodes so as to reach a certain destination node with minimum expected cost. The costs of transition between successive nodes can be positive as well as negative. We prove natural generalizations of the standard results for the deterministic shortest path problem, and we extend the corresponding theory for undiscounted finite state Markovian decision problems by removing the usual restriction that costs are either all nonnegative or all nonpositive.
Stochastic Decomposition: An Algorithm for Two-Stage Linear Programs with Recourse
Authors: Higle Julia L. , Sen Suvrajeet
Published: October 2008

We present a cutting plane algorithm for two-stage stochastic linear programs with recourse. Motivated by Benders' decomposition, our method uses randomly generated observations of random variables to construct statistical estimates of supports of the objective function. In general, the resulting piecewise linear approximations do not agree with the objective function in finite time. However, certain subsequences of the estimated supports are shown to accumulate at supports of the objective function, with probability one. From this, we establish the convergence of the algorithm under relatively mild assumptions.
Probabilistic Models for Linear Programming
Authors: Todd Michael J.
Published: October 2008

We propose and investigate new probabilistic models for linear programming. In contrast to previous models, ours guarantee the existence of optimal solutions and are symmetric under duality. While in some respects our distributions are very special, there is sufficient flexibility to permit an arbitrary degree of primal and/or dual degeneracy, either just at the optimal solution or throughout the feasible region using null variables. Moreover, the precision of the distributions allows us to compute the probability that the feasible region is bounded as well as the distribution of the distance to a constraint hyperplane and that of the components of a vertex. Interest in these measures stems from Karmarkar's algorithm, and we also introduce a model for generating random linear programming problems on a simplex.
Stable Equilibria—A Reformulation. Part II. Discussion of the Definition, and Further Results
Authors: Mertens Jean-François
Published: October 2008

This is the sequel of Mertens (1989). We discuss the geometric content of the definition, showing in particular the algebraic distinctions to matter. We provide an equivalent definition that gets rid of the need to use Hausdorff limits, and finally we show that a “decomposition axiom” eliminates most of the algebraic possibilities, leaving only the “p-stable” sets, for p zero or prime.
An Optimal Investment/Consumption Model with Borrowing
Authors: Fleming Wendell H. , Zariphopoulou Thaleia
Published: October 2008

This paper considers a consumption and investment decision problem for a single agent. Wealth is divided between a riskless asset and a risky asset with logarithmic Brownian motion price fluctuations. Short-selling is not allowed, but borrowing is allowed at rate exceeding the rate of return on the riskless asset. An explicit solution of the dynamic programming differential equation for the maximum total discounted expected utility function U is available only in the HARA case. However, using viscosity solution methods the asymptotic behavior of the value function v(x) is found for small wealth x and for large wealth x.
Numerical Methods for an Optimal Investment-Consumption Model
Authors: Fitzpatrick Ben G. , Fleming Wendell H.
Published: October 2008

This paper examines some numerical techniques for an investment/consumption problem considered by Fleming and Zariphopoulou. The value function v(x) satisfies the differential equation of dynamic programming for x > 0. Special monotonicity and concavity features of the problem allow us to prove convergence not only of discrete approximations to v(x), but of the corresponding discrete approximations to optimal investment and consumption policies.
Convergence and Boundary Behavior of the Projective Scaling Trajectories for Linear Programming
Authors: Monteiro Renato D. C.
Published: October 2008

We analyze the convergence and boundary behavior of the continuous trajectories of the vector field induced by the projective scaling algorithm as applied to (possibly degenerate) linear programming problems in Karmarkar's standard form. We show that a projective scaling trajectory tends to an optimal solution which in general depends on the starting point. When the optimal solution is unique, we show that all projective scaling trajectories approach the optimal solution through the same asymptotic direction. Our analysis is based on the affine scaling trajectories for the homogeneous standard form linear program that arises from Karmarkar's standard form linear program by removing the unique nonhomogeneous constraint.
On the Existence of an Arrow-Radner Equilibrium in the Case of Complete Markets. A Remark
Authors: Dana Rose-Anne , Pontier Monique
Published: October 2008

We consider a continuous time pure exchange stochastic economy with a financial sector. We first give a proof of the “equivalence” of Arrow-Radner and Arrow-Debreu equilibria under the assumption that the gains associated to the securities form a local martingale generator. We then give a simple proof of existence of an Arrow-Debreu equilibrium in the separable utility case, under the assumption that either all agents have finite marginal utility at zero or aggregate endowment is uniformly bounded below.
Two-Player Repeated Games with Nonobservable Actions and Observable Payoffs
Authors: Lehrer Ehud
Published: October 2008

This paper studies two-person repeated games in which after each stage a player is informed about the payoff he received at the previous stage. The information can, in some cases, include more than that. Four kinds of Nash-equilibrium concepts are defined by the limit of the means. A characterization of the equilibrium-payoffs sets and several properties of these sets are given. As a specific example, the standard information case, that of the folk theorem, is provided.
Queueing Simulation in Heavy Traffic
Authors: Asmussen Søren
Published: October 2008

The heavy traffic behavior of a number of standard queueing simulation procedures like sample averaging and regenerative simulation is studied. In particular, limit theorems based upon Brownian approximations are given in a double limit with both the sample size t tending to infinity and the traffic intensity ρ tending to one. The results demonstrate that the growth rate t = t(ρ) ≈ (1 − ρ)−2 plays a critical role, and it follows both from the present theoretical results and empirical illustrations in a companion paper that negative bias presents a serious problem. Furthermore the heavy traffic behavior of the limiting variances in the standard large sample theory is found.
Turnpike Optimality of Smith's Rule in Parallel Machines Stochastic Scheduling
Authors: Weiss Gideon
Published: October 2008

Consider scheduling a batch of jobs with stochastic processing times on parallel machines, with minimization of expected weighted flowtime as objective. Smith's Rule, which orders job starts by decreasing ratio of weight to expected processing time, provides a natural heuristic for this problem. In a previous paper we have found an upper bound for the difference between the expected objective under Smith's Rule and under the optimal strategy. In this paper we find an upper bound on the expected number of times that Smith's rule differs from the optimal decision. Under some mild and reasonable assumptions these bounds remain constant when the number of jobs increases. Hence, under these conditions Smith's Rule is asymptotically optimal, and it has a Turnpike Optimality property, that is, Smith's Rule is optimal most of the time.
A Uniform Tauberian Theorem in Dynamic Programming
Authors: Lehrer Ehud , Sorin Sylvain
Published: October 2008

We prove that, in dynamic programming framework, uniform convergence of vλ implies uniform convergence of vn and vice versa. Moreover, both have the same limit.
Fair Distribution Protocols or How the Players Replace Fortune
Authors: Bárány Imre
Published: October 2008

There are n ≥ 2 players P1, P2, …, Pn, each of them having a finite alphabet A1, …, An, and there is a probability distribution p on A = A1 × ⋯ × An. The players want to choose a ∈ A according to p in such a way that Pk knows only the kth component, ak, of a. This can be done with the help of an impartial person or “fortune” who chooses a ∈ A according to p and informs Pk on ak only. But what happens if no such person is available? Can the players find a procedure that replaces fortune? It is proved here that the answer is yes when n ≥ 4. As an application it is shown that a correlated equilibrium of a noncooperative n-person game (n ≥ 4) coincides with a Nash equilibrium of an extended game involving, in addition, plain conversations only.
Parametric Variational Inequalities with Multivalued Solution Sets
Authors: Kyparisis Jerzy
Published: October 2008

In this paper we study basic properties of multivalued solution sets of parametric variational inequalities under the assumption that the unperturbed problem has a locally unique solution. We derive general existence and Lipschitz continuity results, which extend previous developments, for multivalued solution set maps of parametric variational inequalities defined on polyhedral sets. These results, when applied to parametric nonlinear complementarity problems, yield existence and Lipschitz continuity of multivalued solutions under new conditions on the Jacobian matrix of the variational function. We also obtain a novel result on the existence of (nonunique) solutions to parametric variational inequalities defined on perturbed sets. Finally, we show that the recent directional differentiability results of Qiu and Magnanti can be derived in a unified manner under somewhat more general assumptions which, in particular, makes them applicable to nonlinear complementarity problems.
On a Preemptive Markovian Queue with Multiple Servers and Two Priority Classes
Authors: Gail H. R. , Hantler S. L. , Taylor B. A.
Published: October 2008

We consider a queueing system with multiple servers and two classes of customers operating under a preemptive resume priority rule. The arrival process for each class is Poisson, and the service times are exponentially distributed with different means. In a convenient state space representation of the system, we obtain the matrix equation for the two-dimensional, vector-valued generating function of the equilibrium probability distribution. We give a rigorous proof that, by successively eliminating variables from the matrix equations, a nonsingular, block tridiagonal system of equations is obtained for the set of (m + 1)(m + 2)/2 constants that describe the probabilities of the states of the system when no customers are awaiting service. The mean waiting time of the low priority customers is shown to be given by a simple formula in terms of the (known) waiting time of the high priority customers and the expected number of low priority customers in the queue when no high priority customers are waiting.
A Probabilistic Approach to the Generalized Hessian
Authors: Haussmann U. G.
Published: October 2008

The quadratic variation of Brownian motion is used to give a new definition of a generalized Hessian for nonsmooth functions, totally independently of any gradients. A calculus is developed for the generalized Hessian of functions whose gradient is Lipschitz. It is also shown that for convex functions the Hessian is nonempty.
Global Convergence Property of the Affine Scaling Methods for Primal Degenerate Linear Programming Problems
Authors: Tsuchiya Takashi
Published: October 2008

In this paper we investigate the global convergence property of the affine scaling method under the assumption of dual nondegeneracy. The behavior of the method near degenerate vertices is analyzed in detail on the basis of the equivalence between the affine scaling methods for homogeneous LP problems and Karmarkar's method. It is shown that the step-size 1/8, where the displacement vector is normalized with respect to the distance in the scaled space, is sufficient to guarantee the global convergence for dual nondegenerate LP problems. The result can be regarded as a counterpart to Dikin's global convergence result on the affine scaling method assuming primal nondegeneracy.
Globally Convergent Newton Methods for Nonsmooth Equations
Authors: Han Shih-Ping , Pang Jong-Shi , Rangaraj Narayan
Published: October 2008

This paper presents some globally convergent descent methods for solving systems of nonlinear equations defined by locally Lipschitzian functions. These methods resemble the well-known family of damped Newton and Gauss-Newton methods for solving systems of smooth equations; they generalize some recent Newton-like methods for solving B-differentiable equations which arise from various mathematical programs.
Entropic Proximal Mappings with Applications to Nonlinear Programming
Authors: Teboulle Marc
Published: October 2008

We introduce a family of new transforms based on imitating the proximal mapping of Moreau and the associated Moreau-Yosida proximal approximation of a function. The transforms are constructed in terms of the φ-divergence functional (a generalization of the relative entropy) and of Bregman's measure of distance. An analogue of Moreau's theorem associated with these entropy-like distances is proved. We show that the resulting Entropic Proximal Maps share properties similar to the proximal mapping and provide a fairly general framework for constructing approximation and smoothing schemes for optimization problems. Applications of the results to the construction of generalized augmented Lagrangians for nonlinear programs and the minimax problem are presented.
Reflecting Ito Processes in a Stochastic Control Problem
Authors: Athreya K. B. , Weerasinghe A.
Published: October 2008

Let X(·) be an Ito process with reflection at 0 and state space [0, ∝) and with nonanticipating infinitesimal coefficients μ(·) and σ(·). Let LX(·) be the process of local time at 0 for this X. Suppose that, for each t, (σ(t), μ(t)) are restricted to be in the set A(X(t)) where {A(y); 0 ≤ y < ∞} is a given family of sets in R+ × R. Let Σ(x) be the class of all such Ito processes satisfying X(0) = x. Consider the stochastic control problem of maximizing P(LX(Ta) ≤ y|X(0) = x) over all X in Σ(x) where Ta = inf{t : X(t) = a}. It is shown here (under a natural hypothesis on the family A(·)) that for all (a, y) in R+ × R+ and all x in [0, a) the optimal solution is a reflecting diffusion which maximizes μ/σ2.
Computational Complexity of a Cost Allocation Approach to a Fixed Cost Spanning Forest Problem
Authors: Granot Daniel , Granot Frieda
Published: October 2008

We present a computational analysis of a game theoretic approach to a cost allocation problem arising from a graph optimization problem, referred to as the fixed cost spanning forest (FCSF) problem. The customers in the FCSF problem, represented by nodes in a graph G, are in need of service that can be produced at some facilities yet to be constructed. The cost allocation problem is concerned with the fair distribution of the cost of providing the service among customers. We formulate this cost allocation problem as a cooperative game, referred to as the FCSF game. In general, the core of a FCSF game may be empty. However, for the case when G is a tree, it is shown that the core is not empty. Moreover, we prove that in this case core points can be generated in strongly polynomial time. We further provide a nonredundant characterization of the core of the FCSF game defined over a tree in the special case when all nodes are communities. This is shown to lead, in some instances, to a strongly polynomial algorithm for computing the nucleolus.
Cyclic Schedules for Job Shops with Identical Jobs
Authors: Roundy Robin
Published: October 2008

We consider the problem of finding cyclic schedules for a job shop in which all jobs are identical. Specifically, we assume that a single product is produced on a finite number of machines. Each part is manufactured by performing a given set of operations in a pre-determined sequence. Each operation can be performed on exactly one machine.

Key structural properties of cyclic schedules are studied. A search algorithm based on these properties is proposed, and preliminary computational tests of the algorithm are reported.
Optimality in Accelerated Life Tests
Authors: Del Grosso G. , Gerardi A. , Koch G.
Published: October 2008

We formulate a stochastic control problem arising from the optimal design of accelerated life tests. The model is obtained, in a natural way, in the setup of point processes. The cost functional depends on the total number of items under test at time t, the observed number of items failed up to time t, and the stress level applied to the items under test at time t. The optimal policy minimizing the cost functional is characterized via the dynamic programming equation. After a further specification of the model, we prove that the solution is of bang-bang type. In some specific cases, we also prove that the control problem is equivalent to an optimal stopping problem. This amounts to simply running the test, with the number of items and the stress level at their highest available value, up to the exit time of the state process from a given region. In this special case we exhibit an explicit solution and give a criterion in order to decide whether to let the experiment run or to stop it.
Asymptotic Theory for Solutions in Statistical Estimation and Stochastic Programming
Authors: King Alan J. , Rockafellar R. Tyrrell
Published: October 2008

New techniques of local sensitivity analysis for nonsmooth generalized equations are applied to the study of sequences of statistical estimates and empirical approximations to solutions of stochastic programs. Consistency is shown to follow from a certain local invertibility property, and asymptotic distributions are derived from a generalized implicit function theorem that characterizes asymptotic behavior in situations where estimates are subjected to constraints and estimation functionals are nonsmooth.
Convergence Analysis of Some Algorithms for Solving Nonsmooth Equations
Authors: Qi Liqun
Published: October 2008

This paper presents convergence analysis of some algorithms for solving systems of nonlinear equations defined by locally Lipschitzian functions. For the directional derivative-based and the generalized Jacobian-based Newton methods, both the iterates and the corresponding function values are locally, superlinearly convergent. Globally, a limiting point of the iterate sequence generated by the damped, directional derivative-based Newton method is a zero of the system if and only if the iterate sequence converges to this point and the stepsize eventually becomes one, provided that the system is strongly BD-regular and semismooth at this point. In this case, the convergence is superlinear. A general attraction theorem is presented, which can be applied to two algorithms proposed by Han, Pang and Rangaraj. A hybrid method, which is both globally convergent (in the sense of finding a stationary point of the norm function of the system) and locally quadratically convergent, is also presented.
Queues in Series via Interacting Particle Systems
Authors: Srinivasan Rengarajan
Published: October 2008

In this paper, we consider a serial network with very large (infinite) number of single server queues. Initially, the network is empty. The input process to the network is Poisson with rate less than one (unsaturated case) or one (saturated case) and the service times at each queue is exponential with mean one. We exploit results for interacting particle systems, in particular, the zero-range and simple-exclusion processes to investigate the approach to equilibrium of this network. We derive the hydrodynamic limit of this queueing network which dramatically describes the transient behavior of this network.
A Fully Polynomial-Time Approximation Algorithm for Computing a Stationary Point of the General Linear Complementarity Problem
Authors: Ye Yinyu
Published: October 2008

We apply a potential reduction algorithm to solve the general linear complementarity problem (GLCP)

minimize xTy

subject to Ax + By + Cz = q and (x, y, z) ≥ 0.

We show that the algorithm is a fully polynomial-time approximation scheme (FPTAS) for computing an ε-approximate stationary point of the GLCP. Note that there are some GLCPs in which every stationary point is a solution (xTy = 0). These include the LCPs with row sufficient matrices. We also show that the algorithm is a polynomial-time algorithm for a special class of GLCPs.
A Lot-Sizing Problem on Trees, Related to Network Design
Authors: Bienstock Daniel
Published: October 2008

We describe a capacity expansion problem on trees, which arises in the design of certain communications networks, and is related to the knapsack and the economic lot-sizing problems. One of the main features is that production takes place in fixed (and possibly large) batch sizes. Another feature is that there may be various commodities competing for capacity resources. We present various exact and ε-approximate algorithms for this problem.
Unbounded Utility for Savage's “Foundations of Statistics,” and Other Models
Authors: Wakker Peter
Published: October 2008

A general procedure for extending finite-dimensional “additive-like” representations for binary relations to infinite-dimensional “integral-like” representations is developed by means of a condition called truncation-continuity. The restriction of boundedness of utility, met throughout the literature, can now be dispensed with, and for instance normal distributions, or any other distribution with finite first moment, can be incorporated. Classical representation results of expected utility, such as Savage (1954), von Neumann and Morgenstern (1944), Anscombe and Aumann (1963), de Finetti (1937), and many others, can now be extended. The results are generalized to Schmeidler's (1989) approach with nonadditive measures and Choquet integrals, and Quiggin's (1982) rank-dependent utility. The different approaches have been brought together in this paper to bring to the fore the unity in the extension process.
Sensors and Information in Optimization Under Stochastic Uncertainty
Authors: Artstein Zvi , Wets Roger J-B.
Published: October 2008

The paper offers a framework for the analysis of information available in stochastic optimization problems. The setup proposed here applies to the situation where the decision maker can seek more information about the stochastics of the problem. The information collected in the inquiry only allows for a redefinition of the distribution of the stochastic elements, and the inquiry process itself may introduce new errors and uncertainties. The tool we introduce is termed sensor. Compared with previous methods of analyzing information, e.g., σ-fields or signals, sensors allow for a quantitative analysis in the evaluation of the gain that may result in inquiring information. In this paper we work out the abstract model, and demonstrate it on a concrete problem, which is solved numerically.
Stability of Solutions for Stochastic Programs with Complete Recourse
Authors: Römisch Werner , Schultz Rüdiger
Published: October 2008

Quantitative continuity of optimal solution sets to convex stochastic programs with (linear) complete recourse and random right-hand sides is investigated when the underlying probability measure varies in a metric space. The central result asserts that, under a strong-convexity condition for the expected recourse in the unperturbed problem, optimal tenders behave Hölder-continuous with respect to a Wasserstein metric. For linear stochastic programs this carries over to the Hausdorff distance of optimal solution sets A general sufficient condition for the crucial strong-convexity assumption is given and verified for recourse problems with separable and nonseparable objectives.
Linear Stationary Point Problems on Unbounded Polyhedra
Authors: Dai Yang , Talman Dolf
Published: October 2008

In this paper we propose a complementary pivoting algorithm for finding a stationary point of an affine function on an unbounded polyhedron. Under some mild conditions there is a piecewise linear path from an arbitrarily chosen point in the polyhedron leading to a solution of the problem. By exploiting fully the linearity of the problem, each linear piece of the path is followed in principle by making just one linear programming pivoting step.
Optimal Stopping by Means of Point Process Observations with Applications in Reliability
Authors: Jensen Uwe , Hsu Guang-Hui
Published: October 2008

A problem in reliability is considered in which only partial information is available. Some technical system is assumed to work in one of N unobservable states. The changes of the states are driven by a Markov process with known characteristics. The system fails from time to time according to a point process with a failure rate (intensity) which depends on the unobservable state. After failure a minimal repair is carried out immediately which leaves the state of the system unchanged. It is investigated under which conditions there exists an optimal time to stop operating the system with respect to some reward functional. The only available information is given by the failure point process observations. An explicit solution to this optimal stopping problem with partial information is derived. The problem is solved in the martingale framework. Results for monotone stopping problems are used and a generalization of the so-called monotone case is considered. The well-known disruption or disorder or detection problem is a special case (N = 2) and will be examined in the given context.
Optimal Bin Packing of Items of Sizes Uniformly Distributed over [0, 1]
Authors: Rhee Wansoo T.
Published: October 2008

Consider n independent random variables uniformly distributed over [0, 1] and consider the minimum number Bk of unit size bins needed to pack these items under the restriction that no bin can accept more than k items. We prove that EB2 − EB3 is of order √n. But in sharp contrast, we show that EB3 − EBn is of a smaller order.
Quadratic Convergence in a Primal-Dual Method
Authors: Mehrotra Sanjay
Published: October 2008

We show that the Mizuno-Todd-Ye O(√nL) iteration predictor-corrector primal-dual interior-point algorithm for linear programming is quadratically convergent. Our proof does not assume that the problems be nondegenerate. We do not assume that the iterate generated by the algorithm be convergent, an assumption common to all previous asymptotic convergence analysis.
An Axiomatization of the Core of Market Games: A Correction
Authors: Peleg Bezalel
Published: October 2008

The proof of Lemma 4.7 in Peleg (Peleg, B. 1989. An axiomatization of the core of market games. Math. Oper. Res. 14 448–456.) is incorrect. However, if we add the following innocent axiom, the proof of the lemma becomes straightforward.
Convergence of the Value Functions of Discounted Infinite Horizon Optimal Control Problems with Low Discount Rates
Authors: Wirth Fabian
Published: October 2008

For autonomous, nonlinear, smooth optimal control systems on n-dimensional manifolds we investigate the relationship between the discounted and the average yield optimal value of infinite horizon problems.

It is shown that the value functions of discounted problems converge to the value function of the average yield problem as the discount rate tends to zero, if there exist approximately optimal solutions satisfying some periodicity conditions. In general, the discounted value functions cannot be expected to converge, which is shown by a counterexample. A connection to geometric control theory is then made to establish a result of uniform convergence on compact subsets of the interior of control sets, if optimal trajectories do not leave a compact subset of the interior of these control sets.
Lot-Sizing with Constant Batches: Formulation and Valid Inequalities
Authors: Pochet Yves , Wolsey Laurence A.
Published: October 2008

We consider the classical lot-sizing problem with constant production capacities (LCC) and a variant in which the capacity in each period is an integer multiple of some basic batch size (LCB).

We first show that the classical dynamic program for LCC simplifies for LCB leading to an O(n2 min{n, C}) algorithm (where n is the number of periods and C the batch size). Using this new algorithm, we show how to formulate both problems as linear programs with O(n3) variables and constraints.

A class of so-called (k, l, S, I) inequalities are described for LCB which capture both the dynamic nature of the problem as well as the capacity aspects. For LCB, we prove that these inequalities are the only facet-defining inequalities of a certain form. For LCC, we show that these inequalities include all the known classes of valid inequalities. Finally, we discuss several open questions and possible extensions.
On the Convergence Rate of Dual Ascent Methods for Linearly Constrained Convex Minimization
Authors: Luo Zhi-Quan , Tseng Paul
Published: October 2008

We analyze the rate of convergence of certain dual ascent methods for the problem of minimizing a strictly convex essentially smooth function subject to linear constraints. Included in our study are dual coordinate ascent methods and dual gradient methods. We show that, under mild assumptions on the problem, these methods attain a linear rate of convergence. Our proof is based on estimating the distance from a feasible dual solution to the optimal dual solution set by the norm of a certain residual.
Applications of Degree Theory to Linear Complementarity Problems
Authors: Gowda M. Seetharama
Published: October 2008

In this paper, we consider two applications of degree theory to linear complementarity problems. In the first application, we study the stability of an LCP at a solution point. Specifically we prove the stability of an LCP corresponding to a P0-matrix at an isolated solution. Using a recent degree formula due to Stewart 1991, we strengthen a stability result of Gowda and Pang 1992. In the second application, we use the same degree formula of Stewart to describe the number of solutions of LCP(M, q) when M is a negative almost N-matrix. This analysis leads to a Lipschitzian characterization of the solution map Φ: q ↦ SOL(M, q) corresponding to a nondegenerate negative matrix.
Majorization and Schur Convexity with Respect to Partial Orders
Authors: Hwang Frank K. , Rothblum Uriel G.
Published: October 2008

Majorization and Schur convexity constitute an important tool for establishing inequalities, in particular, due to the Schur-Ostrowski Theorem which provides a simple characterization of Schur convex functions through local two-coordinate conditions. However, the usefulness of the approach is limited by two stringent requirements. First, every Schur convex function must be symmetric. Second, the necessary and sufficient conditions for Schur convexity involve every pair of coordinates on its (symmetric) domain. Several attempts have been made to relax these two requirements. In particular, a more general concept of “majorization with respect to partial orders” was introduced to prepare for such tasks, but it did not capture the classic theory for symmetric functions. In the current paper we obtain the desired generalization by developing a theory of majorization and Schur convexity with respect to partial orders over subsets of Euclidean spaces. Our results are used in Hwang, Rothblum and Shepp (1993) to address some optimal assembly problems.
A General Framework of Continuation Methods for Complementarity Problems
Authors: Kojima Masakazu , Megiddo Nimrod , Mizuno Shinji
Published: October 2008

A general class of continuation methods is presented which, in particular, solve linear complementarity problems with compositive-plus and L*-matrices. Let a, b ∈ Rn be nonnegative vectors. We embed the complementarity problem with a continuously differentiable mapping f: Rn → Rn in an artificial system of equations

(*)   F(x, y) = (μa, ζb) and (x, y) ≥ 0,

where F: R2n → R2n is defined by

F(x, y) = (x1y1, …, xnyn, y − f(x))

and μ ≥ 0 and ζ ≥ 0 are parameters. A pair (x, y) is a solution of the complementarity problem if and only if it solves (*) for μ = 0 and ζ = 0. A general idea of continuation methods founded on the system (*) is as follows:

(1) Choose n-dimensional vectors a ≥ 0 and b > 0 such that the system (*) has a trivial solution (x1, y1) for some μ1, ζ1 ≥ 0.

(2) Trace solutions of (*) from (x1, y1) with μ = μ1 and ζ = ζ1 as the parameters μ and ζ are decreased to zero.

This idea provides a theoretical basis for various methods such as Lemke's method and a method of tracing the central trajectory of linear complementarity problems.
On Adaptive-Step Primal-Dual Interior-Point Algorithms for Linear Programming
Authors: Mizuno Shinji , Todd Michael J. , Ye Yinyu
Published: October 2008

We describe several adaptive-step primal-dual interior point algorithms for linear programming. All have polynomial time complexity while some allow very long steps in favorable circumstances. We provide heuristic reasoning for expecting that the algorithms will perform much better in practice than guaranteed by the worst-case estimates, based on an analysis using a nonrigorous probabilistic assumption.
A Heavy-Traffic Limit for the Cycle Counting Process in G/G/1, Optional Interruptions and Elastic Screen Brownian Motion
Authors: Kella Offer , Taksar Michael I.
Published: October 2008

We consider a queue in which the server is available for primary customers for a random number of busy cycles, after which he leaves for a random amount of time as soon as the system becomes empty. Under appropriate normalization we establish a heavy traffic limit which turns out to be a regenerative generalized elastic screen process (RGESP) with random jumps or linear parts of the trajectories. These jumps or linear parts occur when the local time at zero accumulates to a certain random level. As a main tool we first establish a heavy traffic limit theorem for the renewal counting process associated with the busy cycles in the underlying queueing system. In particular we show that this limit is proportional to the local time at zero of a reflected Brownian motion. We compare the stationary distribution for the RGESP with the corresponding one for the M/G/1 queue, where for both explicit expressions are obtained, and show that the results are consistent.
Stochastic Equilibria in Nonhomogeneous Markov Population Replacement Processes
Authors: Gerontidis Ioannis I.
Published: October 2008

This paper is an exposition on the dynamic stochastic equilibria in multi-type time dependent Markov population processes for different types of environmental behaviour. The joint multivariate cumulant generating function of the various population sizes at any time is derived together with the covariance structure both with and without time lags. An asymptotic analysis shows that there are either one or several equilibria of dynamic character, depending critically on the behaviour of the system parameters as well as on the total population size. The possible stochastic equilibria are characterized as stable or unstable according to whether or not they are independent of initial conditions.
From Totally Unimodular to Balanced 0, ±1 Matrices: A Family of Integer Polytopes
Authors: Conforti Michele , Cornuéjols Gérard , Truemper Klaus
Published: October 2008

In this paper we introduce a family of integer polytopes and characterize them in terms of forbidden submatrices. The two extreme cases in this family arise when the constraint matrix is totally unimodular and balanced, respectively. This generalizes results of Truemper-Chandrasekaran and Conforti-Cornuéjols.
A Polynomial Algorithm for the k-cut Problem for Fixed k
Authors: Goldschmidt Olivier , Hochbaum Dorit S.
Published: October 2008

The k-cut problem is to find a partition of an edge weighted graph into k nonempty components, such that the total edge weight between components is minimum. This problem is NP-complete for an arbitrary k and its version involving fixing a vertex in each component is NP-hard even for k = 3. We present a polynomial algorithm for k fixed, that runs in O(nk²/2−3k/2+4T(n, m)) steps, where T(n, m) is the running time required to find the minimum (s, t)-cut on a graph with n vertices and m edges.
A Polynomial Approximation Scheme for a Constrained Flow-Shop Scheduling Problem
Authors: Hall Leslie A.
Published: October 2008

We present a polynomial approximation scheme for a two-machine flow shop scheduling problem with the additional constraint that each job has a release date, when it first becomes available for processing. This is one of the first such results for multiple-task scheduling problems; previously, the best approximation result for this problem was an algorithm guaranteed to deliver a schedule of length at most 5/3 times the optimal length. Our (1 + ε)-approximation algorithm is intuitively appealing because it is based on Johnson's algorithm, an optimization algorithm for the problem without release dates.
A Fully Polynomial Approximation Scheme for Scheduling a Single Machine to Minimize Total Weighted Late Work
Authors: Kovalyov M. Y. , Potts C. N. , van Wassenhove L. N.
Published: October 2008

This paper studies approximation algorithms for the problem of nonpreemptively scheduling n jobs on a single machine to minimize total weighted late work, where the late work for a job is the amount of processing of this job that is performed after its due date. A family of approximation algorithms {DPε} is derived. For any ε > 0, DPε delivers a schedule having total weighted late work which does not exceed (1 + ε) times that of an optimal schedule. Since DPε requires O(n3 log n + n3/ε) time, the family {DPε} is a fully polynomial approximation scheme.
Strongly Polynomial Algorithms for the Quadratic Transportation Problem with a Fixed Number of Sources
Authors: Cosares Steven , Hochbaum Dorit S.
Published: October 2008

The Transportation problem with a linear objective function is known to be solvable in strongly polynomial time, whereas instances with a convex nonquadratic objective function are not, even for cases with the integrality constraints relaxed. We present a linear time algorithm for the Continuous Quadratic Transportation problem (QTP) with two source nodes. Further, we show how problem instances with a fixed number of source (or destination) nodes, k, could be solved in strongly polynomial time, O(nk+1), using an algebraic tree computation model. The algorithms exploit a relationship between the Transportation problem and the Resource Allocation problem. The strong polynomiality of the algorithms presented here imply the existence of strongly polynomial algorithms for Integer Quadratic Transportation problems with a fixed number of source nodes as well.
Risk Theory in a Periodic Environment: The Cramér-Lundberg Approximation and Lundberg's Inequality
Authors: Asmussen Søren , Rolski Tomasz
Published: October 2008

A risk process with the claim arrival intensity β(t), the claim size distribution β(t) and the premium rate p(t) at time t being periodic functions of t is considered. It is shown that the adjustment coefficient γ* is the same as for the standard time-homogeneous compound Poisson risk process obtained by averaging the parameters over a period, and a suitable version of the Cramér-Lundberg approximation for the ruin probability ψ(s)(u) with initial reserve u and initial season s is derived. An approximation in terms of a Markovian environment model with n states is studied, and limit theorems describing the rate of convergence γn → γ* are given. Finally, various upper and lower bounds of Lundberg type for the ruin probabilities are derived for both the periodic and the Markov-modulated model. By time-reversion, the results apply also to periodic M/G/1 queues.
Stochastic Convexity and Concavity of Markov Processes
Authors: Li Haijun , Shaked Moshe
Published: October 2008

In this paper we consider the temporal stochastic convexity and concavity properties of Markov processes {X(t), t ∈ S} in discrete time (then S = N+ ≡ {0, 1, 2, …}) or in continuous time (then S = [0, ∞)). That is, we obtain conditions on the process {X(t), t ∈ S} which imply that the expectation Ef(X(t)) is a monotone convex (concave) function of t whenever f is a monotone convex (concave) function. The theory is illustrated through some examples. After giving some background we define ℱ-monotonicity and then obtain some general results concerning stochastic convexity and concavity of Markov processes by using the notion of ℱ-monotone operators. We then introduce a method for identifying ℱ-monotone operators, and we discuss the relationship between our results concerning temporal convexity and other results in the literature. In particular, we center our attention on a notion of stochastic concavity. In this respect we show that a result of Shaked and Shanthikumar is incorrect and we prove two alternative versions of it.

The approach that we use here is an operator-analytic approach. This approach is quite powerful, but not as intuitive as sample path approaches used in other papers. However, using it, we can obtain results that we could not obtain otherwise.