-
作者：Fleischer, Lisa K.; Letchford, Adam N.; Lodi, Andrea
作者单位：Dartmouth College; Lancaster University; University of Bologna
摘要：The comb inequalities are a well-known class of facet-inducing inequalities for the traveling salesman problem, defined in terms of certain vertex sets called the handle and the teeth. We say that a comb inequality is simple if the following holds for each tooth: Either the intersection of the tooth with the handle has cardinality one, or the part of the tooth outside the handle has cardinality one, or both. The simple comb inequalities generalize the classical 2-matching inequalities of Edmon...
-
作者：Lehrer, Ehud; Solan, Eflon
作者单位：Tel Aviv University
摘要：We study the notion of excludability in repeated games with vector payoffs, when one of the players is restricted to strategies with bounded computational capacity. We show that a closed set is excludable by Player 2 when Player 1 is restricted to using only bounded-recall strategies if and only if it does not contain a convex approachable set. We provide partial results when Player 1 is restricted to using strategies that can be implemented by automata.
-
作者：Chen, Xujin; Ding, Guoli; Hu, Xiaodong; Zang, Wenan
作者单位：Chinese Academy of Sciences; Louisiana State University System; Louisiana State University; University of Hong Kong
摘要：Let G be a graph with a nonnegative integral function w defined on V(G). A collection T of subsets of V(G) (repetition is allowed) is called a feedback vertex set packing in G if the removal of any member of 3 from G leaves a forest, and every vertex v is an element of V(G) is contained in at most w(v) members of F. The weight of a cycle C in G is the sum of w(v), over all vertices v of C. The purpose of this paper is to characterize all graphs with the property that, for any nonnegative integ...
-
作者：Renault, Jerome
作者单位：Universite PSL; Universite Paris-Dauphine
摘要：We consider a two-player zero-sum game, given by a Markov chain over a finite set of states and a family of matrix games indexed by states. The sequence of states follows the Markov chain. At the beginning of each stage, only Player I is informed of the current state, then the corresponding matrix game is played, and the actions chosen are observed by both players before proceeding to the next stage. We call such a game a Markov chain game with lack of information on one side. This model gener...
-
作者：Bietenhader, Thomas; Okamoto, Yoshio
作者单位：Swiss Federal Institutes of Technology Domain; ETH Zurich; Toyohashi University of Technology
摘要：In cooperative game theory, a characterization of games with stable cores is known as one of the most notorious open problems. We study this problem for a special case of the minimum coloring games, introduced by Deng et al. [10], which arise from a cost allocation problem when the players are involved in conflict. In this paper, we show that the minimum coloring game on a perfect graph has a stable core if and only if every vertex of the graph belongs to a maximum clique. We also consider the...
-
作者：Ruszczynski, Andrzej; Shapiro, Alexander
作者单位：Rutgers University System; Rutgers University New Brunswick; University System of Georgia; Georgia Institute of Technology
摘要：We introduce an axiomatic definition of a conditional convex risk mapping and we derive its properties. In particular, we prove a representation theorem for conditional risk mappings in terms of conditional expectations. We also develop dynamic programming relations for multistage optimization problems involving conditional risk mappings.
-
作者：Canovas, Maria J.; Lopez, Marco A.; Parra, Juan; Toledo, F. Javier
作者单位：Universidad Miguel Hernandez de Elche; Universitat d'Alacant
摘要：We consider the parametric space of all the linear semi-infinite programming problems with constraint systems having the same index set. Under a certain regularity condition, the so-called well-posedness with respect to the solvability, it is known from Canovas et a]. [2] that the optimal value function is Lipschitz continuous around the nominal problem pi. In this paper we obtain an explicit Lipschitz constant for such a function in a certain neighborhood of pi. We emphasize the fact that bot...
-
作者：Ruszczynski, Andrzej; Shapiro, Alexander
作者单位：Rutgers University System; Rutgers University New Brunswick; University System of Georgia; Georgia Institute of Technology
摘要：We consider optimization problems involving convex risk functions. By employing techniques of convex analysis and optimization theory in vector spaces of measurable functions, we develop new representation theorems for risk models, and optimality and duality theory for problems with convex risk functions.
-
作者：De Loera, JA; Hemmecke, R; Köppe, M; Weismantel, R
作者单位：University of California System; University of California Davis; Otto von Guericke University
摘要：We classify according to their computational complexity, integer optimization problems whose constraints and objective functions e polynomials with integer coefficients, and the number of variables is fixed. For the optimization of an integer polynomial over the lattice points of a convex polytope, we show an algorithm to compute lower and upper bounds for the optimal value. For polynomials that are nonnegative over the polytope, these sequences of bounds lead to a fully polynomial-time approx...
-
作者：Perry, D; Stadje, W; Zacks, S
作者单位：University of Haifa; University Osnabruck; State University of New York (SUNY) System; Binghamton University, SUNY
摘要：A production/inventory system is filled continuously at rate I and satisfies demands of i.i.d. random sizes that arrive at Poisson times. For this system we consider two clearing policies. Under sporadic review, clearing takes place after a random time independent of the content process. Under continuous review, the system is cleared as soon as the inventory level reaches some pre-specified threshold. We derive explicit results for the associated expected discounted cost functionals under both...
