1-2期

最新文章

• An exact algorithm for robust influence maximization AI翻译
  作者：Nannicini, Giacomo; Sartor, Giorgio; Traversi, Emiliano; Calvo, Roberto Wolfler
  作者单位：International Business Machines (IBM); IBM USA; SINTEF; Centre National de la Recherche Scientifique (CNRS); CNRS - Institute for Information Sciences & Technologies (INS2I); University of Cagliari
  摘要：We propose a Branch-and-Cut algorithm for the robust influence maximization problem. The influence maximization problem aims to identify, in a social network, a set of given cardinality comprising actors that are able to influence the maximum number of other actors. We assume that the social network is given in the form of a graph with node thresholds to indicate the resistance of an actor to influence, and arc weights to represent the strength of the influence between two actors. In the robus...
• A simplex-type algorithm for continuous linear programs with constant coefficients AI翻译
  作者：Shindin, Evgeny; Weiss, Gideon
  作者单位：International Business Machines (IBM); IBM ISRAEL; University of Haifa
  摘要：We consider continuous linear programs over a continuous finite time horizon T, with a constant coefficient matrix, linear right hand side functions and linear cost coefficient functions. Specifically, we search for optimal solutions in the space of measures or of functions of bounded variation. These models generalize the separated continuous linear programming models and their various duals, as formulated in the past by Anderson, by Pullan, and by Weiss. In previous papers we formulated a sy...
• When do birds of a feather flock together? k-Means, proximity, and conic programming AI翻译
  作者：Li, Xiaodong; Li, Yang; Ling, Shuyang; Strohmer, Thomas; Wei, Ke
  作者单位：University of California System; University of California Davis; University of California System; University of California Davis; Fudan University
  摘要：Given a set of data, one central goal is to group them into clusters based on some notion of similarity between the individual objects. One of the most popular and widely-used approaches is k-means despite the computational hardness to find its global minimum. We study and compare the properties of different convex relaxations by relating them to corresponding proximity conditions, an idea originally introduced by Kumar and Kannan. Using conic duality theory, we present an improved proximity c...
• Lower bounds for finding stationary points I AI翻译
  作者：Carmon, Yair; Duchi, John C.; Hinder, Oliver; Sidford, Aaron
  作者单位：Stanford University; Stanford University; Stanford University
  摘要：We prove lower bounds on the complexity of finding similar to-stationary points (points x such that similar to. f (x)similar to = similar to) of smooth, high-dimensional, and potentially non-convex functions f. We consider oracle-based complexity measures, where an algorithm is given access to the value and all derivatives of f at a query point x. We show that for any (potentially randomized) algorithm A, there exists a function f with Lipschitz pth order derivatives such that A requires at le...
• The asymmetric traveling salesman path LP has constant integrality ratio AI翻译
  作者：Koehne, Anna; Traub, Vera; Vygen, Jens
  作者单位：University of Bonn; University of Bonn
  摘要：We show that the classical LP relaxation of the asymmetric traveling salesman path problem (ATSPP) has constant integrality ratio. If.ATSP and.ATSPP denote the integrality ratios for the asymmetric TSP and its path version, then.ATSPP = 4.ATSP - 3. We prove an even better bound for node-weighted instances: if the integrality ratio for ATSP on node-weighted instances is.NWATSP, then the integrality ratio for ATSPP on node-weighted instances is at most 2.NW ATSP - 1. Moreover, we show that for A...
• The geometry of SDP-exactness in quadratic optimization AI翻译
  作者：Cifuentes, Diego; Harris, Corey; Sturmfels, Bernd
  作者单位：Massachusetts Institute of Technology (MIT); University of Oslo; University of California System; University of California Berkeley
  摘要：Consider the problem of minimizing a quadratic objective subject to quadratic equations. We study the semialgebraic region of objective functions for which this problem is solved by its semidefinite relaxation. For the Euclidean distance problem, this is a bundle of spectrahedral shadows surrounding the given variety. We characterize the algebraic boundary of this region and we derive a formula for its degree.
• Computing Walrasian equilibria: fast algorithms and structural properties AI翻译
  作者：Leme, Renato Paes; Wong, Sam Chiu-wai
  作者单位：Alphabet Inc.; Google Incorporated; University of California System; University of California Berkeley
  摘要：We present the first polynomial time algorithm for computing Walrasian equilibrium in an economy with indivisible goods and general buyer valuations having only access to an aggregate demand oracle, i.e., an oracle that given prices on all goods, returns the aggregated demand over the entire population of buyers. For the important special case of gross substitute valuations, our algorithm queries the aggregate demand oracle O(n(3)) times and takes O(n(3)) time, where n is the number of goods a...
• Chordal decomposition in operator-splitting methods for sparse semidefinite programs AI翻译
  作者：Zheng, Yang; Fantuzzi, Giovanni; Papachristodoulou, Antonis; Goulart, Paul; Wynn, Andrew
  作者单位：University of Oxford; Imperial College London
  摘要：We employ chordal decomposition to reformulate a large and sparse semidefinite program (SDP), either in primal or dual standard form, into an equivalent SDP with smaller positive semidefinite (PSD) constraints. In contrast to previous approaches, the decomposed SDP is suitable for the application of first-order operator-splitting methods, enabling the development of efficient and scalable algorithms. In particular, we apply the alternating direction method of multipliers (ADMM) to solve decomp...
• Piecewise smooth extreme functions are piecewise linear AI翻译
  作者：Di Summa, Marco
  作者单位：University of Padua
  摘要：The infinite relaxations in integer programming were introduced by Gomory and Johnson to provide a general framework for the theory of cutting planes: the so-called valid functions, and in particular the minimal and extreme functions, can be seen as automatic rules for the generation of cuts. However, while many extreme functions are piecewise linear and therefore easy to describe, the set of extreme functions turns out to have a very complicated mathematical structure, as several extreme func...
• Asynchronous level bundle methods AI翻译
  作者：Iutzeler, Franck; Malick, Jerome; de Oliveira, Welington
  作者单位：Communaute Universite Grenoble Alpes; Universite Grenoble Alpes (UGA); Centre National de la Recherche Scientifique (CNRS); Universite PSL; MINES ParisTech
  摘要：In this paper, we consider nonsmooth convex optimization problems with additive structure featuring independent oracles (black-boxes) working in parallel. Existing methods for solving these distributed problems in a general form are synchronous, in the sense that they wait for the responses of all the oracles before performing a new iteration. In this paper, we propose level bundle methods handling asynchronous oracles. These methods require original upper-bounds (using upper-models or scarce ...