-
作者：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...
-
作者：Scavuzzo, Lara; Aardal, Karen; Lodi, Andrea; Yorke-Smith, Neil
作者单位：Delft University of Technology; Technion Israel Institute of Technology
摘要：Mixed Integer Linear Programming (MILP) is a pillar of mathematical optimization that offers a powerful modeling language for a wide range of applications. The main engine for solving MILPs is the branch-and-bound algorithm. Adding to the enormous algorithmic progress in MILP solving of the past decades, in more recent years there has been an explosive development in the use of machine learning for enhancing all main tasks involved in the branch-and-bound algorithm. These include primal heuris...
-
作者：Balkanski, Eric; Faenza, Yuri; Kubik, Mathieu
作者单位：Columbia University
摘要：Worst-case analysis is a performance measure that is often too pessimistic to indicate which algorithms we should use in practice. A classical example is in the context of the Euclidean Traveling Salesman Problem (TSP) in the plane, where local search performs very well in practice even though it only achieves an O ((log log n)/ (log n) ) worst case approximation ratio. In such cases, a natural alternative approach to worst-case analysis is to analyze the performance of algorithms in semi-rand...
-
作者：Del Pia, Alberto; Walter, Matthias
作者单位：University of Wisconsin System; University of Wisconsin Madison; University of Wisconsin System; University of Wisconsin Madison; University of Twente
摘要：We consider themultilinear polytope which arises naturally in binary polynomial optimization. Del Pia and Di Gregorio introduced the class of odd ss-cycle inequalities valid for this polytope, showed that these generally have Chvatal rank 2 with respect to the standard relaxation and that, together with flower inequalities, they yield a perfect formulation for cycle hypergraph instances. Moreover, they describe a separation algorithm in case the instance is a cycle hypergraph. We introduce a w...
-
作者：Helmberg, Christoph
作者单位：Technische Universitat Chemnitz
摘要：The conic bundle implementation of the spectral bundle method for large scale semidefinite programming solves in each iteration a semidefinite quadratic subproblem by an interior point approach. For larger cutting model sizes the limiting operation is collecting and factorizing a Schur complement of the primal-dual KKT system. We explore possibilities to improve on this by an iterative approach that exploits structural low rank properties. Two preconditioning approaches are proposed and analyz...
-
作者：Mathieu, Claire; Verdugo, Victor
作者单位：Universite Paris Cite; Universidad de O'Higgins
摘要：In the classic apportionment problem, the goal is to decide how many seats of a parliament should be allocated to each party as a result of an election. The divisor methods solve this problem by defining a notion of proportionality guided by some rounding rule. Motivated by recent challenges in the context of electoral apportionment, we consider the question of how to allocate the seats of a parliament under parity constraints between candidate types (e.g., an equal number of men and women ele...
