-
作者：Balkanski, Eric; Faenza, Yuri; Kubik, Mathieu
作者单位：Columbia University
摘要：Worst-case analysis is a performance measure that is often too pessimistic to indicate which algorithms we should use in practice. A classical example is in the context of the Euclidean Traveling Salesman Problem (TSP) in the plane, where local search performs very well in practice even though it only achieves an O ((log log n)/ (log n) ) worst case approximation ratio. In such cases, a natural alternative approach to worst-case analysis is to analyze the performance of algorithms in semi-rand...
-
作者：Del Pia, Alberto; Walter, Matthias
作者单位：University of Wisconsin System; University of Wisconsin Madison; University of Wisconsin System; University of Wisconsin Madison; University of Twente
摘要：We consider themultilinear polytope which arises naturally in binary polynomial optimization. Del Pia and Di Gregorio introduced the class of odd ss-cycle inequalities valid for this polytope, showed that these generally have Chvatal rank 2 with respect to the standard relaxation and that, together with flower inequalities, they yield a perfect formulation for cycle hypergraph instances. Moreover, they describe a separation algorithm in case the instance is a cycle hypergraph. We introduce a w...
-
作者：Helmberg, Christoph
作者单位：Technische Universitat Chemnitz
摘要：The conic bundle implementation of the spectral bundle method for large scale semidefinite programming solves in each iteration a semidefinite quadratic subproblem by an interior point approach. For larger cutting model sizes the limiting operation is collecting and factorizing a Schur complement of the primal-dual KKT system. We explore possibilities to improve on this by an iterative approach that exploits structural low rank properties. Two preconditioning approaches are proposed and analyz...
-
作者：Mathieu, Claire; Verdugo, Victor
作者单位：Universite Paris Cite; Universidad de O'Higgins
摘要：In the classic apportionment problem, the goal is to decide how many seats of a parliament should be allocated to each party as a result of an election. The divisor methods solve this problem by defining a notion of proportionality guided by some rounding rule. Motivated by recent challenges in the context of electoral apportionment, we consider the question of how to allocate the seats of a parliament under parity constraints between candidate types (e.g., an equal number of men and women ele...
-
作者：Ahookhosh, Masoud; Nesterov, Yurii
作者单位：University of Antwerp
-
作者：Correa, Jose; Cristi, Andres; Fielbaum, Andres; Pollner, Tristan; Weinberg, S. Matthew
作者单位：Universidad de Chile; Universidad de Chile; University of Sydney; Stanford University
摘要：We consider a fundamental pricing problem in combinatorial auctions. We are given a set of indivisible items and a set of buyers with randomly drawn monotone valuations over subsets of items. A decision-maker sets item prices and then the buyers make sequential purchasing decisions, taking their favorite set among the remaining items. We parametrize an instance by d, the size of the largest set a buyer may want. Our main result asserts that there exist prices such that the expected (over the r...
-
作者：Zong, Manru; Lee, Yin Tat; Yue, Man-Chung
作者单位：University of Hong Kong; University of Washington; University of Washington Seattle
摘要：Short-step methods are an important class of algorithms for solving convex constrained optimization problems. In this short paper, we show that under very mild assumptions on the self-concordant barrier and the width of the l(2)-neighbourhood, any short-step interior-point method is not strongly polynomial-time.
-
作者：Tokushige, Norihide
作者单位：University of the Ryukyus
摘要：Let g be a family of subsets of an n-element set. The family g is called non-trivial 3-wise intersecting if the intersection of any three subsets in g is non-empty, but the intersection of all subsets is empty. For a real number p ? (0, 1) we define the measure of the family by the sum of p(|G|)(1 - p)(n-|G|) over all G ? g. We determine the maximum measure of non-trivial 3-wise intersecting families. We also discuss the uniqueness and stability of the corresponding optimal structure. These re...
-
作者：Fomin, Fedor V. V.; Golovach, Petr A. A.; Panolan, Fahad; Philip, Geevarghese; Saurabh, Saket
作者单位：University of Bergen; Indian Institute of Technology System (IIT System); Indian Institute of Technology (IIT) - Hyderabad; Chennai Mathematical Institute; Institute of Mathematical Sciences (IMSc) India
摘要：We investigate the parameterized complexity of finding diverse sets of solutions to three fundamental combinatorial problems. The input to the WEIGHTED DIVERSE BASES problem consists of a matroid M, a weight function ? : E(M)-* N, and integers k > 1, d > 1. The task is to decide if there is a collection of k bases B-1, ... , B-k of M such that the weight of the symmetric difference of any pair of these bases is at least d. The input to the WEIGHTED DIVERSE COMMON INDEPENDENT SETS problem consi...
-
作者：Callejas, Ivonne; Govindan, Srihari; Pahl, Lucas
作者单位：University of Gottingen; University of Rochester; University of Bonn
摘要：Govindan and Klumpp [7] provided a characterization of perfect equilibria using Lexicographic Probability Systems (LPSs). Their characterization was essentially finite in that they showed that there exists a finite bound on the number of levels in the LPS, but they did not compute it explicitly. In this note, we draw on two recent developments in Real Algebraic Geometry to obtain a formula for this bound.
