-
作者：Litvak, Nelly; Ejov, Vladimir
作者单位：University of Twente; University of South Australia
摘要：We consider the Hamiltonian cycle problem (HCP) embedded in a controlled Markov decision process. In this setting, HCP reduces to an optimization problem on a set of Markov chains corresponding to a given graph. We prove that Hamiltonian cycles are minimizers for the trace of the fundamental matrix on a set of all stochastic transition matrices. In case of doubly stochastic matrices with symmetric linear perturbation, we show that Hamiltonian cycles minimize a diagonal element of a fundamental...
-
作者：Yu, Jia Yuan; Mannor, Shie; Shimkin, Nahum
作者单位：McGill University; Technion Israel Institute of Technology
摘要：We consider a learning problem where the decision maker interacts with a standard Markov decision process, with the exception that the reward functions vary arbitrarily over time. We show that, against every possible realization of the reward process, the agent can perform as well-in hindsight-as every stationary policy. This generalizes the classical no-regret result for repeated games. Specifically, we present an efficient online algorithm-in the spirit of reinforcement learning-that ensures...
-
作者：Guo, Xin; Jarrow, Robert A.; Zeng, Yan
作者单位：University of California System; University of California Berkeley; Cornell University
摘要：Incomplete information is at the heart of information-based credit risk models. In this paper, we rigorously define incomplete information with the notion of delayed filtrations. We characterize two distinct types of delayed information, continuous and discrete: the first generated by a time change of filtrations and the second by finitely many marked point processes. This notion unifies the noisy information in Duffie and Lando [Duffie, D., D. Lando. 2001. Term structures and credit spreads w...
-
作者：Nagarajan, Viswanath; Sviridenko, Maxim
作者单位：International Business Machines (IBM); IBM USA
摘要：Quadratic assignment is a basic problem in combinatorial optimization that generalizes several other problems such as traveling salesman, linear arrangement, dense k subgraph, and clustering with given sizes. The input to the quadratic assignment problem consists of two n x n symmetric nonnegative matrices W = (w(i,j)) and D = (d(i,j)). Given matrices W, D, and a permutation pi: [n] -> [n], the objective function is Q(pi) := Sigma(i,j is an element of[n], i not equal j) w(i,j) . d(pi(i), pi(j)...
-
作者：Faenza, Yuri; Kaibel, Volker
作者单位：University of Rome Tor Vergata; Otto von Guericke University
摘要：We give compact extended formulations for the packing and partitioning orbitopes (with respect to the full symmetric group) described and analyzed in Kaibel and Pfetsch [Kaibel, V., M. E. Pfetsch. 2008. Packing and partitioning orbitopes. Math. Programming, Ser. A 114(1) 1-36]. These polytopes are the convex hulls of all 0/1-matrices with lexicographically sorted columns and at most, respectively, exactly one 1-entry per row. They are important objects for symmetry reduction in certain integer...
-
作者：Borozan, Valentin; Cornuejols, Gerard
作者单位：Aix-Marseille Universite; Carnegie Mellon University
摘要：In this paper, we consider a semi-infinite relaxation of mixed-integer linear programs. We show that minimal valid inequalities for this relaxation correspond to maximal lattice-free convex sets, and that they arise from nonnegative, piecewise linear, positively homogeneous, convex functions.
-
作者：Grechuk, Bogdan; Molyboha, Anton; Zabarankin, Michael
作者单位：Stevens Institute of Technology
摘要：An approach to the Shannon and Renyi entropy maximization problems with constraints on the mean and law-invariant deviation measure for a random variable has been developed. The approach is based on the representation of law-invariant deviation measures through corresponding convex compact sets of nonnegative concave functions. A solution to the problem has been shown to have an alpha-concave distribution (log-concave for Shannon entropy), for which in the case of comonotone deviation measures...
-
作者：Belloni, Alexandre; Freund, Robert M.; Vempala, Santosh
作者单位：Duke University; Massachusetts Institute of Technology (MIT); University System of Georgia; Georgia Institute of Technology
摘要：The classical perceptron algorithm is an elementary row-action/relaxation algorithm for solving a homogeneous linear inequality system Ax > 0. A natural condition measure associated with this algorithm is the Euclidean width tau of the cone of feasible solutions, and the iteration complexity of the perceptron algorithm is bounded by 1/tau(2) [see Rosenblatt, F. 1962. Principles of Neurodynamics. Spartan Books, Washington, DC]. Dunagan and Vempala [Dunagan, J., S. Vempala. 2007. A simple polyno...
-
作者：Fujishige, Satoru; Nagano, Kiyohito
作者单位：Kyoto University; Institute of Science Tokyo; Tokyo Institute of Technology
摘要：A linearly parameterized polymatroid intersection problem appears in the context of principal partitions. We consider a submodular intersection problem on a pair of strong-map sequences of submodular functions, which is an extension of the linearly parameterized polymatroid intersection problem to a nonlinearly parameterized one. We introduce the concept of a basis frame on a finite nonempty set of cardinality n that gives a mapping from the set of all base polyhedra in n-dimensional space int...
-
作者：van Zuylen, Anke; Williamson, David P.
作者单位：Tsinghua University; Cornell University
摘要：We consider ranking and clustering problems related to the aggregation of inconsistent information, in particular, rank aggregation, (weighted) feedback arc set in tournaments, consensus and correlation clustering, and hierarchical clustering. Ailon et al. [Ailon, N., M. Charikar, A. Newman. 2005. Aggregating inconsistent information: Ranking and clustering. Proc. 37th Annual ACM Sympos. Theory Comput. (STOC '05), 684-693], Ailon and Charikar [Ailon, N., M. Charikar. 2005. Fitting tree metrics...
