-
作者：Adly, S.; Nacry, F.; Thibault, L.
作者单位：Universite de Limoges; Universite Perpignan Via Domitia; Universite de Montpellier
摘要：In this paper, we present diverse new metric properties that prox-regular sets shared with convex ones. At the heart of our work lie the Legendre-Fenchel transform and complements of balls. First, we show that a connected prox-regular set is completely determined by the Legendre-Fenchel transform of a suitable perturbation of its indicator function. Then, we prove that such a function is also the right tool to extend, to the context of prox-regular sets, the famous connection between the dista...
-
作者：Benedek, Marton; Fliege, Jorg; Tri-Dung Nguyen
作者单位：HUN-REN; HUN-REN Centre for Economic & Regional Studies; Institute of Economics - HAS; Hungarian Academy of Sciences; Corvinus University Budapest; Budapest University of Technology & Economics; University of Southampton; University of Southampton; University of Southampton
摘要：The nucleolus offers a desirable payoff-sharing solution in cooperative games, thanks to its attractive properties-it always exists and lies in the core (if the core is nonempty), and it is unique. The nucleolus is considered as the most `stable' solution in the sense that it lexicographically minimizes the dissatisfactions among all coalitions. Although computing the nucleolus is very challenging, the Kohlberg criterion offers a powerful method for verifying whether a solution is the nucleolu...
-
作者：Fuellner, Christian; Kirst, Peter; Stein, Oliver
作者单位：Helmholtz Association; Karlsruhe Institute of Technology
摘要：We address the problem of determining convergent upper bounds in continuous non-convex global minimization of box-constrained problems with equality constraints. These upper bounds are important for the termination of spatial branch-and-bound algorithms. Our method is based on the theorem of Miranda which helps to ensure the existence of feasible points in certain boxes. Then, the computation of upper bounds at the objective function over those boxes yields an upper bound for the globally mini...
-
作者：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...
-
作者：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...
-
作者：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
