-
作者：Tang, Tianyun; Toh, Kim-Chuan
作者单位：National University of Singapore; National University of Singapore
摘要：In this paper, we study linearly constrained optimization problems (LCP). After applying Hadamard parametrization, the feasible set of the parametrized problem (LCPH) becomes an algebraic variety, with conducive geometric properties which we explore in depth. We derive explicit formulas for the tangent cones and second-order tangent sets associated with the parametrized polyhedra. Based on these formulas, we develop a procedure to recover the Lagrangian multipliers associated with the constrai...
-
作者：Dey, Santanu S.; Dubey, Yatharth; Molinaro, Marco; Shah, Prachi
作者单位：University System of Georgia; Georgia Institute of Technology; Pontificia Universidade Catolica do Rio de Janeiro; Pontificia Universidade Catolica do Rio de Janeiro
摘要：Full strong-branching (henceforth referred to as strong-branching) is a well-known variable selection rule that is known experimentally to produce significantly smaller branch-and-bound trees in comparison to all other known variable selection rules. In this paper, we attempt an analysis of the performance of the strong-branching rule both from a theoretical and a computational perspective. On the positive side for strong-branching, we identify vertex cover as a class of instances where this r...
-
作者：Reitzig, Raphael; Wild, Sebastian
作者单位：University of Liverpool
摘要：Proportional apportionment is the problem of assigning seats to states (resp. parties) according to their relative share of the population (resp. votes), a field heavily influenced by the early work of Michel Balinski, not least his influential 1982 book with Peyton Young (Fair representation, 2nd edn. Brookings Institution Press, Washington, D.C., 2001). In this article, we consider the computational cost of divisor methods (also known as highest averages methods), the de-facto standard solut...
-
作者：Palomares, Antonio; Pukelsheim, Friedrich; Ramirez, Victoriano
作者单位：University of Granada; University of Augsburg
摘要：Apportionment methods are used in proportional representation systems for the apportionment of parliamentary seats among political parties proportionately to their vote counts, or for the allocation of parliamentary seats between geographical districts proportionately to their population figures. From an axiomatic viewpoint apportionment methods ought to satisfy six basic principles: anonymity, balancedness, concordance, decency, exactness, and fairness. It is well-known that the first two pri...
-
作者：Zheng, Da Wei; Henzinger, Monika
作者单位：University of Illinois System; University of Illinois Urbana-Champaign; Institute of Science & Technology - Austria
摘要：We present an auction algorithm using multiplicative instead of constant weight updates to compute a (1-epsilon)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(1-\varepsilon )$$\end{document}-approximate maximum weight matching (MWM) in a bipartite graph with n vertices and m edges in time O(m epsilon-1)\documentc...
-
作者：Fotakis, Dimitris; Matuschke, Jannik; Papadigenopoulos, Orestis
作者单位：National Technical University of Athens; KU Leuven; Columbia University
摘要：In generalized malleable scheduling, jobs can be allocated and processed simultaneously on multiple machines so as to reduce the overall makespan of the schedule. The required processing time for each job is determined by the joint processing speed of the allocated machines. We study the case that processing speeds are job-dependent M-#-concave functions and provide a constant-factor approximation for this setting, significantly expanding the realm of functions for which such an approximation ...
-
作者：Jennings, Andrew B.; Laraki, Rida; Puppe, Clemens; Varloot, Estelle M.
作者单位：University of Liverpool; Centre National de la Recherche Scientifique (CNRS); Universite PSL; Universite Paris-Dauphine; Helmholtz Association; Karlsruhe Institute of Technology; HSE University (National Research University Higher School of Economics)
摘要：We provide novel representations of strategy-proof voting rules applicable when voters have uni-dimensional single-peaked preferences. In particular, we introduce a 'grading curve' representation which is particularly useful when introducing variable electorates. Our analysis recovers, links and unifies existing results in the literature, and provides new characterizations when strategy-proofness is combined with other desirable properties such as ordinality, participation, consistency, and pr...
-
作者：Kanoh, Shin-ichi; Yoshise, Akiko
作者单位：University of Tsukuba; Japan Society for the Promotion of Science; University of Tsukuba
摘要：We propose a new variant of Chubanov's method for solving the feasibility problem over the symmetric cone by extending Roos's method (Optim Methods Softw 33(1):26-44, 2018) of solving the feasibility problem over the nonnegative orthant. The proposed method considers a feasibility problem associated with a norm induced by the maximum eigenvalue of an element and uses a rescaling focusing on the upper bound for the sum of eigenvalues of any feasible solution to the problem. Its computational bo...
-
作者：Wei, Linchuan; Atamturk, Alper; Gomez, Andres; Kucukyavuz, Simge
作者单位：Northwestern University; University of California System; University of California Berkeley; University of Southern California; Northwestern University
摘要：We consider the convex quadratic optimization problem in Rn with indicator variables and arbitrary constraints on the indicators. We showthat a convex hull description of the associated mixed-integer set in an extended space with a quadratic number of additional variables consists of an (n + 1) x (n + 1) positive semidefinite constraint (explicitly stated) and linear constraints. In particular, convexification of this class of problems reduces to describing a polyhedral set in an extended form...
-
作者：Zaichyk, Hananel; Biess, Armin; Kontorovich, Aryeh; Makarychev, Yury
作者单位：Ben-Gurion University of the Negev; Toyota Technological Institute - Chicago
