-
作者：Delling, Daniel; Fleischman, Daniel; Goldberg, Andrew V.; Razenshteyn, Ilya; Werneck, Renato F.
作者单位：Microsoft; Cornell University; Massachusetts Institute of Technology (MIT)
摘要：We present a novel exact algorithm for the minimum graph bisection problem, whose goal is to partition a graph into two equally-sized cells while minimizing the number of edges between them. Our algorithm is based on the branch-and-bound framework and, unlike most previous approaches, it is fully combinatorial. We introduce novel lower bounds based on packing trees, as well as a new decomposition technique that contracts entire regions of the graph while preserving optimality guarantees. Our a...
-
作者：Awate, Yogesh; Cornuejols, Gerard; Guenin, Bertrand; Tuncel, Levent
作者单位：Carnegie Mellon University; University of Waterloo
摘要：We compare the relative strength of valid inequalities for the integer hull of the feasible region of mixed integer linear programs with two equality constraints, two unrestricted integer variables and any number of nonnegative continuous variables. In particular, we prove that the closure of Type 2 triangle (resp. Type 3 triangle; quadrilateral) inequalities, are all within a factor of of the integer hull, and provide examples showing that the approximation factor is not less than . There is ...
-
作者：Wang, Mengdi; Bertsekas, Dimitri P.
作者单位：Princeton University; Massachusetts Institute of Technology (MIT)
摘要：We consider the solution of strongly monotone variational inequalities of the form , for all . We focus on special structures that lend themselves to sampling, such as when is the intersection of a large number of sets, and/or is an expected value or is the sum of a large number of component functions. We propose new methods that combine elements of incremental constraint projection and stochastic gradient. These methods are suitable for problems involving large-scale data, as well as problems...
-
作者：Dobre, Cristian; Vera, Juan
作者单位：Wageningen University & Research; Tilburg University
摘要：Copositive programming is a relative young field which has evolved into a highly active research area in mathematical optimization. An important line of research is to use semidefinite programming to approximate conic programming over the copositive cone. Two major drawbacks of this approach are the rapid growth in size of the resulting semidefinite programs, and the lack of information about the quality of the semidefinite programming approximations. These drawbacks are an inevitable conseque...
-
作者：Ottem, John Christian; Ranestad, Kristian; Sturmfels, Bernd; Vinzant, Cynthia
作者单位：University of Cambridge; University of Oslo; University of California System; University of California Berkeley; North Carolina State University
摘要：Quartic spectrahedra in 3-space form a semialgebraic set of dimension 24. This set is stratified by the location of the ten nodes of the corresponding real quartic surface. There are twenty maximal strata, identified recently by Degtyarev and Itenberg, via the global Torelli Theorem for real K3 surfaces. We here give a new proof that is self-contained and algorithmic. This involves extending Cayley's characterization of quartic symmetroids, by the property that the branch locus of the projecti...
-
作者：Lasserre, Jean B.
作者单位：Centre National de la Recherche Scientifique (CNRS); Universite de Toulouse; Universite de Toulouse
摘要：Given a compact basic semi- algebraic set K subset of R-n x R-m, a simple set B (box or ellipsoid), and some semi- algebraic function f, we consider sets defined with quantifiers, of the form R-f := {x is an element of B : f (x, y) <= 0 for all y such that (x, y) is an element of K} D-f := {x is an element of B : f (x, y) >= 0 for some y such that (x, y) is an element of K}. The former set R-f is particularly useful to qualify robust decisions x versus noise parameter y (e. g. in robust optim...
-
作者：He, Bingsheng; Yuan, Xiaoming
作者单位：Nanjing University; Hong Kong Baptist University
摘要：This note provides a simple proof of a worst-case convergence rate measured by the iteration complexity for the Douglas-Rachford operator splitting method for finding a root of the sum of two maximal monotone set-valued operators. The accuracy of an iterate to the solution set is measured by the residual of a characterization of the original problem, which is different from conventional measures such as the distance to the solution set.
-
作者：Li, G.; Mordukhovich, B. S.; Pham, T. S.
作者单位：University of New South Wales Sydney; Wayne State University; King Fahd University of Petroleum & Minerals; Duy Tan University
摘要：In this paper we derive new fractional error bounds for polynomial systems with exponents explicitly determined by the dimension of the underlying space and the number/degree of the involved polynomials. Our major result extends the existing error bounds from the system involving only a single polynomial to a general polynomial system and do not require any regularity assumptions. In this way we resolve, in particular, some open questions posed in the literature. The developed techniques are l...
-
作者：Carnes, Tim; Shmoys, David B.
作者单位：Cornell University; Cornell University
摘要：Primal-dual algorithms have played an integral role in recent developments in approximation algorithms, and yet there has been little work on these algorithms in the context of LP relaxations that have been strengthened by the addition of more sophisticated valid inequalities. We introduce primal-dual schema based on the LP relaxations devised by Carr et al. for the minimum knapsack problem as well as for the single-demand capacitated facility location problem. Our primal-dual algorithms achie...
-
作者：Asamov, Tsvetan; Ruszczynski, Andrzej
作者单位：Princeton University; Rutgers University System; Rutgers University New Brunswick
摘要：In this paper we study the concept of time consistency as it relates to multistage risk-averse stochastic optimization problems on finite scenario trees. We use dynamic time-consistent formulations to approximate problems having a single coherent risk measure applied to the aggregated costs over all time periods. The dual representation of coherent risk measures is used to create a time-consistent cutting plane algorithm. Additionally, we also develop methods for the construction of universal ...
