-
作者：Del Pia, Alberto; Khajavirad, Aida; Kunisky, Dmitriy
作者单位：University of Wisconsin System; University of Wisconsin Madison; University of Wisconsin System; University of Wisconsin Madison; Lehigh University; Yale University
摘要：The problem of community detection with two equal-sized communities is closely related to the minimum graph bisection problem over certain random graph models. In the stochastic block model distribution over networks with community structure, a well-known semidefinite programming (SDP) relaxation of the minimum bisection problem recovers the underlying communities whenever possible. Motivated by their superior scalability, we study the theoretical performance of linear programming (LP) relaxat...
-
作者：Gravin, Nick; Wang, Hongao
作者单位：Shanghai University of Finance & Economics; Purdue University System; Purdue University
摘要：We consider the Bayesian online selection problem of a matching in bipartite graphs, that is, the weighted online matching problem where the edges arrive online and edge weights are generated from a known distribution. This setting corresponds to the intersection of two matroids in the work of Kleinberg and Weinberg [40] and Feldman et al. [27]. We study a simple class of nonadaptive policies that we call vertex-additive policies. A vertex-additive policy assigns static prices to every vertex ...
-
作者：Mai, Ngoc Hoang Anh; Magron, Victor; Lasserre, Jean
作者单位：Centre National de la Recherche Scientifique (CNRS)
摘要：If f is a positive definite form, Reznick's Positivstellensatz states that there exists k is an element of N such that parallel to x parallel to(2k)(2)f is a sum of squares of polynomials. Assuming that f can be written as a sumof forms Sigma(p)(l=1) f(l), where each fl depends on a subset of the initial variables, and assuming that these subsets satisfy the so-called running intersection property, we provide a sparse version of Reznick's Positivstellensatz. Namely, there exists k is an elemen...
-
作者：Lin, Tianyi; Jordan, Michael I.
作者单位：University of California System; University of California Berkeley; University of California System; University of California Berkeley
摘要：We propose and analyze a new dynamical system with a closed-loop control law in a Hilbert space H, aiming to shed light on the acceleration phenomenon for monotone inclusion problems, which unifies a broad class of optimization, saddle point, and variational inequality (VI) problems under a single framework. Given an operator A : H paired right arrows H that is maximal monotone, we propose a closed-loop control system that is governed by the operator I - (I + lambda(t)A)(-1), where a feedback ...
-
作者：Braun, Alexander; Kesselheim, Thomas
作者单位：University of Bonn
摘要：We design novel mechanisms for welfare maximization in two-sided markets. That is, there are buyers willing to purchase items and sellers holding items initially, both acting rationally and strategically in order to maximize utility. Our mechanisms are designed based on a powerful correspondence between two-sided markets and prophet inequalities. They satisfy individual rationality, dominant-strategy incentive compatibility, and budget balance constraints and give constant factor approximation...
-
作者：Lacker, Daniel; Soret, Agathe
作者单位：Columbia University
摘要：This paper studies stochastic games on large graphs and their graphon limits. We propose a new formulation of graphon games based on a single typical player's label state distribution. In contrast, other recently proposed models of graphon games work directly with a continuum of players, which involves serious measure-theoretic technicalities. In fact, by viewing the label as a component of the state process, we show in our formulation that graphon games are a special case of mean field games,...
-
作者：El Balghiti, Othman; Elmachtoub, Adam N.; Grigas, Paul; Tewari, Ambuj
作者单位：Columbia University; University of California System; University of California Berkeley; University of Michigan System; University of Michigan
摘要：The predict-then-optimize framework is fundamental in many practical settings: predict the unknown parameters of an optimization problem and then solve the problem using the predicted values of the parameters. A natural loss function in this environment is to consider the cost of the decisions induced by the predicted parameters in contrast to the prediction error of the parameters. This loss function is referred to as the smart predict then-optimize (SPO) loss. In this work, we seek to provid...
-
作者：Gutekunst, Samuel C.; Williamson, David P.
作者单位：Bucknell University; Bucknell University; Cornell University
摘要：Facet-defining inequalities of the symmetric traveling salesman problem (TSP) polytope play a prominent role in both polyhedral TSP research and state-of-the-art TSP solvers. In this paper, we introduce a new class of facet-defining inequalities, the circlet inequalities. These inequalities were first conjectured in Gutekunst and Williamson [Gutekunst SC, Williamson DP (2019) Characterizing the integrality gap of the subtour LP for the circulant traveling salesman problem. SIAM J. Discrete Mat...
-
作者：Clarkson, Jake; Lin, Kyle Y.; Glazebrook, Kevin D.
作者单位：Lancaster University; United States Department of Defense; United States Navy; Naval Postgraduate School; Lancaster University
摘要：Consider a two-person zero-sum search game between a hider and a searcher. The hider hides among n discrete locations, and the searcher successively visits individual locations until finding the hider. Known to both players, a search at location i takes t(i) time units and detects the hider-if hidden there-independently with probability alpha(i) for i = 1, ..., n. The hider aims to maximize the expected time until detection, whereas the searcher aims to minimize it. We prove the existence of a...
-
作者：Guan, Chonghu; Xu, Zuo Quan; Zhou, Rui
作者单位：Hong Kong Polytechnic University
摘要：This paper studies a dynamic optimal reinsurance and dividend-payout problem for an insurance company in a finite time horizon. The goal of the company is to maximize the expected cumulative discounted dividend payouts until bankruptcy or maturity, whichever comes earlier. The company is allowed to buy reinsurance contracts dynamically over the whole time horizon to cede its risk exposure with other reinsurance companies. This is a mixed singular-classical stochastic control problem, and the c...
