-
作者：Huang, Chien-Chung; Kavitha, Telikepalli
作者单位：Universite PSL; Ecole Normale Superieure (ENS); Tata Institute of Fundamental Research (TIFR)
摘要：Our input instance is a bipartite graph G where each vertex has a preference list ranking its neighbors in a strict order of preference. A matching M is popular if there is no matching N such that the number of vertices that prefer N to M outnumber those that prefer M to N. Each edge is associated with a utility and we consider the problem of matching vertices in a popular and utility-optimal manner. It is known that it is NP-hard to compute a max-utility popular matching. So we consider mixed...
-
作者：Buchbinder, Niv; Schwartz, Roy; Weizman, Baruch
作者单位：Tel Aviv University; Technion Israel Institute of Technology; Tel Aviv University
摘要：We consider multiway cut, a basic graph partitioning problem in which the goal is to find the minimum weight collection of edges disconnecting a given set of special vertices called terminals. Multiway cut admits a well-known simplex embedding relaxation, where rounding this embedding is equivalent to partitioning the simplex. Current best-known solutions to the problem are comprised of a mix of several different ingredients, resulting in intricate algorithms. Moreover, the best of these algor...
-
作者：Huang, Yu-Jui; Zhou, Zhou
作者单位：University of Colorado System; University of Colorado Boulder; University of Sydney
摘要：A new definition of continuous-time equilibrium controls is introduced. As opposed to the standard definition, which involves a derivative-type operation, the new definition parallels how a discrete-time equilibrium is defined and allows for unambiguous economic interpretation. The terms strong equilibria and weak equilibria are coined for controls under the new and standard definitions, respectively. When the state process is a time-homogeneous continuous-time Markov chain, a careful asymptot...
-
作者：Soto, Jose A.; Turkieltaub, Abner; Verdugo, Victor
作者单位：Centre National de la Recherche Scientifique (CNRS); CNRS - National Institute for Mathematical Sciences (INSMI); Universidad de Chile; University of British Columbia; Universidad de O'Higgins
摘要：In the ordinal matroid secretary problem (MSP), candidates do not reveal numerical weights, but the decision maker can still discern if a candidate is better than another. An algorithm alpha is probability-competitive if every element from the optimum appears with probability 1/alpha in the output. This measure is stronger than the standard utility competitiveness. Our main result is the introduction of a technique based on forbidden sets to design algorithms with strong probability-competitiv...
-
作者：Arapostathis, Ari; Hmedi, Hassan; Pang, Guodong
作者单位：University of Texas System; University of Texas Austin; Pennsylvania Commonwealth System of Higher Education (PCSHE); Pennsylvania State University; Pennsylvania State University - University Park
摘要：We study ergodic properties of Markovian multiclass many-server queues that are uniform over scheduling policies and the size of the system. The system is heavily loaded in the Halfin-Whitt regime, and the scheduling policies are work conserving and preemptive. We provide a unified approach via a Lyapunov function method that establishes Foster-Lyapunov equations for both the limiting diffusion and the prelimit diffusion-scaled queuing processes simultaneously. We first study the limiting cont...
-
作者：Lewis, Adrian S.; Wylie, Calvin
作者单位：Cornell University
摘要：Diverse optimization algorithms correctly identify, in finite time, intrinsic constraints that must be active at optimality. Analogous behavior extends beyond optimization to systems involving partly smooth operators, and in particular to variational inequalities over partly smooth sets. As in classical nonlinear programming, such active-set structure underlies the design of accelerated local algorithms of Newton type. We formalize this idea in broad generality as a simple linearization scheme...
-
作者：Peters, Hans; Roy, Souvik; Sadhukhan, Soumyarup
作者单位：Maastricht University; Indian Statistical Institute; Indian Statistical Institute Kolkata
摘要：Finitely many agents have preferences on a finite set of alternatives, single-peaked with respect to a connected graph with these alternatives as vertices. A probabilistic rule assigns to each preference profile a probability distribution over the alternatives. First, all unanimous and strategy-proof probabilistic rules are characterized when the graph is a tree. These rules are uniquely determined by their outcomes at those preference profiles at which all peaks are on leaves of the tree and,...
