-
作者：Dupuis, Paul; Leder, Kevin; Wang, Hui
作者单位：Brown University; Columbia University
摘要：This paper considers buffer over flow probabilities for stable queueing systems with one server and different classes of arrivals. The service priority is given to the class of customers whose current weighted queue size is the largest (weighted-serve-the-longest-queue policy). We explicitly identify the exponential decay rate for the rare-event probabilities of interest and construct asymptotically optimal importance-sampling schemes for simulation.
-
作者：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...
-
作者：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.
-
作者：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...
-
作者：Penn, Michal; Polukarov, Maria; Tennenholtz, Moshe
作者单位：Technion Israel Institute of Technology; University of Southampton; Microsoft; MICROSOFT ISRAEL
摘要：We introduce a new class of games called random order congestion games (ROCGs). In an ROCG, each player has a task that can be carried out by any element of a set of resources, and each resource executes its assigned tasks in a random order. The aim of each player is to minimize his expected cost, which is the sum of the fixed costs over the set of his utilized resources and the expected cost of his task execution. The cost of a player's task execution is determined by the earliest time his ta...
-
作者：Aliev, Iskander; Henk, Martin
作者单位：Cardiff University; Cardiff University; Otto von Guericke University
摘要：The largest integer that cannot be represented as a nonnegative integral combination of given set of positive integers is called the Frobenius number of these integers. We show that the asymptotic growth of the Frobenius number on average is significantly slower than the growth of the maximum Frobenius number.
-
作者：Teper, Roee
作者单位：Tel Aviv University
摘要：Information consisting of probabilities of some (but possibly not all) events induces an integral with respect to a probability specified on a subalgebra. A decision maker evaluates the alternatives using only the available information and completely ignoring unavailable information. Assume now that the decision maker assesses the worth of a different lottery at each point in a discrete time. Assume also that each such lottery is preferred to some fixed alternative lottery. Now, consider the s...
