-
作者：Bertsimas, Dimitris; den Hertog, Dick; Pauphilet, Jean; Zhen, Jianzhe
作者单位：Massachusetts Institute of Technology (MIT); University of Amsterdam; University of London; London Business School
摘要：Robust convex constraints are difficult to handle, since finding the worst-case scenario is equivalent to maximizing a convex function. In this paper, we propose a new approach to deal with such constraints that unifies most approaches known in the literature and extends them in a significant way. The extension is either obtaining better solutions than the ones proposed in the literature, or obtaining solutions for classes of problems unaddressed by previous approaches. Our solution is based o...
-
作者：Nam Ho-Nguyen; Wright, Stephen J.
作者单位：University of Sydney; University of Wisconsin System; University of Wisconsin Madison
摘要：We study a model for adversarial classification based on distributionally robust chance constraints. We show that under Wasserstein ambiguity, the model aims to minimize the conditional value-at-risk of the distance to misclassification, and we explore links to adversarial classification models proposed earlier and to maximum-margin classifiers. We also provide a reformulation of the distributionally robust model for linear classification, and show it is equivalent to minimizing a regularized ...
-
作者：Dey, Santanu; Singh, Mohit; Williamson, David P.
作者单位：University System of Georgia; Georgia Institute of Technology; Cornell University
-
作者：Cui, Shisheng; Shanbhag, Uday, V; Yousefian, Farzad
作者单位：Pennsylvania Commonwealth System of Higher Education (PCSHE); Pennsylvania State University; Pennsylvania State University - University Park; Rutgers University System; Rutgers University New Brunswick
摘要：Mathematical programs with equilibrium constraints (MPECs) represent a class of hierarchical programs that allow for modeling problems in engineering, economics, finance, and statistics. While stochastic generalizations have been assuming increasing relevance, there is a pronounced absence of efficient first/zeroth-order schemes with non-asymptotic rate guarantees for resolving even deterministic variants of such problems. We consider a subclass of stochastic MPECs (SMPECs) where the parametri...
-
作者：Cartis, Coralia; Massart, Estelle; Otemissov, Adilet
作者单位：Alan Turing Institute; University of Oxford; National Physical Laboratory - UK; Nazarbayev University
摘要：We propose a random-subspace algorithmic framework for global optimization of Lipschitz-continuous objectives, and analyse its convergence using novel tools from conic integral geometry. X-REGO randomly projects, in a sequential or simultaneous manner, the high-dimensional original problem into low-dimensional subproblems that can then be solved with any global, or even local, optimization solver. We estimate the probability that the randomly-embedded subproblem shares (approximately) the same...
-
作者：Carr, Robert; Ravi, R.; Simonetti, Neil
作者单位：University of New Mexico; Carnegie Mellon University
摘要：In the Traveling Salesman Problem (TSP), a salesman wants to visit a set of cities and return home. There is a cost c(ij) of traveling from city i to city j, which is the same in either direction for the Symmetric TSP. The objective is to visit each city exactly once, minimizing total travel costs. In the Graphical TSP, a city may be visited more than once, which may be necessary on a sparse graph. We present a new integer programming formulation for the Graphical TSP requiring only two classe...
-
作者：Garg, Paritosh; Jordan, Linus; Svensson, Ola
作者单位：Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne
摘要：While the basic greedy algorithm gives a semi-streaming algorithm with an approximation guarantee of 2 for the unweighted matching problem, it was only recently that Paz and Schwartzman obtained an analogous result for weighted instances. Their approach is based on the versatile local ratio technique and also applies to generalizations such as weighted hypergraph matchings. However, the framework for the analysis fails for the related problem of weighted matroid intersection and as a result th...
-
作者：Babecki, Catherine; Thomas, Rekha R.
作者单位：University of Washington; University of Washington Seattle
摘要：A graphical design is a subset of graph vertices such that the weighted averages of certain graph eigenvectors over the design agree with their global averages. We use Gale duality to show that positively weighted graphical designs in regular graphs are in bijection with the faces of a generalized eigenpolytope of the graph. This connection can be used to organize, compute and optimize designs. We illustrate the power of this tool on three families of Cayley graphs - cocktail party graphs, cyc...
-
作者：Buchbinder, Niv; Coester, Christian; Naor, Joseph
作者单位：Tel Aviv University; University of Sheffield; Technion Israel Institute of Technology
摘要：We consider the online k-taxi problem, a generalization of the k-server problem, in which k servers are located in a metric space. A sequence of requests is revealed one by one, where each request is a pair of two points, representing the start and destination of a travel request by a passenger. The goal is to serve all requests while minimizing the distance traveled without carrying a passenger. We show that the classic Double Coverage algorithm has competitive ratio 2(k) - 1 on HSTs, matchin...
-
作者：Faenza, Yuri; Zhang, Xuan
作者单位：Columbia University
摘要：Birkhoff's representation theorem (Birkhoff, Duke Math J 3(3):443-454, 1937) defines a bijection between elements of a distributive lattice and the family of upper sets of an associated poset. Although not used explicitly, this result is at the backbone of the combinatorial algorithm by Irving et al. (J ACM 34(3):532-543, 1987) for maximizing a linear function over the set of stable matchings in Gale and Shapley's stable marriage model (Gale and Shapley, Am Math Monthly 69(1):9-15 1962). In th...
