-
作者：Boursier, Etienne; Perchet, Vianney
作者单位：Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne; Institut Polytechnique de Paris; ENSAE Paris
摘要：Strategic information is valuable either by remaining private (for instance if it is sensitive) or, on the other hand, by being used publicly to increase some utility. These two objectives are antagonistic and leaking this information by taking full advantage of it might be more rewarding than concealing it. Unlike classical solutions that focus on the first point, we consider instead agents that optimize a natural trade-off between both objectives. We formalize this as an optimization problem...
-
作者：Herings, P. Jean-Jacques; Zhan, Yang
作者单位：Tilburg University; Nanjing University; Nanjing University
摘要：One of the most important stability concepts for network formation is pairwise stability. We develop a homotopy algorithm that is effective in computing pairwise stable networks for a generic network formation problem. To do so, we reformulate the concept of pairwise stability as a Nash equilibrium of a non-cooperative game played by the links in the network and adapt the linear tracing procedure for non-cooperative games to the network formation problem. As a by-product of our main result, we...
-
作者：Thomae, Simon; Walther, Grit; Schiffer, Maximilian
作者单位：RWTH Aachen University; Technical University of Munich; Technical University of Munich
摘要：We study piecewise affine policies for multi-stage adjustable robust optimization (ARO) problems with non-negative right-hand side uncertainty. First, we construct new dominating uncertainty sets and show how a multi-stage ARO problem can be solved efficiently with a linear program when uncertainty is replaced by these new sets. We then demonstrate how solutions for this alternative problem can be transformed into solutions for the original problem. By carefully choosing the dominating sets, w...
-
作者：Liang, Jiaming; Guigues, Vincent; Monteiro, Renato D. C.
作者单位：University of Rochester; University of Rochester; Getulio Vargas Foundation; University System of Georgia; Georgia Institute of Technology
摘要：This paper considers optimization problems where the objective is the sum of a function given by an expectation and a closed convex function, and proposes stochastic composite proximal bundle (SCPB) methods for solving it. Complexity guarantees are established for them without requiring knowledge of parameters associated with the problem instance. Moreover, it is shown that they have optimal complexity when these problem parameters are known. To the best of our knowledge, this is the first pro...
-
作者：Hirayama, Tsuyoshi; Liu, Yuhao; Makino, Kazuhisa; Shi, Ke; Xu, Chao
作者单位：University of Electronic Science & Technology of China; Kyoto University
摘要：In this paper, we study the minimum k-partition problem of submodular functions, i.e., given a finite set V and a submodular function f : 2(V) -> R, computing a k-partition {V-1, ... , V-k} of V with minimum Sigma k(i=1) f(V-i). The problem is a natural generalization of the minimum k-cut problem in graphs and hypergraphs. It is known that the problem is NP-hard for general k, and solvable in polynomial time for fixed k <= 3. In this paper, we construct the first polynomial-time algorithm for ...
-
作者：Neuwohner, Meike
作者单位：University of Bonn
摘要：We consider the weighted k-set packing problem, where, given a collection S of sets, each of cardinality at most k, and a positive weight function w : S -> Q(>0), the task is to find a sub-collection of S consisting of pairwise disjoint sets of maximum total weight. As this problem does not permit a polynomial-time o( k/ log k )-approximation unless P = N P (Hazan et al. in Comput Complex 15:20-39, 2006. https://doi.org/ 10.1007/s00037-006-0205-6), most previous approaches rely on local search...
-
作者：Josz, Cedric; Lai, Lexiao
作者单位：Columbia University
摘要：We consider first-order methods with constant step size for minimizing locally Lipschitz coercive functions that are tame in an o-minimal structure on the real field. We prove that if the method is approximated by subgradient trajectories, then the iterates eventually remain in a neighborhood of a connected component of the set of critical points. Under suitable method-dependent regularity assumptions, this result applies to the subgradient method with momentum, the stochastic subgradient meth...
-
作者：Boyd, Sylvia; Cheriyan, Joseph; Haddadan, Arash; Ibrahimpur, Sharat
作者单位：University of Ottawa; University of Waterloo; Amazon.com; University of London; London School Economics & Political Science
摘要：We present approximation algorithms for several network design problems in the model of flexible graph connectivity (Adjiashvili et al., in: IPCO, pp 13-26, 2020, Math Program 1-33, 2021). Let k >== 1, p >= 1 and q >= 0 be integers. In an instance of the ( p, q)-Flexible Graph Connectivity problem, denoted ( p, q)-FGC, we have an undirected connected graph G = (V, E), a partition of E into a set of safe edges l and a set of unsafe edges U, and nonnegative costs c : E -> R(>=)0 on the edges. A ...
-
作者：Igarashi, Ayumi; Zwicker, William S.
作者单位：Research Organization of Information & Systems (ROIS); National Institute of Informatics (NII) - Japan; Union College; Istanbul Bilgi University; CY Cergy Paris Universite
摘要：Fair division has been studied in both continuous and discrete contexts. One strand of the continuous literature seeks to award each agent with a single connected piece-a subinterval. The analogue for the discrete case corresponds to the fair division of a graph, where allocations must be contiguous so that each bundle of vertices is required to induce a connected subgraph. With envy-freeness up to one item (EF1) as the fairness criterion, however, positive results for three or more agents hav...
-
作者：Edelman, Paul H.; Van der Linden, Martin; Weymark, John A.
作者单位：Vanderbilt University; Vanderbilt University; Emory University; Vanderbilt University
摘要：The core of a monotonic transferable utility (TU) game is shown to be the set of prices that incentivize each individual to demand the grand coalition in a market demand problem in which the goods being demanded are coalitions viewed as excluable public goods. It is also shown that the core is the intersection of superdifferentials evaluated at the grand coalition of the covers of person-specific TU games derived from the original game. These characterizations of the core demonstrate how a mar...
