-
作者：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.
-
作者：Munoz, Gonzalo; Paat, Joseph; Xavier, Alinson S.
作者单位：Universidad de O'Higgins; University of British Columbia; United States Department of Energy (DOE); Argonne National Laboratory
摘要：A branch-and-bound (BB) tree certifies a dual bound on the value of an integer program. In this work, we introduce the tree compression problem (TCP): Given a BB treeTthat certifies a dual bound, can we obtain a smaller tree with the same (or stronger) bound by either (1) applying a different disjunction at some node inTor (2) removing leaves fromT? We believe such post-hoc analysis of BB trees may assist in identifying helpful general disjunctions in BB algorithms. We initiate our study by co...
-
作者：Khalife, Sammy; Cheng, Hongyu; Basu, Amitabh
作者单位：Johns Hopkins University
摘要：In this article we present new results on neural networks with linear threshold activation functions x?1({x>0}).We precisely characterize the class of functions that are representable by such neural networks and show that 2 hidden layers are necessary and sufficient to represent any function representable in the class. This is a surprising result in the light of recent exact representability investigations for neural networks using other popular activation functions like rectified linear units...
-
作者：Gaar, Elisabeth; Lee, Jon; Ljubic, Ivana; Sinnl, Markus; Taninmis, Kuebra
作者单位：Johannes Kepler University Linz; Johannes Kepler University Linz; University of Michigan System; University of Michigan; ESSEC Business School
摘要：We study a class of integer bilevel programs with second-order cone constraints at the upper-level and a convex-quadratic objective function and linear constraints at the lower-level. We develop disjunctive cuts (DCs) to separate bilevel-infeasible solutions using a second-order-cone-based cut-generating procedure. We propose DC separation strategies and consider several approaches for removing redundant disjunctions and normalization. Using these DCs, we propose a branch-and-cut algorithm for...
-
作者：Aziz, Haris; Li, Bo; Wu, Xiaowei
作者单位：University of New South Wales Sydney; Hong Kong Polytechnic University; University of Macau
摘要：We initiate the work on maximin share (MMS) fair allocation of m indivisible chores to n agents using only their ordinal preferences, from both algorithmic and mechanism design perspectives. The previous best-known approximation ratio using ordinal preferences is 2 - 1/n by Aziz et al. [AAAI 2017]. We improve this result by giving a deterministic 5/3-approximation algorithm that determines an allocation sequence of agents, according to which items are allocated one by one. By a tighter analysi...
