-
作者：Torrico, Alfredo; Ahmed, Shabbir; Toriello, Alejandro
作者单位：University System of Georgia; Georgia Institute of Technology
摘要：We study the i.i.d. online bipartite matching problem, a dynamic version of the classical model where one side of the bipartition is fixed and known in advance, while nodes from the other side appear one at a time as i.i.d. realizations of a uniform distribution, and must immediately be matched or discarded. We consider various relaxations of the polyhedral set of achievable matching probabilities, introduce valid inequalities, and discuss when they are facet-defining. We also show how several...
-
作者：Correa, Rafael; Hantoute, Abderrahim; Perez-Aros, Pedro
作者单位：Universidad de Chile; Universidad de Chile; Universidad de Chile; Universidad de O'Higgins; Universidad de Chile
摘要：In this work we give an extension of the Brondsted-Rockafellar Theorem, and some of its important consequences, to proper convex lower-semicontinuous epi-pointed functions defined in locally convex spaces. We use a new approach based on a simple variational principle, which also allows recovering the classical results in a natural way.
-
作者：Ahmadian, Sara; Hosseinzadeh, Hamideh; Sanita, Laura
作者单位：University of Waterloo; Alzahra University
摘要：Cooperative matching games (Shapley and Shubik) and Network bargaining games (Kleinberg and Tardos) are games described by an undirected graph, where the vertices represent players. An important role in such games is played by stable graphs, that are graphs whose set of inessential vertices (those that are exposed by at least one maximum matching) are pairwise non adjacent. In fact, stable graphs characterize instances of such games that admit the existence of stable outcomes. In this paper, w...
-
作者：Lambrechts, Erik; Ficker, Annette M. C.; Goossens, Dries R.; Spieksma, Frits C. R.
作者单位：KU Leuven; KU Leuven; Ghent University
摘要：The Circle Method is widely used in the field of sport scheduling to generate schedules for round-robintournaments. If in such a tournament, team A played team B in its previous match and is now playing team C, team C is said to receive a carry-over effect from team B. The so-called carry-over effect value is a number that can be associated to each round-robin schedule; it represents a degree of unbalancedness of the schedule with respect to carry-over. Here, we prove that, for an even number ...
-
作者：Esfahani, Peyman Mohajerin; Kuhn, Daniel
作者单位：Delft University of Technology; Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne
摘要：We consider stochastic programs where the distribution of the uncertain parameters is only observable through a finite training dataset. Using the Wasserstein metric, we construct a ball in the space of (multivariate and non-discrete) probability distributions centered at the uniform distribution on the training samples, and we seek decisions that perform best in view of the worst-case distribution within this Wasserstein ball. The state-of-the-art methods for solving the resulting distributio...
-
作者：Bauschke, Heinz H.; Schaad, Jason; Wang, Xianfu
作者单位：University of British Columbia
摘要：The problem of finding a zero of the sum of two maximally monotone operators is of central importance in optimization. One successful method to find such a zero is the Douglas-Rachford algorithm which iterates a firmly nonexpansive operator constructed from the resolvents of the given monotone operators. In the context of finding minimizers of convex functions, the resolvents are actually proximal mappings. Interestingly, as pointed out by Eckstein in 1989, the Douglas-Rachford operator itself...
-
作者：Lubin, Miles; Yamangil, Emre; Bent, Russell; Vielma, Juan Pablo
作者单位：Massachusetts Institute of Technology (MIT); United States Department of Energy (DOE); Los Alamos National Laboratory
摘要：Generalizing both mixed-integer linear optimization and convex optimization, mixed-integer convex optimization possesses broad modeling power but has seen relatively few advances in general-purpose solvers in recent years. In this paper, we intend to provide a broadly accessible introduction to our recent work in developing algorithms and software for this problem class. Our approach is based on constructing polyhedral outer approximations of the convex constraints, resulting in a global solut...
-
作者：Combettes, Patrick L.; Eckstein, Jonathan
作者单位：Centre National de la Recherche Scientifique (CNRS); CNRS - National Institute for Mathematical Sciences (INSMI); Universite Paris Cite; Sorbonne Universite; Rutgers University System; Rutgers University New Brunswick; Rutgers University System; Rutgers University New Brunswick
摘要：We propose new primal-dual decomposition algorithms for solving systems of inclusions involving sums of linearly composed maximally monotone operators. The principal innovation in these algorithms is that they are block-iterative in the sense that, at each iteration, only a subset of the monotone operators needs to be processed, as opposed to all operators as in established methods. Flexible strategies are used to select the blocks of operators activated at each iteration. In addition, we allo...
-
作者：Kruger, A. Y.; Lopez, M. A.; Thera, M. A.
作者单位：Federation University Australia; Universitat d'Alacant; Centre National de la Recherche Scientifique (CNRS); Universite de Limoges
摘要：Our aim in the current article is to extend the developments in Kruger et al. (SIAM J Optim 20(6):3280-3296, 2010. doi:10.1137/100782206) and, more precisely, to characterize, in the Banach space setting, the stability of the local and global error bound property of inequalities determined by lower semicontinuous functions under data perturbations. We propose new concepts of (arbitrary, convex and linear) perturbations of the given function defining the system under consideration, which turn o...
-
作者：Adly, Samir; Dontchev, Asen
作者单位：Universite de Limoges; University of Michigan System; University of Michigan
