-
作者：Hunkenschroeder, Christoph
作者单位：Technical University of Berlin
摘要：We show that the problem of deciding whether a given Euclidean lattice L has an orthonormal basis is in NP and co-NP. Since this is equivalent to saying that L is isomorphic to the standard integer lattice, this problem is a special form of the lattice isomorphism problem, which is known to be in the complexity class SZK. We achieve this by deploying a result on characteristic vectors by Elkies that gained attention in the context of 4-manifolds and Seiberg-Witten equations, but seems rather u...
-
作者：Tian, Lai; So, Anthony Man-Cho
作者单位：Chinese University of Hong Kong
摘要：We consider the oracle complexity of computing an approximate stationary point of a Lipschitz function. When the function is smooth, it is well known that the simple deterministic gradient method has finite dimension-free oracle complexity. However, when the function can be nonsmooth, it is only recently that a randomized algorithm with finite dimension-free oracle complexity has been developed. In this paper, we show that no deterministic algorithm can do the same. Moreover, even without the ...
-
作者：Kannan, Rohit; Bayraksan, Guezin; Luedtke, James R.
作者单位：Virginia Polytechnic Institute & State University; University System of Ohio; Ohio State University; University of Wisconsin System; University of Wisconsin Madison; University of Wisconsin System; University of Wisconsin Madison
摘要：We consider data-driven approaches that integrate a machine learning prediction model within distributionally robust optimization (DRO) given limited joint observations of uncertain parameters and covariates. Our framework is flexible in the sense that it can accommodate a variety of regression setups and DRO ambiguity sets. We investigate asymptotic and finite sample properties of solutions obtained using Wasserstein, sample robust optimization, and phi-divergence-based ambiguity sets within ...
-
作者：Joyce, Alexander; Yang, Boshi
作者单位：Clemson University
摘要：Let F subset of R-n be a nonempty closed set. Understanding the structure of the closed convex hull (C) over bar (F) := <(conv{over bar>{( x, xx(T))|x is an element of F} in the lifted space is crucial for solving quadratic programs related to F. This paper discusses the relationship between C(F) and (C) over bar (G), where G results by adding non-intersecting quadratic constraints to F. We prove that C(G) can be represented as the intersection of C(F) and half spaces defined by the added cons...
-
作者：Guenin, Bertrand; Heo, Cheolwon
作者单位：University of Waterloo; Korea Institute for Advanced Study (KIAS)
摘要：Even-cycle matroids are elementary lifts of graphic matroids. An even-cycle matroid is pinch-graphic if it has a signed-graph representation with a blocking pair. We present a polynomial algorithm to check if an internally 4-connected binary matroid is pinch-graphic. Combining this with a result in Guenin and Heo (Small separations in pinch-graphic matroids. Math Program (2023). https://doi.org/10.1007/s10107-023-01950-8) this allows us to check, in polynomial time, if an arbitrary binary matr...
-
作者：Lodi, Andrea; Olivier, Philippe; Pesant, Gilles; Sankaranarayanan, Sriram
作者单位：Universite de Montreal; Polytechnique Montreal; Universite de Montreal; Polytechnique Montreal; Indian Institute of Management (IIM System); Indian Institute of Management Ahmedabad
摘要：Decision making problems are typically concerned with maximizing efficiency. In contrast, we address problems where there are multiple stakeholders and a centralized decision maker who is obliged to decide in a fair manner. Different decisions give different utility to each stakeholder. In cases where these decisions are made repeatedly, we provide efficient mathematical programming formulations to identify both the maximum fairness possible and the decisions that improve fairness over time, f...
-
作者：Sanchez-Fernandez, Luis; Fernandez-Garcia, Norberto; Fisteus, Jesus A.; Brill, Markus
作者单位：Universidad Carlos III de Madrid; Universidad Carlos III de Madrid; Technical University of Berlin
摘要：We propose the maximin support method, a novel extension of the D'Hondt apportionment method to approval-based multiwinner elections. The maximin support method is a sequential procedure that aims to maximize the voter support of the least supported elected candidate. It can be computed efficiently and satisfies (adjusted versions of) the main properties of the original D'Hondt method: house monotonicity, population monotonicity, and proportional representation. We also establish a close relat...
-
作者：Aardal, Karen; Sanita, Laura
作者单位：Delft University of Technology; Bocconi University
-
作者：Zeng, Liaoyuan; Zhang, Yongle; Li, Guoyin; Pong, Ting Kei; Wang, Xiaozhou
作者单位：Zhejiang University of Technology; Sichuan Normal University; University of New South Wales Sydney; Hong Kong Polytechnic University
摘要：The Frank-Wolfe (FW) method, which implements efficient linear oracles that minimize linear approximations of the objective function over a fixed compact convex set, has recently received much attention in the optimization and machine learning literature. In this paper, we propose a new FW-type method for minimizing a smooth function over a compact set defined as the level set of a single difference-of-convex function, based on new generalized linear-optimization oracles (LO). We show that the...
-
作者：Qi, Yunwei; Sen, Suvrajeet
作者单位：University System of Ohio; Ohio State University; University of Southern California
