-
作者：Hao, Bainian; Michini, Carla
作者单位：University of Wisconsin System; University of Wisconsin Madison
摘要：We study the inefficiency of pure Nash equilibria in symmetric network congestion games defined over series-parallel networks with affine edge delays. For arbitrary networks, Correa (Math Oper Res 44(4):1286-1303, 2019) proved a tight upper bound of 5/2 on the PoA. On the other hand, for extension-parallel networks, a subclass of series-parallel networks, Fotakis (Theory Comput Syst 47:113-136, 2010) proved that the PoA is 4/3. He also showed that this bound is not valid for series-parallel ne...
-
作者：Soh, Yong Sheng; Varvitsiotis, Antonios
作者单位：National University of Singapore; Agency for Science Technology & Research (A*STAR); Agency for Science Technology & Research (A*STAR); A*STAR - Institute of High Performance Computing (IHPC); Singapore University of Technology & Design
摘要：Given a matrix X is an element of R-mxn (+) with non-negative entries, the cone factorization problem concerns computing {a(1),..., a(m)}subset of Kappa belonging to a convex cone K subset of R-k, and {b(1),..., b(n)}subset of K-* belonging to its dual so that X-i j = < a(i), b(j) > for all i is an element of [m], j is an element of [n]. Cone factorizations are fundamental to mathematical optimization as they allow us to express convex bodies as feasible regions of linear conic programs. In th...
-
作者：Aissi, Hassene; Mahjoub, A. Ridha
作者单位：Centre National de la Recherche Scientifique (CNRS); CNRS - Institute for Information Sciences & Technologies (INS2I); Universite PSL; Universite Paris-Dauphine; Kuwait University
摘要：We consider in this paper the budgeted minimum s - t cut problem. Suppose that we are given a directed graph G = (V, A) with two distinguished nodes s and t, k non-negative cost functions c(1),..., c(k) : A -> Z(+), and k - 1 budget bounds b(1),..., bk(-1). The goal is to find a s - t cut C satisfying the budget constraints c(h)(C) <= b(h), for h = 1,..., k-1, and whose cost c(k) (C) is minimum. In this paper we discuss the linear relaxation of the problem and introduce a strict partial orderi...
-
作者：Hanguir, Oussama; Ma, Will; Han, Jiangze; Ryan, Christopher Thomas
作者单位：Columbia University; Columbia University; University of British Columbia
摘要：We consider the problem of designing a linear program that has diverse solutions as the right-hand side varies. This problem arises in video game settings where designers aim to have players use different weapons or tactics as they progress. We model this design question as a choice over the constraint matrix A and cost vector c to maximize the number of possible supports of unique optimal solutions (what we call loadouts) of Linear Programs max{c inverted perpendicular x divided by Ax <= b,x ...
-
作者：Bin, Michelangelo; Notarnicola, Ivano; Parisini, Thomas
作者单位：University of Bologna; Imperial College London; University of Cyprus; University of Trieste
摘要：We consider the discrete-time Arrow-Hurwicz-Uzawa primal-dual algorithm, also known as the first-order Lagrangian method, for constrained optimization problems involving a smooth strongly convex cost and smooth convex constraints. We prove that, for every given compact set of initial conditions, there always exists a sufficiently small stepsize guaranteeing exponential stability of the optimal primal-dual solution of the problem with a domain of attraction including the initialization set. Ins...
-
作者：Beideman, Calvin; Chandrasekaran, Karthekeyan; Wang, Weihang
作者单位：University of Illinois System; University of Illinois Urbana-Champaign
摘要：We consider the problem of deterministically enumerating all minimum k-cut-sets in a given hypergraph for fixed constant k. The input here is a hypergraph G = (V, E) with non-negative hyperedge costs. A subset F subset of E of hyperedges is a k-cut-set if the number of connected components in G - F is at least k and it is a minimum k-cut-set if it has the least cost among all k-cut-sets. For fixed k, we call the problem of finding a minimum k-cut-set as Hypergraph- k- Cut and the problem of en...
-
作者：Mancinska, Laura; Roberson, David E.; Varvitsiotis, Antonios
作者单位：University of Copenhagen; Technical University of Denmark; Singapore University of Technology & Design
摘要：In the (G, H)-isomorphism game, a verifier interacts with two non-communicating players (called provers), by privately sending each of them a random vertex from either G or H. The goal of the players is to convince the verifier that the graphs G and H are isomorphic. In recent work along with Atserias et al. (J Comb Theory Ser B 136:89-328, 2019) we showed that a verifier can be convinced that two non-isomorphic graphs are isomorphic, if the provers are allowed to share quantum resources. In t...
-
作者：Khanh, Pham Duy; Mordukhovich, Boris S.; Phat, Vo Thanh; Tran, Dat Ba
作者单位：Wayne State University
摘要：This paper proposes and justifies two globally convergent Newton-type methods to solve unconstrained and constrained problems of nonsmooth optimization by using tools of variational analysis and generalized differentiation. Both methods are coderivative-based and employ generalized Hessians (coderivatives of subgradient mappings) associated with objective functions, which are either of class C1,1, or are represented in the form of convex composite optimization, where one of the terms may be ex...
-
作者：Piccialli, Veronica; Schwiddessen, Jan; Sudoso, Antonio M.
作者单位：Sapienza University Rome; University of Klagenfurt
摘要：Support vector machines (SVMs) are well-studied supervised learning models for binary classification. Large amounts of samples can be cheaply and easily obtained in many applications. What is often a costly and error-prone process is to label these data points manually. Semi-supervised support vector machines (S3VMs) extend the well-known SVM classifiers to the semi-supervised approach, aiming to maximize the margin between samples in the presence of unlabeled data. By leveraging both labeled ...
-
作者：Mirka, Renee; Smedira, Devin; Williamson, David P.
作者单位：Cornell University; Massachusetts Institute of Technology (MIT)
摘要：This paper considers the interplay between semidefinite programming, matrix rank, and graph coloring. Karger et al. (J ACM 45(2):246-265, 1998) give a vector program in which a coloring of a graph can be encoded as a semidefinite matrix of low rank. By complementary slackness conditions of semidefinite programming, if an optimal dual solution has high rank, any optimal primal solution must have low rank. We attempt to characterize graphs for which we can show that the corresponding dual optima...
