-
作者：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...
-
作者：Dadush, Daniel; Eisenbrand, Friedrich; Rothvoss, Thomas
作者单位：Centrum Wiskunde & Informatica (CWI); Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne; University of Washington; University of Washington Seattle
摘要：Approximate integer programming is the following: For a given convex body K subset of R-n, either determine whether K boolean AND Z(n) is empty, or find an integer point in the convex body 2 center dot (K - c)+ c which is K, scaled by 2 from its center of gravity c. Approximate integer programming can be solved in time 2(O(n)) while the fastest known methods for exact integer programming run in time 2(O(n)) center dot n(n). So far, there are no efficient methods for integer programming known t...
-
作者：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...
-
作者：Glaeser, Max; Pfetsch, Marc E.
作者单位：Technical University of Darmstadt
摘要：This article investigates smallest branch-and-bound trees and their computation. We first revisit the notion of hiding sets to deduce lower bounds on the size of branch-and bound trees for certain binary programs, using both variable disjunctions and general disjunctions. We then provide exponential lower bounds for variable disjunctions by a disjoint composition of smaller binary programs. Moreover, we investigate the complexity of finding small branch-and-bound trees using variable disjuncti...
-
作者：Lim, Tongseok
作者单位：Purdue University System; Purdue University
摘要：The theory of Optimal Transport and Martingale Optimal Transport (MOT) were inspired by problems in economics and finance and have flourished over the past decades, making significant advances in theory and practice. MOT considers the problem of pricing and hedging of a financial instrument, referred to as an option, assuming its payoff depends on a single asset price. In this paper we introduce Vectorial Martingale Optimal Transport (VMOT) problem, which considers the more general and realist...
