-
作者：Borozan, Valentin; Cornuejols, Gerard
作者单位：Aix-Marseille Universite; Carnegie Mellon University
摘要：In this paper, we consider a semi-infinite relaxation of mixed-integer linear programs. We show that minimal valid inequalities for this relaxation correspond to maximal lattice-free convex sets, and that they arise from nonnegative, piecewise linear, positively homogeneous, convex functions.
-
作者：Grechuk, Bogdan; Molyboha, Anton; Zabarankin, Michael
作者单位：Stevens Institute of Technology
摘要：An approach to the Shannon and Renyi entropy maximization problems with constraints on the mean and law-invariant deviation measure for a random variable has been developed. The approach is based on the representation of law-invariant deviation measures through corresponding convex compact sets of nonnegative concave functions. A solution to the problem has been shown to have an alpha-concave distribution (log-concave for Shannon entropy), for which in the case of comonotone deviation measures...
-
作者：Belloni, Alexandre; Freund, Robert M.; Vempala, Santosh
作者单位：Duke University; Massachusetts Institute of Technology (MIT); University System of Georgia; Georgia Institute of Technology
摘要：The classical perceptron algorithm is an elementary row-action/relaxation algorithm for solving a homogeneous linear inequality system Ax > 0. A natural condition measure associated with this algorithm is the Euclidean width tau of the cone of feasible solutions, and the iteration complexity of the perceptron algorithm is bounded by 1/tau(2) [see Rosenblatt, F. 1962. Principles of Neurodynamics. Spartan Books, Washington, DC]. Dunagan and Vempala [Dunagan, J., S. Vempala. 2007. A simple polyno...
-
作者：Fujishige, Satoru; Nagano, Kiyohito
作者单位：Kyoto University; Institute of Science Tokyo; Tokyo Institute of Technology
摘要：A linearly parameterized polymatroid intersection problem appears in the context of principal partitions. We consider a submodular intersection problem on a pair of strong-map sequences of submodular functions, which is an extension of the linearly parameterized polymatroid intersection problem to a nonlinearly parameterized one. We introduce the concept of a basis frame on a finite nonempty set of cardinality n that gives a mapping from the set of all base polyhedra in n-dimensional space int...
-
作者：van Zuylen, Anke; Williamson, David P.
作者单位：Tsinghua University; Cornell University
摘要：We consider ranking and clustering problems related to the aggregation of inconsistent information, in particular, rank aggregation, (weighted) feedback arc set in tournaments, consensus and correlation clustering, and hierarchical clustering. Ailon et al. [Ailon, N., M. Charikar, A. Newman. 2005. Aggregating inconsistent information: Ranking and clustering. Proc. 37th Annual ACM Sympos. Theory Comput. (STOC '05), 684-693], Ailon and Charikar [Ailon, N., M. Charikar. 2005. Fitting tree metrics...
-
作者：Ben-Tal, Aharon; Nemirovski, Arkadi
作者单位：Technion Israel Institute of Technology; University System of Georgia; Georgia Institute of Technology
摘要：In the paper we consider the chance-constrained version of an affinely perturbed linear matrix inequality (LMI) constraint, assuming the primitive perturbations to be independent with light-tail distributions (e.g., bounded or Gaussian). Constraints of this type, playing a central role in chance-constrained linear/conic quadratic/semidefinite programming, are typically computationally intractable. The goal of this paper is to develop a tractable approximation to these chance constraints. Our a...
-
作者：Penn, Michal; Polukarov, Maria; Tennenholtz, Moshe
作者单位：Technion Israel Institute of Technology; University of Southampton; Microsoft; MICROSOFT ISRAEL
摘要：We introduce a new class of games called random order congestion games (ROCGs). In an ROCG, each player has a task that can be carried out by any element of a set of resources, and each resource executes its assigned tasks in a random order. The aim of each player is to minimize his expected cost, which is the sum of the fixed costs over the set of his utilized resources and the expected cost of his task execution. The cost of a player's task execution is determined by the earliest time his ta...
-
作者：Buchbinder, Niv; Naor, Joseph (Seffi)
作者单位：Microsoft; Technion Israel Institute of Technology
摘要：We study a wide range of online covering and packing optimization problems. In an online covering problem, a linear cost function is known in advance, but the linear constraints that define the feasible solution space are given one by one, in rounds. In an online packing problem, the profit function as well as the packing constraints are not known in advance. In each round additional information (i.e., a new variable) about the profit function and the constraints is revealed. An online algorit...
-
作者：Salez, Justin; Shah, Devavrat
作者单位：Inria; Universite PSL; Ecole Normale Superieure (ENS); Massachusetts Institute of Technology (MIT)
摘要：The random assignment problem asks for the minimum-cost perfect matching in the complete n x n bipartite graph K-nn with i.i.d. edge weights, say uniform on [0, 1]. In a remarkable work by Aldous [Aldous, D. 2001. The zeta(2) limit in the random assignment problem. RSA 18 381-418], the optimal cost was shown to converge to zeta(2) as n -> infinity, as conjectured by Mezard and Parisi [Mezard, M., G. Parisi. 1987. On the solution of the random link matching problem. J. Phys. 48 1451-1459] throu...
-
作者：Cardaliaguet, Pierre; Rainer, Catherine
作者单位：Centre National de la Recherche Scientifique (CNRS); CNRS - National Institute for Mathematical Sciences (INSMI); Universite de Bretagne Occidentale
摘要：For zero-sum two-player continuous-time games with integral payoff and incomplete information on one side, the authors show that the optimal strategy of the informed player can be computed through an auxiliary optimization problem over some martingale measures. The authors also characterize the optimal martingale measures and compute them explicitly in several examples.
