-
作者：Cai, MC; Deng, XT; Zang, WN
作者单位：Chinese Academy of Sciences; Academy of Mathematics & System Sciences, CAS; City University of Hong Kong; University of Hong Kong
摘要：We establish a necessary and sufficient condition for the linear system {x : Hx greater than or equal to e, x greater than or equal to 0} associated with a bipartite tournament to be totally dual integral, where H is the cycle-vertex incidence matrix and e is the all-one vector. The consequence is a min-max relation on packing and covering cycles, together with strongly polynomial time algorithms for the feedback vertex set problem and the cycle packing problem on the corresponding bipartite t...
-
作者：Frank, A; Shepherd, B; Tandon, V; Végh, Z
作者单位：Eotvos Lorand University; AT&T; Alcatel-Lucent; Lucent Technologies
摘要：We consider the node-capacitated routing problem in an undirected ring network along with its fractional relaxation, the node-capacitated multicommodity flow problem. For the feasibility problem, Farkas' lemma provides a characterization for general undirected graphs, asserting roughly that there exists such a flow if and only if the so-called distance inequality holds for every choice of distance functions arising from nonnegative node weights. For rings, this (straightforward) result will be...
-
作者：Gamarnik, D
作者单位：International Business Machines (IBM); IBM USA
摘要：We investigate stability of scheduling policies in queueing systems. To this day no algorithmic characterization exists for checking stability of a given policy in a given queueing system, In this paper we introduce a certain generalized priority, policy and prove that the stability of this policy is algorithmically undecidable. We also prove that stability of a homogeneous random walk in F-+(d) is undecidable. Finally, we show that the problem of computing a fluid limit of a queueing system o...
-
作者：Borkar, VS
作者单位：Tata Institute of Fundamental Research (TIFR)
摘要：We propose for risk-sensitive control of finite Markov chains a counterpart of the popular Q-learning algorithm for classical Markov decision processes. The algorithm is shown to converge with probability one to the desired solution. The proof technique is an adaptation of the o.d.e. approach for the analysis of stochastic approximation algorithms, with most of die work involved used for the analysis of the specific o.d.e.s. that arise.
