-
作者：Cornuejols, Gerard; Lee, Dabeen; Li, Yanjun
作者单位：Carnegie Mellon University; Purdue University System; Purdue University
摘要：We study the following problem: given a rational polytope with Chvatal rank 1, does it contain an integer point? Boyd and Pulleyblank observed that this problem is in the complexity class NP boolean AND\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\cap $$\end{document} co-NP, an indication that it is probably not...
-
作者：Buchbinder, Niv; Feldman, Moran; Filmus, Yuval; Garg, Mohit
作者单位：Tel Aviv University; Open University Israel; Technion Israel Institute of Technology; University of Haifa; Universita della Svizzera Italiana
摘要：The Submodular Welfare Maximization problem (SWM) captures an important subclass of combinatorial auctions and has been studied extensively. In particular, it has been studied in a natural online setting in which items arrive one-by-one and should be allocated irrevocably upon arrival. For this setting, Korula et al. (SIAM J Comput 47(3):1056-1086, 2018) were able to show that the greedy algorithm is 0.5052-competitive when the items arrive in a uniformly random order. Unfortunately, however, ...
-
作者：Yang, Wenzhuo; Sim, Melvyn; Xu, Huan
作者单位：National University of Singapore; National University of Singapore; University System of Georgia; Georgia Institute of Technology
摘要：Motivated by the binary classification problem in machine learning, we study in this paper a class of decision problems where the decision maker has a list of goals, from which he aims to attain the maximal possible number of goals. In binary classification, this essentially means seeking a prediction rule to achieve the lowest probability of misclassification, and computationally it involves minimizing a (difficult) non-convex, 0-1 loss function. To address the intractability, previous method...
-
作者：Mehlitz, Patrick
作者单位：Brandenburg University of Technology Cottbus
摘要：In optimal control, switching structures demanding at most one control to be active at any time instance appear frequently. Discretizing such problems, a so-called mathematical program with switching constraints is obtained. Although these problems are related to other types of disjunctive programs like optimization problems with complementarity or vanishing constraints, their inherent structure makes a separate consideration necessary. Since standard constraint qualifications are likely to fa...
-
作者：Kronqvist, Jan; Bernal, David E.; Grossmann, Ignacio E.
作者单位：Abo Akademi University; Carnegie Mellon University
摘要：In this paper, we present two new methods for solving convex mixed-integer nonlinear programming problems based on the outer approximation method. The first method is inspired by the level method and uses a regularization technique to reduce the step size when choosing new integer combinations. The second method combines ideas from both the level method and the sequential quadratic programming technique and uses a second order approximation of the Lagrangean when choosing the new integer combi...
-
作者：Kroer, Christian; Waugh, Kevin; Kilinc-Karzan, Fatma; Sandholm, Tuomas
作者单位：Carnegie Mellon University; University of Alberta; Carnegie Mellon University
摘要：Sparse iterative methods, in particular first-order methods, are known to be among the most effective in solving large-scale two-player zero-sum extensive-form games. The convergence rates of these methods depend heavily on the properties of the distance-generating function that they are based on. We investigate both the theoretical and practical performance improvement of first-order methods (FOMs) for solving extensive-form games through better design of the dilated entropy function-a class ...
-
作者：Shen, Xiangkun; Nagarajan, Viswanath
作者单位：University of Michigan System; University of Michigan
摘要：We consider fractional online covering problems withlq-norm objectives as well as its dual packing problems. The problem of interest is of the formmin{f(x):Ax >= 1,x >= 0}wheref(x)= n-ary sumation ece||x(Se)||qeis the weighted sum oflq-norms andAis a non-negative matrix. The rows ofA(i.e. covering constraints) arrive online over time. We provide an onlineO(logd+log rho)-competitive algorithm where rho=amaxaminanddis the maximum of the row sparsity ofAandmax|Se|This is based on the online prima...
-
作者：van Beesten, E. Ruben; Romeijnders, Ward
作者单位：University of Groningen
摘要：In traditional two-stage mixed-integer recourse models, the expected value of the total costs is minimized. In order to address risk-averse attitudes of decision makers, we consider a weighted mean-risk objective instead. Conditional value-at-risk is used as our risk measure. Integrality conditions on decision variables make the model non-convex and hence, hard to solve. To tackle this problem, we derive convex approximation models and corresponding error bounds, that depend on the total varia...
-
作者：Berczi, Kristof; Chandrasekaran, Karthekeyan; Kiraly, Tamas; Madan, Vivek
作者单位：Eotvos Lorand University; University of Illinois System; University of Illinois Urbana-Champaign; University System of Georgia; Georgia Institute of Technology
摘要：In the multiway cut problem, we are given an undirected graph with non-negative edge weights and a collection of k terminal nodes, and the goal is to partition the node set of the graph into k non-empty parts each containing exactly one terminal, so that the total weight of the edges crossing the partition is minimized. The multiway cut problem for k >= 3 is APX-hard. For arbitrary k, the best-known approximation factor is 1.2965 due to Sharma and Vondrak (Proceedings of the forty-sixth annual...
-
作者：Li, Xudong; Sun, Defeng; Toh, Kim-Chuan
作者单位：Fudan University; Hong Kong Polytechnic University; National University of Singapore; National University of Singapore
摘要：We derive an explicit formula, as well as an efficient procedure, for constructing a generalized Jacobian for the projector of a given square matrix onto the Birkhoff polytope, i.e., the set of doubly stochastic matrices. To guarantee the high efficiency of our procedure, a semismooth Newton method for solving the dual of the projection problem is proposed and efficiently implemented. Extensive numerical experiments are presented to demonstrate the merits and effectiveness of our method by com...
