-
作者：Nesterov, Yurii
摘要：In this paper we develop new tensor methods for unconstrained convex optimization, which solve at each iteration an auxiliary problem of minimizing convex multivariate polynomial. We analyze the simplest scheme, based on minimization of a regularized local model of the objective function, and its accelerated version obtained in the framework of estimating sequences. Their rates of convergence are compared with the worst-case lower complexity bounds for corresponding problem classes. Finally, f...
-
作者：Schmidt, Daniel; Zey, Bernd; Margot, Francois
作者单位：University of Bonn; Dortmund University of Technology
摘要：A correction to this paper has been published: https://doi.org/10.1007/s10107-021-01648-9
-
作者：Dash, Sanjeeb; Gunluk, Oktay; Lee, Dabeen
作者单位：International Business Machines (IBM); IBM USA; Cornell University; Institute for Basic Science - Korea (IBS)
摘要：Integer programming problems that arise in practice often involve decision variables with one or two sided bounds. In this paper, we consider a generalization of Chvatal-Gomory inequalities obtained by strengthening Chvatal-Gomory inequalities using the bounds on the variables. We prove that the closure of a rational polyhedron obtained after applying the generalized Chvatal-Gomory inequalities is also a rational polyhedron. This generalizes a result of Dunkel and Schulz on 0-1 problems to the...
-
作者：Seguin-Charbonneau, Loic; Shepherd, F. Bruce
作者单位：University of British Columbia
摘要：We study the maximum edge-disjoint path problem (medp) in planar graphs G = (V, E) with edge capacities u(e). We are given a set of terminal pairs si ti, i = 1, 2..., k and wish to find a maximum routable subset of demands. That is, a subset of demands that can be connected by a family of paths that use each edge at most u(e) times. It is well-known that there is an integrality gap of Omega(root n) for the natural LP relaxation, even in planar graphs (Garg-Vazirani-Yannakakis). We show that if...
-
作者：Correa, Jose; Saona, Raimundo; Ziliotto, Bruno
作者单位：Universidad de Chile; Centre National de la Recherche Scientifique (CNRS); Universite PSL; Universite Paris-Dauphine
摘要：In the classic prophet inequality, a well-known problem in optimal stopping theory, samples from independent random variables (possibly differently distributed) arrive online. A gambler who knows the distributions, but cannot see the future, must decide at each point in time whether to stop and pick the current sample or to continue and lose that sample forever. The goal of the gambler is to maximize the expected value of what she picks and the performance measure is the worst case ratio betwe...
-
作者：Koppe, Matthias; Zhou, Yuan
作者单位：University of California System; University of California Davis; University of Kentucky
摘要：We investigate three competing notions that generalize the notion of a facet of finite-dimensional polyhedra to the infinite-dimensional Gomory-Johnson model. These notions were known to coincide for continuous piecewise linear functions with rational breakpoints. We show that two of the notions, extreme functions and facets, coincide for the case of continuous piecewise linear functions, removing the hypothesis regarding rational breakpoints. We prove an if-and-only-if version of the Gomory-J...
-
作者：Nobili, Paolo; Sassano, Antonio
作者单位：University of Salento; Sapienza University Rome
摘要：A graph G(V, E) is claw-free if no vertex has three pairwise non-adjacent neighbours. The maximum weight stable set (MWSS) problem in a claw-free graph is a natural generalization of the matching problem and has been shown to be polynomially solvable by Minty and Sbihi in 1980. In a remarkable paper, Faenza, Oriolo and Stauffer have shown that, in a two-step procedure, a claw-free graph can be first turned into a quasi-line graph by removing strips containing all the irregular nodes and then d...
-
作者：Schmidt, Daniel; Zey, Bernd; Margot, Francois
作者单位：University of Bonn; Dortmund University of Technology
摘要：The Steiner forest problem asks for a minimum weight forest that spans a given number of terminal sets. We propose new cut- and flow-based integer linear programming formulations for the problem which yield stronger linear programming bounds than the two previous strongest formulations: The directed cut formulation (Balakrishnan et al. in Oper Res 37(5):716-740, 1989; Chopra and Rao in Math Prog 64(1):209-229, 1994) and the advanced flow formulation by Magnanti and Raghavan (Networks 45:61-79,...
-
作者：Chubanov, Sergei
-
作者：Szeszler, David
作者单位：Budapest University of Technology & Economics
摘要：We present various new results on greedoids. We prove a theorem that generalizes an equivalent formulation of Edmonds' classic matroid polytope theorem to local forest greedoids-a class of greedoids that contains matroids as well as branching greedoids. We also describe an application of this theorem in the field of measuring the reliability of networks by game-theoretical tools. Finally, we prove new results on the optimality of the greedy algorithm on greedoids and correct some mistakes that...
