1-2期

最新文章

• A simple and fast linear-time algorithm for divisor methods of apportionment AI翻译
  作者：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...
• Note on axiomatic properties of apportionment methods for proportional representation systems AI翻译
  作者：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...
• A Constant-Factor Approximation for Generalized Malleable Scheduling under M#-Concave Processing Speeds AI翻译
  作者：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 ...
• New characterizations of strategy-proofness under single-peakedness AI翻译
  作者：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...
• A new extension of Chubanov's method to symmetric cones AI翻译
  作者：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...
• On the convex hull of convex quadratic optimization problems with indicators AI翻译
  作者：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...
• Efficient Kirszbraun extension with applications to regression (vol 207, pg 617, 2024) AI翻译
  作者：Zaichyk, Hananel; Biess, Armin; Kontorovich, Aryeh; Makarychev, Yury
  作者单位：Ben-Gurion University of the Negev; Toyota Technological Institute - Chicago
• An abstract model for branch and cut AI翻译
  作者：Kazachkov, Aleksandr M.; Le Bodic, Pierre; Sankaranarayanan, Sriram
  作者单位：State University System of Florida; University of Florida; Monash University; Indian Institute of Management (IIM System); Indian Institute of Management Ahmedabad
  摘要：Branch and cut is the dominant paradigm for solving a wide range of mathematical programming problems-linear or nonlinear-combining efficient search (via branch and bound) and relaxation-tightening procedures (via cutting planes, or cuts). While there is a wealth of computational experience behind existing cutting strategies, there is simultaneously a relative lack of theoretical explanations for these choices, and for the tradeoffs involved therein. Recent papers have explored abstract models...
• A solution algorithm for chance-constrained problems with integer second-stage recourse decisions AI翻译
  作者：Lodi, Andrea; Malaguti, Enrico; Monaci, Michele; Nannicini, Giacomo; Paronuzzi, Paolo
  作者单位：Technion Israel Institute of Technology; University of Bologna; University of Southern California
  摘要：We study a class of chance-constrained two-stage stochastic optimization problems where the second-stage recourse decisions belong to mixed-integer convex sets. Due to the nonconvexity of the second-stage feasible sets, standard decomposition approaches cannot be applied. We develop a provably convergent branch-and-cut scheme that iteratively generates valid inequalities for the convex hull of the second-stage feasible sets, resorting to spatial branching when cutting no longer suffices. We sh...
• The price of Anarchy in series-parallel network congestion games AI翻译
  作者：Hao, Bainian; Michini, Carla
  作者单位：University of Wisconsin System; University of Wisconsin Madison
  摘要：We study the inefficiency of pure Nash equilibria in symmetric network congestion games defined over series-parallel networks with affine edge delays. For arbitrary networks, Correa (Math Oper Res 44(4):1286-1303, 2019) proved a tight upper bound of 5/2 on the PoA. On the other hand, for extension-parallel networks, a subclass of series-parallel networks, Fotakis (Theory Comput Syst 47:113-136, 2010) proved that the PoA is 4/3. He also showed that this bound is not valid for series-parallel ne...