-
作者：Pashkovich, Kanstantsin
作者单位：University of Ottawa
摘要：In cooperative games, players have a possibility to form different coalitions. This leads to the questions about ways to motivate all players to collaborate, i.e. to motivate the players to form the so-called grand coalition. One of such ways is captured by the concept of nucleolus, which dates back to Babylonian Talmud. Weighted voting games form a class of cooperative games, that are often used to model decision making processes in parliaments. In this paper, we provide an algorithm for comp...
-
作者：van Hoeve, Willem-Jan
作者单位：Carnegie Mellon University
摘要：We introduce an iterative framework for solving graph coloring problems using decision diagrams. The decision diagram compactly represents all possible color classes, some of which may contain edge conflicts. In each iteration, we use a constrained minimum network flow model to compute a lower bound and identify conflicts. Infeasible color classes associated with these conflicts are removed by refining the decision diagram. We prove that in the best case, our approach may use exponentially sma...
-
作者：Lu, Cheng; Hochbaum, Dorit S.
作者单位：University of California System; University of California Berkeley
摘要：We study a 1-dimensional discrete signal denoising problem that consists of minimizing a sum of separable convex fidelity terms and convex regularization terms, the latter penalize the differences of adjacent signal values. This problem generalizes the total variation regularization problem. We provide here a unified approach to solve the problem for general convex fidelity and regularization functions that is based on the Karush-Kuhn-Tucker optimality conditions. This approach is shown here t...
-
作者：Hoa, Le Tuan
作者单位：Vietnam Academy of Science & Technology (VAST)
摘要：The paper provides a connection between Commutative Algebra and Integer Programming and contains two parts. The first one is devoted to the asymptotic behavior of integer programs with a fixed cost linear functional and the constraint sets consisting of a finite system of linear equations or inequalities with integer coefficients depending linearly on n. An integer N-* is determined such that the optima of these integer programs are a quasi-linear function of n for all n >= N-*. Using results ...
-
作者：Fan, Jingnan; Ruszczynski, Andrzej
作者单位：Rutgers University System; Rutgers University New Brunswick; Rutgers University System; Rutgers University New Brunswick
摘要：For controlled discrete-time stochastic processes we introduce a new class of dynamic risk measures, which we call process-based. Their main feature is that they measure risk of processes that are functions of the history of a base process. We introduce a new concept of conditional stochastic time consistency and we derive the structure of process-based risk measures enjoying this property. We show that they can be equivalently represented by a collection of static law-invariant risk measures ...
-
作者：Frank, Andras; Murota, Kazuo
作者单位：Eotvos Lorand University; Tokyo Metropolitan University; Research Organization of Information & Systems (ROIS); Institute of Statistical Mathematics (ISM) - Japan
摘要：The present work is the first member of a pair of papers concerning decreasingly-minimal (dec-min) elements of a set of integral vectors, where a vector is dec-min if its largest component is as small as possible, within this, the next largest component is as small as possible, and so on. This discrete notion, along with its fractional counterpart, showed up earlier in the literature under various names. The domain we consider is an M-convex set, that is, the set of integral elements of an int...
-
作者：Garg, Naveen; Kumar, Nikhil; Sebo, Andras
作者单位：Indian Institute of Technology System (IIT System); Indian Institute of Technology (IIT) - Delhi; University of Potsdam; Communaute Universite Grenoble Alpes; Institut National Polytechnique de Grenoble; Universite Grenoble Alpes (UGA); Centre National de la Recherche Scientifique (CNRS)
摘要：In this paper, we bound the integrality gap and the approximation ratio for maximum plane multiflow problems and deduce bounds on the flow-multicut-gap. We consider instances where the union of the supply and demand graphs is planar and prove that there exists a multiflow of value at least half the capacity of a minimum multicut. We then show how to convert any multiflow into a half-integer flow of value at least half the original multiflow. Finally, we round any half-integer multiflow into an...
-
作者：Anegg, Georg; Angelidakis, Haris; Kurpisz, Adam; Zenklusen, Rico
作者单位：Swiss Federal Institutes of Technology Domain; ETH Zurich; Eindhoven University of Technology
摘要：There has been a recent surge of interest in incorporating fairness aspects into classical clustering problems. Two recently introduced variants of the k-Center problem in this spirit are Colorful k-Center, introduced by Bandyapadhyay, Inamdar, Pai, and Varadarajan, and lottery models, such as the Fair Robust k-Center problem introduced by Harris, Pensyl, Srinivasan, and Trinh. To address fairness aspects, these models, compared to traditional k-Center, include additional covering constraints....
-
作者：Driggs, Derek; Ehrhardt, Matthias J.; Schonlieb, Carola-Bibiane
作者单位：University of Cambridge; University of Bath
摘要：Variance reduction is a crucial tool for improving the slow convergence of stochastic gradient descent. Only a few variance-reduced methods, however, have yet been shown to directly benefit from Nesterov's acceleration techniques to match the convergence rates of accelerated gradient methods. Such approaches rely on negative momentum, a technique for further variance reduction that is generally specific to the SVRG gradient estimator. In this work, we show for the first time that negative mome...
-
作者：Friedland, Shmuel; Lasserre, Jean-Bernard; Lim, Lek-Heng; Nie, Jiawang
作者单位：University of Illinois System; University of Illinois Chicago; University of Illinois Chicago Hospital; Centre National de la Recherche Scientifique (CNRS); University of Chicago; University of California System; University of California San Diego
