We consider fast algorithms for monotone submodular maximization subject to a matroid constraint. We assume that the matroid is given as input in an explicit form, and the goal is to obtain the best possible running times for important matroids. We develop a new algorithm for a general matroid constraint with a $1  1/e  \epsilon$ approximation that achieves a fast running time provided we have a fast data structure for maintaining an approximately maximum weight base in the matroid through a sequence of decrease weight operations. We construct such data structures for graphic matroids and partition matroids, and we obtain the first algorithms for these classes of matroids that achieve a nearlyoptimal, $1  1/e  \epsilon$ approximation, using a nearlylinear number of function evaluations and arithmetic operations.
more »
« less
This content will become publicly available on January 7, 2025
Faster exact and approximation algorithms for packing and covering matroids via pushrelabel
Matroids are a fundamental object of study in combinatorial optimization. Three closely related and important problems involving matroids are maximizing the size of the union of $k$ independent sets (that is, \emph{$k$fold matroid union}), computing $k$ disjoint bases (a.k.a.\ \emph{matroid base packing}), and covering the elements by $k$ bases (a.k.a.\ \emph{matroid base covering}). These problems generalize naturally to integral and realvalued capacities on the elements. This work develops faster exact and/or approximation problems for these and some other closely related problems such as optimal reinforcement and matroid membership. We obtain improved running times both for general matroids in the independence oracle model and for the graphic matroid. The main thrust of our improvements comes from developing a faster and unifying \emph{pushrelabel} algorithm for the integercapacitated versions of these problems, building on previous work by [FM12]. We then build on this algorithm in two directions. First we develop a faster augmenting path subroutine for $k$fold matroid union that, when appended to an approximation version of the pushrelabel algorithm, gives a faster exact algorithm for some parameters of $k$. In particular we obtain a subquadraticquery running time in the uncapacitated setting for the three basic problems listed above. We also obtain faster approximation algorithms for these problems with realvalued capacities by reducing to small integral capacities via randomized rounding. To this end, we develop a new randomized rounding technique for base covering problems in matroids that may also be of independent interest.
more »
« less
 Award ID(s):
 2129816
 NSFPAR ID:
 10500356
 Editor(s):
 Woodruff, David P.
 Publisher / Repository:
 SIAM
 Date Published:
 Journal Name:
 Proceedings of the 2024 ACMSIAM Symposium on Discrete Algorithms, SODA 2024, Alexandria, VA, USA, January 710, 2024
 Format(s):
 Medium: X
 Location:
 Alexandria, VA, USA
 Sponsoring Org:
 National Science Foundation
More Like this


We consider fast algorithms for monotone submodular maximization subject to a matroid constraint. We assume that the matroid is given as input in an explicit form, and the goal is to obtain the best possible running times for important matroids. We develop a new algorithm for a general matroid constraint with a 1  1/e  epsilon approximation that achieves a fast running time provided we have a fast data structure for maintaining an approximately maximum weight base in the matroid through a sequence of decrease weight operations. We construct such data structures for graphic matroids and partition matroids, and we obtain the first algorithms for these classes of matroids that achieve a nearlyoptimal, 1  1/e  epsilon approximation, using a nearlylinear number of function evaluations and arithmetic operations.more » « less

Bansal, Nikhil ; Merelli, Emanuela ; Worrell, James (Ed.)We consider the fundamental problems of determining the rooted and global edge and vertex connectivities (and computing the corresponding cuts) in directed graphs. For rooted (and hence also global) edge connectivity with small integer capacities we give a new randomized Monte Carlo algorithm that runs in time Õ(n²). For rooted edge connectivity this is the first algorithm to improve on the Ω(n³) time bound in the densegraph highconnectivity regime. Our result relies on a simple combination of sampling coupled with sparsification that appears new, and could lead to further tradeoffs for directed graph connectivity problems. We extend the edge connectivity ideas to rooted and global vertex connectivity in directed graphs. We obtain a (1+ε)approximation for rooted vertex connectivity in Õ(nW/ε) time where W is the total vertex weight (assuming integral vertex weights); in particular this yields an Õ(n²/ε) time randomized algorithm for unweighted graphs. This translates to a Õ(KnW) time exact algorithm where K is the rooted connectivity. We build on this to obtain similar bounds for global vertex connectivity. Our results complement the known results for these problems in the low connectivity regime due to work of Gabow [Harold N. Gabow, 1995] for edge connectivity from 1991, and the very recent work of Nanongkai et al. [Nanongkai et al., 2019] and Forster et al. [Sebastian Forster et al., 2020] for vertex connectivity.more » « less

There has been a longstanding interest in computing diverse solutions to optimization problems. In 1995 J. Krarup [28] posed the problem of finding kedge disjoint Hamiltonian Circuits of minimum total weight, called the peripatetic salesman problem (PSP). Since then researchers have investigated the complexity of finding diverse solutions to spanning trees, paths, vertex covers, matchings, and more. Unlike the PSP that has a constraint on the total weight of the solutions, recent work has involved finding diverse solutions that are all optimal. However, sometimes the space of exact solutions may be too small to achieve sufficient diversity. Motivated by this, we initiate the study of obtaining sufficientlydiverse, yet approximatelyoptimal solutions to optimization problems. Formally, given an integer k, an approximation factor c, and an instance I of an optimization problem, we aim to obtain a set of k solutions to I that a) are all c approximatelyoptimal for I and b) maximize the diversity of the k solutions. Finding such solutions, therefore, requires a better understanding of the global landscape of the optimization function. Given a metric on the space of solutions, and the diversity measure as the sum of pairwise distances between solutions, we first provide a general reduction to an associated budgetconstrained optimization (BCO) problem, where one objective function is to optimized subject to a bound on the second objective function. We then prove that biapproximations to the BCO can be used to give biapproximations to the diverse approximately optimal solutions problem. As applications of our result, we present polynomial time approximation algorithms for several problems such as diverse capproximate maximum matchings, shortest paths, global mincut, and minimum weight bases of a matroid. The last result gives us diverse capproximate minimum spanning trees, advancing a step towards achieving diverse capproximate TSP tours. We also explore the connection to the field of multiobjective optimization and show that the class of problems to which our result applies includes those for which the associated DUALRESTRICT problem defined by Papadimitriou and Yannakakis [35], and recently explored by Herzel et al. [26] can be solved in polynomial timore » « less

There has been a longstanding interest in computing diverse solutions to optimization problems. In 1995 J. Krarup [28] posed the problem of finding kedge disjoint Hamiltonian Circuits of minimum total weight, called the peripatetic salesman problem (PSP). Since then researchers have investigated the complexity of finding diverse solutions to spanning trees, paths, vertex covers, matchings, and more. Unlike the PSP that has a constraint on the total weight of the solutions, recent work has involved finding diverse solutions that are all optimal. However, sometimes the space of exact solutions may be too small to achieve sufficient diversity. Motivated by this, we initiate the study of obtaining sufficientlydiverse, yet approximatelyoptimal solutions to optimization problems. Formally, given an integer k, an approximation factor c, and an instance I of an optimization problem, we aim to obtain a set of k solutions to I that a) are all c approximatelyoptimal for I and b) maximize the diversity of the k solutions. Finding such solutions, therefore, requires a better understanding of the global landscape of the optimization function. Given a metric on the space of solutions, and the diversity measure as the sum of pairwise distances between solutions, we first provide a general reduction to an associated budgetconstrained optimization (BCO) problem, where one objective function is to optimized subject to a bound on the second objective function. We then prove that biapproximations to the BCO can be used to give biapproximations to the diverse approximately optimal solutions problem. As applications of our result, we present polynomial time approximation algorithms for several problems such as diverse capproximate maximum matchings, shortest paths, global mincut, and minimum weight bases of a matroid. The last result gives us diversecapproximate minimum spanning trees, advancing a step towards achieving diverse capproximate TSP tours. We also explore the connection to the field of multiobjective optimization and show that the class of problems to which our result applies includes those for which the associated DUALRESTRICT problem defined by Papadimitriou and Yannakakis [35], and recently explored by Herzel et al. [26] can be solved in polynomial time.more » « less