-
作者：Lagarde, Antoine; Tomala, Tristan
作者单位：Hautes Etudes Commerciales (HEC) Paris
摘要：We consider the problem of optimal partisan gerrymandering: a legislator in charge of redrawing the boundaries of equal-sized congressional districts wants to ensure the best electoral outcome for his own party. The so-called gerrymanderer faces two issues: the number of districts is finite and there is uncertainty at the level of each district. Solutions to this problem consists in cracking favorable voters in as many districts as possible to get tight majorities, and in packing unfavorable v...
-
作者：Ambrus, Gergely; Csiszarik, Adrian; Matolcsi, Mate; Varga, Daniel; Zsamboki, Pal
作者单位：Szeged University; HUN-REN; HUN-REN Alfred Renyi Institute of Mathematics; Eotvos Lorand University; Budapest University of Technology & Economics
摘要：By improving upon previous estimates on a problem posed by L. Moser, we prove a conjecture of Erdos that the density of any measurable planar set avoiding unit distances is less than 1/4. Our argument implies the upper bound of 0.2470.
-
作者：Chen, Rui; Luedtke, James
作者单位：University of Wisconsin System; University of Wisconsin Madison
摘要：We propose a new method for separating valid inequalities for the epigraph of a function of binary variables. The proposed inequalities are disjunctive cuts defined by disjunctive terms obtained by enumerating a subset I of the binary variables. We show that by restricting the support of the cut to the same set of variables I, a cut can be obtained by solving a linear program with 2(vertical bar I vertical bar) constraints. While this limits the size of the set I used to define the multi-term ...
-
作者：El Housni, Omar; Foussoul, Ayoub; Goyal, Vineet
作者单位：Cornell University; Columbia University
摘要：We consider the class of disjoint bilinear programs max {x(T) y | x is an element of X, y is an element of Y} where X and Y are packing polytopes. We present an O( log logm1 /logm1 log logm2/ logm2)-approximation algorithm for this problem where m1 and m2 are the number of packing constraints in X and Y respectively. In particular, we show that there exists a near-optimal solution ( (x) over tilde, (y) over tilde) such that (x) over tilde and (y) over tilde are near-integral. We give an LP rel...
-
作者：Aujol, J. -F.; Dossal, Ch.; Rondepierre, A.
作者单位：Universite de Bordeaux; Centre National de la Recherche Scientifique (CNRS); Universite Federale Toulouse Midi-Pyrenees (ComUE); Universite de Toulouse; Institut National des Sciences Appliquees de Toulouse; Universite Toulouse III - Paul Sabatier; Universite de Toulouse; Centre National de la Recherche Scientifique (CNRS)
摘要：In this work, we are interested in the famous FISTA algorithm. We show that FISTA is an automatic geometrically optimized algorithm for functions satisfying a quadratic growth assumption. This explains why FISTA works better than the standard Forward-Backward algorithm (FB) in such a case, although FISTA is known to have a polynomial asymptotic convergence rate while FB is exponential. We provide a simple rule to tune the alpha parameter within the FISTA algorithm to reach an epsilon-solution ...
-
作者：Caragiannis, Ioannis; Filos-Ratsikas, Aris; Nath, Swaprava; Voudouris, Alexandros A.
作者单位：Aarhus University; University of Liverpool; Indian Institute of Technology System (IIT System); Indian Institute of Technology (IIT) - Kanpur; University of Essex
摘要：When a company undergoes a merger or transfers its ownership, the existing governing body has an opinion on which buyer should take over as the new owner. Similar situations occur while assigning the host of big sports tournaments, like the World Cup or the Olympics. In all these settings, the values of the external bidders are as important as the opinions of the internal experts. Motivated by such scenarios, we consider a social welfare maximizing approach to design and analyze truthful mecha...
-
作者：Kraetschmer, Volker
作者单位：University of Duisburg Essen
摘要：We investigate statistical properties of the optimal value of the Sample Average Approximation of stochastic programs, continuing the study (Kratschmer in Nonasymptotic upper estimates for errors of the sample average approximation method to solve risk averse stochastic programs, 2023. Forthcoming in SIAM J. Optim.). Central Limit Theorem type results are derived for the optimal value. As a crucial point the investigations are based on a new type of conditions from the theory of empirical proc...
-
作者：Zaichyk, Hananel; Biess, Armin; Kontorovich, Aryeh; Makarychev, Yury
作者单位：Ben-Gurion University of the Negev; Toyota Technological Institute - Chicago
摘要：We introduce a framework for performing vector-valued regression in finite-dimensional Hilbert spaces. Using Lipschitz smoothness as our regularizer, we leverage Kirszbraun's extension theorem for off-data prediction. We analyze the statistical and computational aspects of this method-to our knowledge, its first application to supervised learning. We decompose this task into two stages: training (which corresponds operationally to smoothing/regularization) and prediction (which is achieved via...
-
作者：Dadush, Daniel; Hojny, Christopher; Huiberts, Sophie; Weltge, Stefan
作者单位：Eindhoven University of Technology; Columbia University; Technical University of Munich
摘要：We give a simple and natural method for computing approximately optimal solutions for minimizing a convex function f over a convex set K given by a separation oracle. Our method utilizes the Frank-Wolfe algorithm over the cone of valid inequalities of K and subgradients of f . Under the assumption that f is L-Lipschitz and that K contains a ball of radius r and is contained inside the origin centered ball of radius ((R L)2 ) R, using O((RL)(2)/(e)2 . R-2/ r(2)) iterations and calls to the orac...
-
作者：Aprile, Manuel; Averkov, Gennadiy; Di Summa, Marco; Hojny, Christopher
作者单位：University of Padua; Brandenburg University of Technology Cottbus; Eindhoven University of Technology
摘要：For a finite set X subset of Z(d) that can be represented as X = Q n Z(d) for some polyhedron Q, we call Q a relaxation of X and define the relaxation complexity rc(X) of X as the least number of facets among all possible relaxations Q of X. The rational relaxation complexity rc(Q)( X) restricts the definition of rc( X) to rational polyhedra Q. In this article, we focus on X = Delta(d), the vertex set of the standard simplex, which consists of the null vector and the standard unit vectors in R...
