1期

最新文章

• Worst-Case Examples for Lasserre's Measure-Based Hierarchy for Polynomial Optimization on the Hypercube AI翻译
  作者：de Klerk, Etienne; Laurent, Monique
  作者单位：Tilburg University; Delft University of Technology; Centrum Wiskunde & Informatica (CWI)
  摘要：We study the convergence rate of a hierarchy of upper bounds for polynomial optimization problems, proposed by Lasserre, and a related hierarchy by de Klerk, Hess, and Laurent. For polynomial optimization over the hypercube, we show a refined convergence analysis for the first hierarchy. We also show lower bounds on the convergence rate for both hierarchies on a class of examples. These lower bounds match the upper bounds and thus establish the true rate of convergence on these examples. Inter...
• Finding a Stable Allocation in Polymatroid Intersection AI翻译
  作者：Iwata, Satoru; Yokoi, Yu
  作者单位：University of Tokyo; Research Organization of Information & Systems (ROIS); National Institute of Informatics (NII) - Japan
  摘要：The stable matching (or stable marriage) model of Gale and Shapley [Gale D, Shapley LS (1962) College admissions and the stability of marriage. Amer. Math. Monthly 69(1):9 15.] has been generalized in various directions, such as matroid kernels by Fleiner [Fleiner T (2001) A matroid generalization of the stable matching polytope. Aardal K, Gerards AMH, eds. Proc. 8th Internat. Conf. Integer Programming Combin. Optim., Lecture Notes in Computer Science, vol. 2081 (Springer-Verlag, Berlin), 105-...
• On the Efficiency of Random Permutation for ADMM and Coordinate Descent AI翻译
  作者：Sun, Ruoyu; Luo, Zhi-Quan; Ye, Yinyu
  作者单位：University of Illinois System; University of Illinois Urbana-Champaign; University of Illinois System; University of Illinois Urbana-Champaign; The Chinese University of Hong Kong, Shenzhen; Shenzhen Research Institute of Big Data; Stanford University
  摘要：Random permutation is observed to be powerful for optimization algorithms: for multiblock ADMM (alternating direction method of multipliers), whereas the classical cyclic version diverges, the randomly permuted version converges in practice; for BCD (block coordinate descent), the randomly permuted version is typically faster than other versions. In this paper we provide strong theoretical evidence that random permutation has positive effects on ADMM and BCD, by analyzing randomly permuted ADM...
• The Euclidean k-Supplier Problem AI翻译
  作者：Nagarajan, Viswanath; Schieber, Baruch; Shachnai, Hadas
  作者单位：University of Michigan System; University of Michigan; International Business Machines (IBM); IBM USA; Technion Israel Institute of Technology
  摘要：The k-supplier problem is a fundamental location problem that involves opening k facilities to minimize the maximum distance of any client to an open facility. We consider the k-supplier problem in Euclidean metrics (of arbitrary dimension) and present an algorithm with approximation ratio 1 + root 3 < 2.74. This improves upon the previously known 3-approximation algorithm, which also holds for general metrics. Our result is almost best possible as the Euclidean k-supplier problem is NP-hard t...
• Nonzero-Sum Stochastic Differential Games with Impulse Controls: A Verification Theorem with Applications AI翻译
  作者：Aid, Rene; Basei, Matteo; Callegaro, Giorgia; Campi, Luciano; Vargiolu, Tiziano
  作者单位：Universite PSL; Universite Paris-Dauphine; University of California System; University of California Berkeley; University of Padua; University of London; London School Economics & Political Science
  摘要：We consider a general nonzero-sum impulse game with two players. The main mathematical contribution of this paper is a verification theorem that provides, under some regularity conditions, a suitable system of quasi-variational inequalities for the payoffs and the strategies of the two players at some Nash equilibrium. As an application, we study an impulse game with a one-dimensional state variable, following a real-valued scaled Brownian motion, and two players with linear and symmetric runn...
• An (Almost) Optimal Solution for Orthogonal Point Enclosure Query in R3 AI翻译
  作者：Rahul, Saladi
  作者单位：University of Illinois System; University of Illinois Urbana-Champaign
  摘要：The orthogonal point enclosure query (OPEQ) problem is a fundamental problem in the context of data management for modeling user preferences. Formally, preprocess a set S of n axis-aligned boxes (possibly overlapping) in R-d into a data structure so that the boxes in S containing a given query point q can be reported efficiently. In the pointer machine model, optimal solutions for the OPEQ in R-1 and R-2 were discovered in the 1980s: linear-space data structures that can answer the query in O(...
• The Computational Complexity of Integer Programming with Alternations AI翻译
  作者：Danny Nguyen; Pak, Igor
  作者单位：University of Michigan System; University of Michigan; University of California System; University of California Los Angeles
  摘要：We prove that integer programming with three alternating quantifiers is NP-complete, even for a fixed number of variables. This complements earlier results by Lenstra [16] [Lenstra H (1983) Integer programming with a fixed number of variables. Math. Oper. Res. 8(4):538-5481 and Kannan [13,14] [Kannan R (1990) Test sets for integer programs, for all there exists sentences. Polyhedral Combinatorics (American Mathematical Society, Providence, RI), 39-47. Kannan R (1992) Lattice translates of a po...
• Hiring Secretaries over Time: The Benefit of Concurrent Employment AI翻译
  作者：Disser, Yann; Fearnley, John; Gairing, Martin; Goebel, Oliver; Klimm, Max; Schmand, Daniel; Skopalik, Alexander; Toennis, Andreas
  作者单位：Technical University of Darmstadt; University of Liverpool; RWTH Aachen University; Humboldt University of Berlin; Goethe University Frankfurt; University of Twente; University of Bonn
  摘要：We consider a stochastic online problem where n applicants arrive over time, one per time step. Upon the arrival of each applicant, their cost per time step is revealed, and we have to fix the duration of employment, starting immediately. This decision is irrevocable; that is, we can neither extend a contract nor dismiss a candidate once hired. In every time step, at least one candidate needs to be under contract, and our goal is to minimize the total hiring cost, which is the sum of the appli...
• Random Serial Dictatorship: The One and Only AI翻译
  作者：Bade, Sophie
  作者单位：University of London; Royal Holloway University London; Max Planck Society
  摘要：Fix a Pareto-optimal, strategy-proof, and nonbossy deterministic matching mechanism and define a random matching mechanism by assigning agents to the roles in the mechanism via a uniform lottery. Given a profile of preferences, the lottery over outcomes that arises under the random matching mechanism is identical to the lottery that arises under random serial dictatorship, where the order of dictators is uniformly distributed. This result extends the celebrated equivalence between the core fro...
• Optimal Redeeming Strategy of Stock Loans Under Drift Uncertainty AI翻译
  作者：Xu, Zuo Quan; Yi, Fahuai
  作者单位：Hong Kong Polytechnic University; Guangdong University of Foreign Studies
  摘要：In practice, one must recognize the inevitable incompleteness of information while making decisions. In this paper, we consider the optimal redeeming problem of stock loans under a state of incomplete information presented by the uncertainty in the (bull or bear) trends of the underlying stock. This is called drift uncertainty. Owing to the unavoidable need for the estimation of trends while making decisions, the related Hamilton-Jacobi-Bellman equation turns out to be of a degenerate paraboli...