bluuebunny/crossref_metadata_2025_split huggingface dataset:
Player Type Distributions as State Variables and Information Revelation in Zero Sum Repeated Games with Discounting
Authors: Bergin James 
Published: October 2008

This paper examines the role of the player type distributions in repeated zero sum games of incomplete information with discounting of payoffs. In particular the strategic “sufficiency” of the posterior distributions for histories and the limiting properties of the posterior sequence are discussed. It is shown that differentiability of the value function is sufficient to allow the posteriors to serve as “state” variables for histories. The limiting properties of the posterior distributions are considered and a characterization given of the set of possible limit points of the posterior distribution. This characterization is given in terms of the “value” of information in the one-stage game.
Probabilistic Analysis of Network Flow Algorithms
Authors: Karp Richard M. , Motwani Rajeev , Nisan Noam 
Published: October 2008

This paper is concerned with the design and probabilistic analysis of algorithms for the maximum-flow problem and capacitated transportation problems. These algorithms run in linear time and, under certain assumptions about the probability distribution of edge capacities, obtain an optimal solution with high probability. The design of our algorithms is based on the following general method, which we call the mimicking method, for solving problems in which some of the input data are deterministic and some are random with a known distribution: 1. Replace each random variable in the problem by its expectation; this gives a deterministic problem instance that has a special form, making it particularly easy to solve; 2. Solve the resulting deterministic problem instance; 3. Taking into account the actual values of the random variables, mimic the solution of the deterministic instance to obtain a near-optimal solution to the original problem; 4. Fine-tune this suboptimal solution to obtain an optimal solution. We present linear time algorithms to compute a feasible flow in directed and undirected capacitated transportation problem instances. The algorithms are shown to be successful with high probability when the probability distribution of the input data satisfies certain assumptions. We also consider the maximum flow problem with multiple sources and sinks. We show that with high probability the minimum cut isolates either the sources or the sinks, and we give a linear-time algorithm that produces a maximum flow with high probability.
Stochastic Machine Minimization with Constant Service Times
Authors: Coffman E. G. , Flatto Leopold , Wright Paul E. 
Published: October 2008

We consider the nonpreemptive scheduling of n ≥ 1 jobs on identical, parallel machines. With job running times all given by some constant, the objective is to minimize the expected number of machines needed throughout a schedule subject to the following waiting-time constraints. At time 0, a timer with (random) initial value W is started; after time W all jobs must either be finished or running on a machine. The value of W is not known in advance, but its distribution is made available to the scheduler. In general, if job running times are random, there might be situations in which, after running jobs on a given number of machines, it would be desirable to activate new machines, because the remaining times of unfinished jobs are stochastically too large compared to the time remaining on the timer. A principal result of this paper is that randomness of job running times is essential to such situations; if running times are deterministic, then irrespective of the distribution of W, an optimal policy initially assigns jobs to some number of machines kn (which depends on the distribution of W), and maintains that number while there are jobs available, until the timer has expired, at which point any remaining, as yet unscheduled jobs are assigned to new, unused machines. This paper also analyzes the dependence of kn and the minimal expected cost on the parameters of the timer distribution when W is either exponentially distributed or uniformly distributed on a finite interval. The determination of kn turns out to have an intriguing number-theoretic flavor.
Filtered Monte Carlo
Authors: Glasserman Paul 
Published: October 2008

By a filtered Monte Carlo estimator we mean one whose constituent parts—summands or integral increments—are conditioned on an increasing family of σ-fields. Unbiased estimators of this type are suggested by compensator identities. Replacing a point-process integrator with its intensity gives rise to one class of examples; exploiting Levy's formula gives rise to another. We establish variance inequalities complementing compensator identities. Among estimators that are (Stieltjes) stochastic integrals, we show that filtering reduces variance if the integrand and the increments of the integrator have conditional positive correlation. We also provide more primitive hypotheses that ensure this condition, making use of stochastic monotonicity properties. Our most detailed conditions apply in a Markov setting where monotone, up-down, and convex generators play a central role. We give examples. As an application of our results, we compare certain estimators that do and do not exploit the property that Poisson arrivals see time averages.
On Quadratic Cost Criteria for Option Hedging
Authors: Schäl Manfred 
Published: October 2008

Consider an option with maturity time T corresponding to a contingent claim H (in an incomplete market). A fair hedging price for H should take into account an optimal dynamical hedging plan against H. Let Ct be the cumulative cost and ℑt be the set of events of the history up to time t. You can choose the plan at time t such that you minimize (i) E[{Ct+1 − Ct}2 ∣ ℑt], (ii) E[{CT − Ct}2 ∣ ℑt], or (iii) E[{CT − C0}2]. Sufficient conditions on the underlying stochastic process (in discrete time) are provided such that the fair hedging price does not depend on the choice of (i), (ii), or (iii), which fact should increase its acceptability.
Denumerable Constrained Markov Decision Processes and Finite Approximations
Authors: Altman Eitan 
Published: October 2008

The purpose of this paper is two fold. First to establish the theory of discounted constrained Markov decision processes with a countable state and action spaces with general multi-chain structure. Second, to Introduce finite approximation methods. We define the occupation measures and obtain properties of the set of all achievable occupation measures under the different admissible policies. We establish the optimality of stationary policies for the constrained control problem, and obtain an LP with a countable number of decision variables through which stationary optimal policies are computed. Since for such an LP one cannot expect to find an optimal solution in a finite number of operations, we present two schemes for finite approximations and establish the convergence of optimal values and policies for both the discounted and the expected average cost, with unbounded cost. Sometimes It turns out to be easier to solve the problem with infinite state space than the problem with finite yet large state space. Based on the optimal policy for the problem with infinite state space, we construct policies which are almost optimal for the problem with truncated state space. This method is applied to obtain an ε-optimal policy for a problem of optimal priority assignment under constraints for a system of K finite queues.
An O(√nL)-Iteration Homogeneous and Self-Dual Linear Programming Algorithm
Authors: Ye Yinyu , Todd Michael J. , Mizuno Shinji 
Published: October 2008

We present an O(√nL)-iteration homogeneous and self-dual linear programming (LP) algorithm. The algorithm possesses the following features: • It solves the linear programming problem without any regularity assumption concerning the existence of optimal, feasible, or interior feasible solutions. • It can start at any positive primal-dual pair, feasible or infeasible, near the central ray of the positive orthant (cone), and it does not use any big M penalty parameter or lower bound. • Each iteration solves a system of linear equations whose dimension is almost the same as that solved in the standard (primal-dual) interior-point algorithms. • If the LP problem has a solution, the algorithm generates a sequence that approaches feasibility and optimality simultaneously; if the problem is infeasible or unbounded, the algorithm will correctly detect infeasibility for at least one of the primal and dual problems.
An Adjustment Process for an Economy with Linear Production Technologies
Authors: van den Elzen Antoon , van der Laan Gerard , Talman Dolf 
Published: October 2008

In this paper an adjustment process for a general equilibrium model with linear production technologies is given. The process reaches an equilibrium in the economy by simultaneous adaptations of prices and activity levels. Initially the prices of the commodities in excess demand are relatively increased and the prices of the commodities in excess supply are relatively decreased. Firms have only a positive activity level when they make zero profit. An important feature of the process is that it keeps track of the location of the starting price vector throughout its operation. Furthermore, the choice of the starting price vector is only limited by economic considerations. Besides, the process converges under rather weak conditions and possesses an appealing economic interpretation.
Lower and Upper Bounds for the Allocation Problem and Other Nonlinear Optimization Problems
Authors: Hochbaum Dorit S. 
Published: October 2008

We demonstrate the impossibility of strongly polynomial algorithms for the allocation problem, in the comparison model and in the algebraic tree computation model, that follow from lower bound results. Consequently, there are no strongly polynomial algorithms for nonlinear (concave) separable optimization over a totally unimodular constraint matrix. This is in contrast to the case when the objective is linear. We present scaling-based algorithms that use a greedy algorithm as a subroutine. The algorithms are polynomial for the allocation problem and its extensions and are also optimal for the sample allocation problem and the generalized upper bounds allocation problem, in that the complexity meets the lower bound derived from the comparison model. For other extensions of the allocation problem the scaling-based algorithms presented here are the fastest known. These algorithms are also polynomial time algorithms for solving with ε accuracy the allocation problem and its extension in continuous variables.
On the Relation Between Recurrence and Ergodicity Properties in Denumerable Markov Decision Chains
Authors: Dekker R. , Hordijk A. , Spieksma F. M. 
Published: October 2008

This paper studies two properties of the set of Markov chains induced by the deterministic policies in a Markov decision chain. These properties are called μ-uniform geometric ergodicity and μ-uniform geometric recurrence. μ-uniform ergodicity generalises a quasi-compactness condition. It can be interpreted as a strong version of stability, as it implies that the Markov chains generated by the deterministic stationary policies are uniformly stable. μ-uniform geometric recurrence can be shown to be equivalent to the simultaneous Doeblin condition, If μ is bounded. Both properties imply the existence of deterministic average and sensitive optimal policies. The second Key theorem in this paper shows the equivalence of μ-uniform geometric ergodicity and weak μ-uniform geometric recurrence under appropriate continuity conditions. In the literature numerous recurrence conditions have been used. The first Key theorem derives the relation between several of these conditions, which interestingly turn out to be equivalent in most cases.
Optimal Replacement with Semi-Markov Shock Models Using Discounted Costs
Authors: Feldman Richard M. 
Published: October 2008

Consider a system that is subject to a sequence of randomly occurring shocks; each shock causes some damage of random magnitude to the system. Any of the shocks might cause the system to fail, and the probability of such a failure is a function of the sum of the magnitudes of damage caused by all previous shocks. When the system fails, it must be immediately replaced and a failure cost is incurred. If the system is replaced before failure, a smaller replacement cost is incurred, and that cost may depend upon the state of the system at replacement time. The purpose of this paper is to determine the optimal replacement policy among the class of policies that replace at shock times. The main assumption is that the cumulative damage process is a semi-Markov process. The cost criterion is to minimize the discounted cost of replacement. (See Feldman [Feldman, R. M. 1976. Optimal replacement with semi-Markov shock models. J. Appl. Probab. 13 108–117; Feldman, R. M. 1977. The maintenance of systems governed by semi-Markov shock models. Proceedings of the Conference on the Theory and Applications of Reliability with Emphasis on Bayesian and Nonparametric Methods. Edited by C. P. Tsokos. Academic Press.] for the average cost criterion case.) The general approach will be to apply optimal stopping theory to the replacement problem.
Fast Approximation Algorithms for Fractional Packing and Covering Problems
Authors: Plotkin Serge A. , Shmoys David B. , Tardos Éva 
Published: October 2008

This paper presents fast algorithms that find approximate solutions for a general class of problems, which we call fractional packing and covering problems. The only previously known algorithms for solving these problems are based on general linear programming techniques. The techniques developed in this paper greatly outperform the general methods in many applications, and are extensions of a method previously applied to find approximate solutions to multicommodity flow problems. Our algorithm is a Lagrangian relaxation technique; an important aspect of our results is that we obtain a theoretical analysis of the running time of a Lagrangian relaxation-based algorithm. We give several applications of our algorithms. The new approach yields several orders of magnitude of improvement over the best previously known running times for algorithms for the scheduling of unrelated parallel machines in both the preemptive and the nonpreemptive models, for the job shop problem, for the Held and Karp bound for the traveling salesman problem, for the cutting-stock problem, for the network embedding problem, and for the minimum-cost multicommodity flow problem.
Coordination Complexity of Parallel Price-Directive Decomposition
Authors: Grigoriadis Michael D. , Khachiyan Leonid G. 
Published: October 2008

The general block-angular convex resource sharing problem in K blocks and M nonnegative block-separable coupling constraints is considered. Applications of this model are in combinatorial optimization, network flows, scheduling, communication networks, engineering design, and finance. This paper studies the coordination complexity of approximate price-directive decomposition (PDD) for this problem, i.e., the number of iterations required to solve the problem to a fixed relative accuracy as a function of K and M. First a simple PDD method based on the classical logarithmic potential is shown to be optimal up to a logarithmic factor in M in the class of all PDD methods that work with the original (unrestricted) blocks. It is then shown that logarithmic and exponential potentials generate a polylogarithmically-optimal algorithm for a wider class of PDD methods which can restrict the blocks by the coupling constraints. As an application, the fastest currently-known deterministic approximation algorithm for minimum-cost multicommodity flows is obtained.
On a Wide Region of Centers and Primal-Dual Interior Point Algorithms for Linear Programming
Authors: Sturm Jos F. , Zhang Shuzhong 
Published: October 2008

In the adaptive step primal-dual interior point method for linear programming, polynomial algorithms are obtained by computing Newton directions towards targets on the central path, and restricting the iterates to a neighborhood of this central path. In this paper, the adaptive step methodology is extended, by considering targets in a certain central region, which contains the usual central path, and subsequently generating iterates in a neighborhood of this region. The size of the central region can vary from the central path to the whole feasible region by choosing a certain parameter. An 𝒪(√nL) iteration bound is obtained under mild conditions on the choice of the target points. In particular, we leave plenty of room for experimentation with search directions. The practical performance of the new primal-dual interior point method is measured on part of the Netlib test set for various sizes of the central region.
α-Covex Sets and Strong Quasiconvexity
Authors: Crouzeix J. P. , Ferland J. A. , Zălinescu C. 
Published: October 2008

A major property of continuous strong convex functions is that they are inf-compact; hence, their minima are reached. In the past, several attempts have been made to extend strong convexity to generalized convexity, but they fail in the sense that they do not ensure inf-compactness. In this paper, we introduce a concept of strong convexity on sets from which we deduce new concepts of strong quasiconvexity related to inf-compactness.
Separating Maximally Violated Comb Inequalities in Planar Graphs
Authors: Fleischer L. , Tardos É. 
Published: October 2008

The Traveling Salesman Problem (TSP) is a benchmark problem in combinatorial optimization. It was one of the very first problems used for developing and testing approaches to solving large integer programs, including cutting plane algorithms and branch-and-cut algorithms. Much of the research in this area has been focused on finding new classes of facets for the TSP polytope, and much less attention has been paid to algorithms for separating from these classes of facets. In this paper, we consider the problem of finding violated comb inequalities. If there are no violated subtour constraints in a fractional solution of the TSP, a comb inequality may not be violated by more than 1. Given a fractional solution in the subtour elimination polytope whose graph is planar, we either find a violated comb inequality or determine that there are no comb inequalities violated by 1. Our algorithm runs in O(n + MC(n)) time, where MC(n) is the time to compute a cactus representation of all minimum cuts of a weighted planar graph on n vertices.
Processor Shadowing: Maximizing Expected Throughput in Fault-Tolerant Systems
Authors: Bruno J. L. , Coffman E. G. , Lagarias J. C. , Richardson T. J. , Shor P. W. 
Published: October 2008

This paper studies parallel processing as a device for increasing fault tolerance. In the first of two basic models, a single job with a given running time is to be run on a finite set of processors; each processor is subject to failure but only while running a job. If a job is running on only one processor, and that processor fails, then the job must be restarted on another processor, assuming not all processors have already failed. To avoid such losses in accrued running time when at least two processors are available, it can be decided at any time to run the job synchronously on two processors in parallel, a replication technique we call shadowing. Clearly, shadowing has its own downside: while two processors are running, the failure rate is doubled. We show how to resolve this trade-off optimally; we devise a policy that schedules shadowing in such a way as to maximize the probability that the job finishes before all processors fail. We prove that the policy is of threshold type. That is, depending on the number of processors and the duration of the job, there is an optimal time to begin shadowing; once started, shadowing continues so long as neither processor fails and the job does not complete. We also show that the thresholds are monotone in the number of processors, i.e., if more processors are initially available, then shadowing should be started sooner. In the second of our two models, we have the same set-up except that we have an unbounded number of jobs, each having the same running time, and the objective is to maximize the expected number of jobs completed before all processors fail. We show that the optimal policy is again of threshold type, but that the thresholds are, surprisingly, not monotone in the number of processors. The optimal thresholds have a curious oscillatory behavior that we study in detail. Variants of the above problems are also analyzed using the same methods; several other variants are left as interesting open problems.
Modified Wilson's Method for Nonlinear Programs with Nonunique Multipliers
Authors: Fischer Andreas 
Published: October 2008

This paper first investigates Newton-type methods for generalized equations with compact solution sets. The analysis of their local convergence behavior is based, besides other conditions, on the upper Lipschitz-continuity of the local solution set mapping of a simply perturbed generalized equation. This approach is then applied to the KKT conditions of a nonlinear program with inequality constraints and leads to a modified version of the classical Wilson method. It is shown that the distances of the iterates to the set of KKT points converge q-quadratically to zero under conditions that do not imply a unique multiplier vector. Additionally to the Mangasarian-Fromovitz Constraint Qualification and to a Second-Order Sufficiency Condition the local minimizer is required to fulfill a Constant Rank Condition (weaker than the Constant Rank Constraint Qualification one of Janin) and a so-called Weak Complementarity Condition.
Convex Operators and Supports
Authors: Brumelle S. L. 
Published: October 2008

In this paper we show that if Z is a partially ordered linear space with the property that each set with an upper bound has a least upper bound, then any convex operator F from a linear space X into Z has a support at each x ∈ X (i.e., for each x ∈ X, there exists an affine operator A such that A(x) = F(x) and A(y) ≤ F(y) for each y ∈ X). The results in this paper are actually in the context of a more general condition than convexity, called W-convexily. W-convexity is a pointwise property of an operator and is closely related to another generalization of convexity, called order-convexity, which was introduced by Ortega and Rheinboldt in 1967.
Approximation Algorithms for Certain Scheduling Problems
Authors: Ibarra Oscar H. , Kim Chul E. 
Published: October 2008

A subset of a set of tasks ℱ is to be scheduled on a single processor. Associated with each task J time μ(J) and profit p(J). The tasks have precedence constraints in that a task cannot be scheduled until all of its predecessors have been scheduled. Approximation algorithms of polynomial time complexity are presented for the following problems: MAXPROFIT problem. Given T, the available processor time, find a subset L of ℱ such that ∑L∈Lμ(J) ≤ T and ∑J∈LP(J) is maximal. MINTIME problem. Given P, the minimum profit desired, find a subset L of ℱ such that ∑J∈LP(J) ≥ p and ∑J∈Lμ(J) is minimal.