-
作者：Chen, Rui; Zhu, Haoran
作者单位：The Chinese University of Hong Kong, Shenzhen; Microsoft
摘要：The complexity class Dp is the class of all languages that are the intersection of a language in NP and a language in co-NP. It was conjectured that recognizing a facet for the knapsack polytope is Dp-complete. We provide a positive answer to this conjecture. Moreover, despite the Dp-hardness of the recognition problem, we give a polynomial-time algorithm for deciding if an inequality with a fixed number of distinct coefficients defines a facet of a knapsack polytope.
-
作者：Csaji, Gergely; Kiraly, Tamas; Yokoi, Yu
作者单位：Eotvos Lorand University; Eotvos Lorand University; Institute of Science Tokyo
摘要：This paper considers the problem of finding maximum-size stable matchings in the presence of ties, a well-known NP-hard problem, by extending the existing 32-approximation algorithm to a common generalization of many previously studied and newly introduced models. These include the existence of critical agents, where matching as many of these agents as possible is prioritized; free edges that cannot be blocking edges; and triangle-stabilities, which mean that for an edge to block, the improvem...
-
作者：Chen, Xiaochen; Guan, Guohui; Liang, Zongxia
作者单位：Tsinghua University; Renmin University of China; Renmin University of China
摘要：This paper investigates portfolio selection within a continuous-time financial market with regime switching and beliefs-dependent utilities. The market coefficients and the investor's utility function both depend on the market regime, which is modeled by an observable finite-state continuous-time Markov chain. The optimization problem is formulated by aggregating expected certainty equivalents under different regimes, leading to time inconsistency. Utilizing the equilibrium strategy, we derive...
-
作者：Ghosal, Promit; Nutz, Marcel
作者单位：University of Chicago; Columbia University
摘要：We study Sinkhorn's algorithm for solving the entropically regularized optimal transport problem. Its iterate pi t is shown to satisfy H(pi t|pi*) + H(pi*|pi t) = O(t(-1)), where H denotes relative entropy and pi* denotes the optimal coupling. This holds for a large class of cost functions and marginals, including quadratic cost with sub-Gaussian marginals. We also obtain the rate O(t(-1)) for the dual suboptimality and O(t(-2)) for the marginal entropies. More precisely, we derive nonasymptot...
-
作者：Li, Hanyang; Cui, Ying
作者单位：University of California System; University of California Berkeley
摘要：We investigate a class of composite nonconvex functions, where the outer function is the sum of univariate extended-real-valued convex functions and the inner function is the limit of difference-of-convex functions. A notable feature of this class is that the inner function may fail to be locally Lipschitz continuous. It covers a range of important, yet challenging, applications, including inverse optimal value optimization and problems under value-at-risk constraints. We propose an asymptotic...
-
作者：Grand-Clement, Julien; Vieille, Nicolas
作者单位：Hautes Etudes Commerciales (HEC) Paris; Hautes Etudes Commerciales (HEC) Paris
摘要：This paper investigates properties of Blackwell s-optimal strategies in zero-sum stochastic games when the adversary is restricted to stationary strategies, motivated by applications to robust Markov decision processes. For a class of absorbing games (including generalized Big Match games), we show that Markovian Blackwell s-optimal strategies may fail to exist, yet we prove the existence of Blackwell s-optimal strategies that can be implemented by a two-state automaton whose internal transiti...
-
作者：Kawase, Yasushi; Nishimura, Koichi; Sumita, Hanna
作者单位：University of Tokyo
摘要：We study the problem of minimizing a given symmetric strictly convex function over the Minkowski sum of an integral base-polyhedron and an M-convex set. This problem has a hybrid of continuous and discrete structures. This relates to allocating mixed goods, consisting of both divisible and indivisible goods, to agents with binary valuations so that the fairness measure, such as the Nash welfare, is maximized. Integral basepolyhedra and M-convex sets have similar and nice properties, and the no...
-
作者：Luke, D. Russell; Tam, Matthew K.
作者单位：University of Gottingen; University of Melbourne
摘要：We study the proximal point algorithm when the operator of interest is metrically subregular and satisfies a submonotonicity property. The latter property can be viewed as a quantified weakening of the standard definition of a monotone operator. Our main result gives a condition under which locally, the proximal point algorithm generates sequences that are linearly convergent to a zero of the underlying operator. General properties of our notion of submonotonicity are also explored as well as ...
-
作者：Friggstad, Zachary; Mousavi, Ramin; Rahgoshay, Mirmahdi; Salavatipour, Mohammad R.
作者单位：University of Alberta
摘要：In this paper, we present improved approximation algorithms for the (unsplitta-ble) capacitated vehicle routing problem (CVRP) in general metrics. In the CVRP, we are given a set of points (clients) V together with a depot r in a metric space, with each v is an element of V having a demand d(v) > 0 and a vehicle of bounded capacity Q. The goal is to find a mini-mum cost collection of tours for the vehicle, each starting and ending at the depot, such that each client is visited at least once an...
-
作者：Fan, Yanqin; Park, Hyeonseok; Xua, Gaoqian
作者单位：University of Washington; University of Washington Seattle; Dongbei University of Finance & Economics; Dongbei University of Finance & Economics
摘要：This paper studies distributional model risk in marginal problems, where each marginal measure is assumed to lie in a Wasserstein ball. We establish fundamental results including strong duality, finiteness of the proposed Wasserstein distributional model risk, and the existence of an optimizer at each radius. We also show continuity of the Wasserstein distributional model risk as a function of the radius. Using strong duality, we extend the well-known Makarov bounds for the distribution functi...
