-
作者：Cheriyan, Joseph; Gao, Zhihan; Georgiou, Konstantinos; Singla, Sahil
作者单位：University of Waterloo; Carnegie Mellon University
摘要：We study the Asymmetric Traveling Salesman Problem (ATSP), and our focus is on negative results in the framework of the Sherali-Adams (SA) Lift and Project method. Our main result pertains to the standard linear programming (LP) relaxation of ATSP, due to Dantzig, Fulkerson, and Johnson. For any fixed integer and small , , there exists a digraph G on vertices such that the integrality ratio for level t of the SA system starting with the standard LP on G is . Thus, in terms of the input size, t...
-
作者：Iiduka, Hideaki
作者单位：Meiji University
摘要：This paper considers a networked system with a finite number of users and supposes that each user tries to minimize its own private objective function over its own private constraint set. It is assumed that each user's constraint set can be expressed as a fixed point set of a certain quasi-nonexpansive mapping. This enables us to consider the case in which the projection onto the constraint set cannot be computed efficiently. This paper proposes two methods for solving the problem of minimizin...
-
作者：Kim, Donghwan; Fessler, Jeffrey A.
作者单位：University of Michigan System; University of Michigan
摘要：We introduce new optimized first-order methods for smooth unconstrained convex minimization. Drori and Teboulle (Math Program 145(1-2):451-482, 2014. doi: 10.1007/s10107-013-0653-010.1007/s10107-013-0653-0 TargetType=) recently described a numerical method for computing the N-iteration optimal step coefficients in a class of first-order algorithms that includes gradient methods, heavy-ball methods (Polyak in USSR Comput Math Math Phys 4(5):1-17, 1964. doi: 10.1016/0041-5553(64)90137-510.1016/0...
-
作者：Aissi, Hassene; Mahjoub, A. Ridha; McCormick, S. Thomas; Queyranne, Maurice
作者单位：Universite PSL; Universite Paris-Dauphine; University of British Columbia; Universite Catholique Louvain
摘要：We consider multiobjective and parametric versions of the global minimum cut problem in undirected graphs and bounded-rank hypergraphs with multiple edge cost functions. For a fixed number of edge cost functions, we show that the total number of supported non-dominated (SND) cuts is bounded by a polynomial in the numbers of nodes and edges, i.e., is strongly polynomial. This bound also applies to the combinatorial facet complexity of the problem, i.e., the maximum number of facets (linear piec...
-
作者：Lee, Jon; Vygen, Jens
作者单位：University of Michigan System; University of Michigan; University of Bonn
-
作者：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...
-
作者：Ostrowski, James; Anjos, Miguel F.; Vannelli, Anthony
作者单位：University of Tennessee System; University of Tennessee Knoxville; Universite de Montreal; Universite de Montreal; Polytechnique Montreal; University of Guelph
摘要：The past decade has seen advances in general methods for symmetry breaking in mixed-integer linear programming. These methods are advantageous for general problems with general symmetry groups. Some important classes of mixed integer linear programming problems, such as bin packing and graph coloring, contain highly structured symmetry groups. This observation has motivated the development of problem-specific techniques. In this paper we show how to strengthen orbital branching in order to exp...
-
作者：Lehrer, Ehud; Teper, Roee
作者单位：Tel Aviv University; INSEAD Business School; Pennsylvania Commonwealth System of Higher Education (PCSHE); University of Pittsburgh
摘要：The extension of set functions (or capacities) in a concave fashion, namely a concavification, is an important issue in decision theory and combinatorics. It turns out that some set-functions cannot be properly extended if the domain is restricted to be bounded. This paper examines the structure of those capacities that can be extended over a bounded domain in a concave manner. We present a property termed the sandwich property that is necessary and sufficient for a capacity to be concavifiabl...
