bluuebunny/crossref_metadata_2025_split huggingface dataset:
Constrained Markov Decision Models with Weighted Discounted Rewards
Authors: Feinberg Eugene A. , Shwartz Adam 
Published: October 2008

This paper deals with constrained optimization of Markov Decision Processes. Both objective function and constraints are sums of standard discounted rewards, but each with a different discount factor Such models arise, e.g., in production and in applications involving multiple time scales. We prove that it a feasible policy exists, then there exists an optimal policy which is (i) stationary (nonrandomized) from some step onward, (ii) randomized, Markov before this step, but the total number of actions which are added by randomization is bounded by the number of constraints. Optimality of such policies for multi-criteria problems is also established. These new policies have the pleasing aesthetic property that the amount of randomization they require over any trajectory is restricted by the number of constraints. This result is new even for constrained optimization with a single discount factor, where the optimality of randomized stationary policies is known. However, a randomized stationary policy may require an infinite number of randomizations over time. We also formulate a linear programming algorithm for approximate solutions of con-strained weighted discounted models.
Asymptotic Convergence Analysis of the Forward-Backward Splitting Algorithm
Authors: Zhu Ciyou 
Published: October 2008

The asymptotic convergence of the forward-backward splitting algorithm for solving equations of type 0 ∈ T(z) is analyzed, where T is a multivalued maximal monotone operator in the n-dimensional Euclidean space. When the problem has a nonempty solution set, and T is split in the form T = ℱ + h with ℱ being maximal monotone and h being co-coercive with modulus greater than ½, convergence rates are shown, under mild conditions, to be linear, superlinear or sublinear depending on how rapidly ℱ−1 and h−1 grow in the neighborhoods of certain specific points. As a special case, when both ℱ and h are polyhedral functions, we get R-linear convergence and 2-step Q-linear convergence without any further assumptions on the strict monotonicity on T or on the uniqueness of the solution. As another special case when h = 0, the splitting algorithm reduces to the proximal point algorithm, and we get new results, which complement R. T. Rockafellar's and F. J. Luque's earlier results on the proximal point algorithm.
Overtaking and Almost-Sure Optimality for Infinite Horizon Markov Decision Processes
Authors: Leizarowitz Arie 
Published: October 2008

We consider infinite horizon optimal control of Markov chains on complete metric spaces. We employ the overtaking optimality criterion, which is either applied to the expected cost-flow, or to the individual sample paths, yielding almost-sure optimality results. We use the existence of a solution pair (Φ(·), λ) to the optimality equation ℒΦ(x) = λ to establish and characterize optimal strategies. For finite state-spaces we derive sufficient, as well as necessary conditions for overtaking optimality.
The Circuit Polytope: Facets
Authors: Bauer Petra 
Published: October 2008

Given an undirected graph G = (V, E) and a cost vector c ∈ ℝE, the weighted girth problem is to find a circuit in G having minimum total cost. This problem is in general 𝒩𝒫-hard. A promising approach to the solution of hard combinatorial optimization problems is given by the so-called cutting plane methods. These involve linear programming techniques based on a partial description of the convex hull of the incidence vectors of possible solutions. We consider the weighted girth problem in the case where G is the complete graph Kn and study the facial structure of the circuit polytope PCn and some related polyhedra. In the appendix we give complete characterizations of PCn for n up to 6. We were motivated to study the weighted girth problem by the fact that this problem and variations of it appear as a subproblem, namely the pricing problem, in a column generation approach to the vehicle routing problem.
Scaling Methods for Finding a Maximum Free Multiflow of Minimum Cost
Authors: Goldberg Andrew V. , Karzanov Alexander V. 
Published: October 2008

Suppose we are given an undirected graph with nonnegative integer-valued edge capacities and costs in which a subset of nodes is specified. We consider the problem of finding a collection of flows between arbitrary pairs of specified nodes such that the capacity constraints are satisfied and the sum of costs of flows is minimum, provided that the sum of values of flows is maximum. It is known that this problem has a half-integer optimal solution and such a solution can be found in strongly polynomial time using the ellipsoid method. In this paper we give two “purely combinatorial” polynomial algorithms for finding a half-integer optimal solution. These are based on capacity and cost scaling techniques and use the double covering method earlier worked out for the problem.
Simpson Points in Planar Problems with Locational Constraints. The Round-Norm Case
Authors: Carrizosa Emilio , Conde Eduardo , Muñoz-Márquez Manuel , Puerto Justo 
Published: October 2008

The Simpson set is one of the most popular solution concepts in location models with voting. In this paper we address the problem of finding such a set for planar models with locational constraints when the metric in use is induced by a round norm. After formulating the problem as a mathematical program, we first propose a general algorithm that enables the evaluation of the corresponding objective function. Then, we show how to solve the problem by proving the existence of a finite dominating set of locations, the best of which can be found by inspection (using the evaluation algorithm proposed).
Simpson Points in Planar Problems with Locational Constraints. The Polyhedral-Gauge Case
Authors: Carrizosa Emilio , Conde Eduardo , Muñoz-Márquez Manuel , Puerto Justo 
Published: October 2008

In this paper we address the problem of finding Simpson points in planar models with locational constraints when distances are measured by polyhedral gauges. Making use of the results we have stated in a previous paper, we show here the existence of a finite set of points in the plane, independent of the weights associated with the users, that contains at least a Simpson point. Connection between Simpson points (as a result of a voting process) and Weber points (as the outcome of a planning process) are explored. It is shown by means of an example that the existing relations for the unconstrained case are no longer true when locational constraints are imposed. In order to reconcile both voting and planning processes, a biobjective problem is described, for which we construct a finite dominating set.
Nearly Optimal Competitive Online Replacement Policies
Authors: El-Yaniv Ran , Karp Richard M. 
Published: October 2008

This paper studies the online replacement problem. In this problem an online player is engaged at each time in one activity. Associated with each activity are a changeover cost and flow rate. While involved in an activity the player's budget is depleted at the activity's flow rate. The player can switch to a new activity whenever it is offered but he pays a changeover cost. The player's goal is to decide when to switch activities so that his total cost is minimized. Typical applications are: equipment, jobs and supplier replacement, mortgage refinancing, etc. With respect to the competitive ratio performance measure, this paper seeks to determine the best possible competitive ratio achievable by an online replacement policy. Our results include the following: a general lower bound on the performance of any deterministic policy, a policy that is optimal in several special cases and a simple policy that is approximately optimal.
An Operational Calculus for Matrix-Exponential Distributions, with Applications to a Brownian (q, Q) Inventory Model
Authors: Asmussen Søren , Perry David 
Published: October 2008

A distribution G on (0, ∞) is called matrix-exponential if the density has the form αeTz s where α is a row vector, T a square matrix and s a column vector. Equivalently, the Laplace transform is rational. For such distributions, we develop an operator calculus, where the key step is manipulation of analytic functions f(z) extended to matrix arguments. The technique is illustrated via an inventory model moving according to a reflected Brownian motion with negative drift, such that an order of size Q is placed when the stock process down-crosses some level q. Explicit formulas for the stationary density are found under the assumption that the leadtime Z has a matrix-exponential distribution, and involve expressions of the form f(T) where f(z) = √1 − 2z.
Finitely Repeated Games with Finite Automata
Authors: Neyman Abraham 
Published: October 2008

In honor of R. J. Aumann's 65th birthday The paper studies the implications of bounding the complexity of the strategies players may select, on the set of equilibrium payoffs in repeated games. The complexity of a strategy is measured by the size of the minimal automation that can implement it. A finite automation has a finite number of states and an initial state. It prescribes the action to be taken as a function of the current state and a transition function changing the state of the automaton as a function of its current state and the present actions of the other players. The size of an automaton is its number of states. The main results imply in particular that in two person repeated games, the set of equilibrium payoffs of a sequence of such games, G(n), n = 1, 2, …, converges as n goes to infinity to the individual rational and feasible payoffs of the one shot game, whenever the bound on one of the two automata sizes is polynomial or subexponential in n and both, the length of the game and the bounds of the automata sizes are at least n. A special case of such result justifies cooperation in the finitely repeated prisoner's dilemma, without departure from strict utility maximization or complete information, but under the assumption that there are bounds (possibly very large) to the complexity of the strategies that the players may use.
The Travelling Salesman and the PQ-Tree
Authors: Burkard Rainer E. , Deĭneko Vladimir G. , Woeginger Gerhard J. 
Published: October 2008

Let D = (dij ) be the n × n distance matrix of a set of n cities {1, 2, …, n}, and let T be a PQ-tree with node degree bounded by d that represents a set Π(T) of permutations over {1, 2, …, n}. We show how to compute for D in O(2 dn 3) time the shortest travelling salesman tour contained in Π(T). Our algorithm may be interpreted as a common generalization of the well-known Held and Karp dynamic programming algorithm for the TSP and of the dynamic programming algorithm for finding the shortest pyramidal TSP tour. A consequence of our result is that the shortcutting phase of the “twice around the tree” heuristic for the Euclidean TSP can be optimally implemented in polynomial time. This contradicts a statement of Papadimitriou and Vazirani as published in 1984.
Locating an Undesirable Facility by Generalized Cutting Planes
Authors: Carrizosa Emilio , Plastria Frank 
Published: October 2008

We address the problem of locating an undesirable facility within a compact set by minimizing a strictly decreasing boundedly lower subdifferentiable function of the squared Euclidean distances to a set of fixed points. Using (generalized) cutting planes, the resolution of this problem is reduced to solving a sequence of maxmin problems. These maxmin problems have a clear geometrical interpretation, which enables to solve them sequentially by means of an on-line enumeration of the vertices of polyhedra in higher dimensions.
Stochastic Convexity on General Space
Authors: Meester Ludolf E. , Shanthikumar J. George 
Published: October 2008

This paper presents a general theory of stochastic convexity. The notions of stochastic convexity formulated by Shaked and Shanthikumar (1988a, 1988b, 1990) are defined for general partially ordered spaces. All of the closure properties of the one-dimensional real theory are proved to be true in this general framework as well and results concerning the temporal convexity of Markov chains are sharpened. Many proofs are based on new ideas, some of which also provide insightful alternatives for proofs in Shaked and Shanthikumar (1990). The general theory encompasses the (largely one-dimensional) stochastic convexity theory as known from these papers, and at the same time permits treatment of multivariate multiparameter families as well as more general random objects. Among others, it applies to real vector spaces and yields a theory of stochastic convexity for random vectors and stochastic processes. We illustrate this new scope with examples and applications from queueing theory, coverage processes, reliability and branching processes. We show that the virtual waiting time process of an NHPP driven ·/G/1 queue is stochastically convex in the arrival intensity function, which explains the known adverse effect of fluctuating arrival rates; that the expected size of an i.i.d. union of random sets grows concavely; that the expected utility of repairable items under imperfect repair policies is increasing and convex in the probabilities of successful repair.
Optimal Allocations of Continuous Resources to Several Activities with a Concave Return Function—Some Theoretical Results
Authors: Einbu J. M. 
Published: October 2008

The problem of allocating J continuous resources to K competing activities each with a concave return function is considered. The following results pertaining to the space of optimal solution to this problem are proved: —under the most unrestricted conditions an optimal solution is almost always unique; —there exists at least one optimal solution with J + K − 1 or less allocations; —there exists at least one optimal solution for which the number of activities having multiple allocations is at most J − 1; Also, sufficient input conditions for a unique optimal solution are established and it is shown how the dimension and extent of the optimal solution space can be derived directly from the output matrix.
Best Algorithms for Approximating the Maximum of a Submodular Set Function
Authors: Nemhauser G. L. , Wolsey L. A. 
Published: October 2008

A real-valued function z whose domain is all of the subsets of N = {1, …, n) is said to be submodular if z(S) + z(T) ≥ z(S ∪ T) + z(S ∩ T), ∀S, T ⊆ N, and nondecreasing if z(S) ≤ z(T), ∀S ⊂ T ⊆ N. We consider the problem maxS⊂N {z(S): |S| ≤ K, z submodular and nondecreasing, z(Ø) = 0}. Many combinatorial optimization problems can be posed in this framework. For example, a well-known location problem and the maximization of certain boolean polynomials are in this class. We present a family of algorithms that involve the partial enumeration of all sets of cardinality q and then a greedy selection of the remaining elements, q = 0, …, K − 1. For fixed K, the qth member of this family requires O(nq+1) computations and is guaranteed to achieve at least [Formula: see text] Our main result is that this is the best performance guarantee that can be obtained by any algorithm whose number of computations does not exceed O(nq+1).
The Functional Equations of Undiscounted Markov Renewal Programming
Authors: Schweitzer P. J. , Federgruen A. 
Published: October 2008

This paper investigates the solutions to the functional equations that arise inter alia in Undiscounted Markov Renewal Programming. We show that the solution set is a connected, though possibily nonconvex set whose members are unique up to n* constants, characterize n* and show that some of these n* degrees of freedom are locally rather than globally independent. Our results generalize those obtained in Romanovsky (Romanovsky, I. 1973. On the solvability of Bellman's functional equation for a Markovian decision process. J. Math. Anal. Appl. 42 485–498.) where another approach is followed for a special class of discrete time Markov Decision Processes. Basically our methods involve the set of randomized policies. We first study the sets of pure and randomized maximal-gain policies, as well as the set of states that are recurrent under some maximal-gain policy.
Determining All Solutions to Certain Systems of Nonlinear Equations
Authors: Garcia C. B. , Zangwill W. I. 
Published: October 2008

Only during the past decade has it been discovered how, under fairly reasonable conditions, to calculate a solution of a system of n nonlinear equations in n variables. The technique utilized was the so-called “complementarity” or “fixed point” approach to the Brouwer fixed point theorem. In this paper we extend that approach to calculate for certain systems not just one but all possible solutions. All solutions can be calculated when the equations of the system behave like a polynomial in the highest order terms. That is, in each equation the highest order term must be a variable raised to a power while the lower order terms can be more general. Our procedure starts with a trivial system of equations, one to which all solutions are obvious and immedately known. The trivial system is then deformed into the system given with the unknown solutions. The idea is to follow the paths generated from the obvious solutions into the unknown solutions of the given system. This process under rather general conditions calculates all of the solutions.
Quotatone Apportionment Methods
Authors: Balinski M. L. , Young H. P. 
Published: October 2008

The problem of apportionment is that of allocating an integer number of seats “proportionally” among a set of states or regions as a fraction of their populations. An apportionment method satisfies quota if it accords to each state the exactly proportional (rational) number of seats due it rounded up or rounded down. A method is house monotone if no state’s allocation goes down when the total number of seats to be distributed goes up. This paper gives a simple characterization of all house monotone methods satisfying quota. Further, a manner of exposition is formulated which unites several key house monotone apportionment methods, thus showing clearly their connections.
Matroids and a Reliability Analysis Problem
Authors: Ball Michael O. , Nemhauser George L. 
Published: October 2008

We present an algorithm for the reliability analysis problem of determining the probability that a stochastic binary system operates. The stochastic binary system is viewed as an independence system. The algorithm finds a partition of the set of independence sets into subsets called intervals. If F ⊆ G, the interval between F and G is the collection of subsets F with F ⊆ F′ ⊆ G. The probability of an event corresponding to an interval is easy to calculate and the probability that the system operates is simply the sum of the event probabilities corresponding to the intervals in the partition. For any independence system a lower bound on the number of intervals needed in a partition is the number of bases. We show that for matroids this bound can be attained. Our algorithm finds a minimum cardinality interval partition of a matroid and characterizes matroids.
Sequencing with Series-Parallel Precedence Constraints
Authors: Monma Clyde L. , Sidney Jeffrey B. 
Published: October 2008

One of the most important ideas in the theory of sequencing and scheduling is the method of adjacent pairwise job interchange. This method compares the costs of two sequences which differ only by interchanging a pair of adjacent jobs. In 1956, W. E. Smith defined a class of problems for which a total preference ordering of the jobs exists with the property that in any sequence, whenever two adjacent jobs are not in preference order, they may be interchanged with no resultant cost increase. In such a case the unconstrained sequencing problem is easily solved by sequencing the jobs in preference order. In this paper, a natural subclass of these problems is considered for which such a total preference ordering exists for all subsequences of jobs. The main result is an efficient general algorithm for these sequencing problems with series-parallel precedence constraints. These problems include the least cost fault detection problem, the one-machine total weighted completion time problem, the two-machine maximum completion time flow-shop problem and the maximum cumulative cost problem.
Minimal Forbidden Subgraphs of Unimodular Multicommodity Networks
Authors: Truemper K. , Soun Y. 
Published: October 2008

An integral matrix with independent columns is called unimodular if the greatest common divisor of the determinants of its maximum-rank square submatrices is one. An integral matrix A (not necessarily having independent columns) is defined to be unimodular if every basis of A has that property. It is known that this is so if and only if the extreme points of the set of nonnegative vectors x satisfying Ax = b are integral for all integral vectors b. Here the constraint matrix of a k-commodity network flow problem is shown to be unimodular if and only if the associated (undirected) graph does not have a subgraph homeomorphic to the following graphs: (i) the complete graph on four nodes, and if k ≥ 3, (ii) a cycle with three additional edges, each a duplicate of a different edge of the cycle, having no node with degree 2 (these graphs have from three to six nodes). The following algorithm checks whether subgraphs of the above type are present. First find the 2-connected subgraphs that contain at least two edges. Then reduce each such subgraph to a graph with fewer nodes and arcs. The forbidden subgraphs are not present if and only if the algorithm reduces each 2-connected subgraph to a cycle with two edges. When this is not possible, a forbidden subgraph is produced. Suitable implementation of the algorithm results in O(n) complexity, where n is the number of edges of the original graph.
Almost Sure Comparisons of Renewal Processes and Poisson Processes, with Application to Reliability Theory
Authors: Miller Douglas R. 
Published: October 2008

If the interarrival times of a renewal process {Si, i = 0, 1, 2…} have a failure rate function which is bounded away from 0 and ∞, then it is possible to construct (nonhomogeneous) Poisson processes {Ti0, i = 0, 1, 2, …} and {Ti1, i = 0, 1, 2, …} on the same probability space with {Si, i = 0, 1, 2, …} such that {T00, T10, T20, …} ⊂ {S0, S1, S2, …} ⊂ {T01, T11, T21, …} almost surely. This has applications to the reliability theory of maintained systems. If the components of a maintained coherent system have exponential lifetimes and NWU repair times, then an initially perfect system will have a NBU distribution of time until first system failure. Furthermore, transient availability is greater than steady-state availability.
Competitive Optimality of Logarithmic Investment
Authors: Bell Robert M. , Cover Thomas M. 
Published: October 2008

Consider the two-person zero-sum game in which two investors are each allowed to invest in a market with stocks (X1, X2, …, Xm) ∼ F, where Xi ≥ 0. Each investor has one unit of capital. The goal is to achieve more money than one’s opponent. Allowable portfolio strategies are random investment policies B ∈ Rm, B ≥ 0, E ∑ mi = 1Bi = 1. The payoff to player 1 for policy B1 vs. B2 is P {Bt1 X ≥ Bt2 X}. The optimal policy is shown to be B* = Ub*, where U is a random variable uniformly distributed on [0, 2], and b* maximizes E ln bt X over b ≥ 0, ∑ bi = 1. Curiously, this competitively optimal investment policy b* is the same policy that achieves the maximum possible growth rate of capital in repeated independent investments (Breiman [Breiman, L. 1961. Optimal gambling systems for favorable games. Fourth Berkeley Symposium. 1 65–78.] and Kelly [Kelly, J. 1956. A new interpretation of information rate. Bell System Tech. J. 917–926.]). Thus the immediate goal of outperforming another investor is perfectly compatible with maximizing the asymptotic rate of return.