The densest subgraph problem in a graph (\dsg), in the simplest
form, is the following. Given an undirected graph $G=(V,E)$ find a
subset $S \subseteq V$ of vertices that maximizes the ratio
$|E(S)|/|S|$ where $E(S)$ is the set of edges with both endpoints
in $S$. \dsg and several of its variants are well-studied in theory
and practice and have many applications in data mining and network
analysis. In this paper we study fast algorithms and structural
aspects of \dsg via the lens of \emph{supermodularity}.
For this we consider the densest supermodular subset problem (\dssp):
given a non-negative supermodular function $f: 2^V
\rightarrow \mathbb{R}_+$, maximize $f(S)/|S|$.
For \dsg we describe a simple flow-based algorithm that outputs a
$(1-\eps)$-approximation in deterministic $\tilde{O}(m/\eps)$ time
where $m$ is the number of edges. Our algorithm is the first to have
a near-linear dependence on $m$ and $1/\eps$ and improves previous
methods based on an LP relaxation. It generalizes to hypergraphs, and
also yields a faster algorithm for directed \dsg.
Greedy peeling algorithms have been very popular for \dsg and
several variants due to their efficiency, empirical performance, and
worst-case approximation guarantees. We describe a simple peeling
algorithm for \dssp and analyze its approximation guarantee in a
fashion that unifies several existing results. Boob et
al.\ \cite{bgpstww-20} developed an \emph{iterative} peeling
algorithm for \dsg which appears to work very well in practice, and
made a conjecture about its convergence to optimality. We
affirmatively answer their conjecture, and in fact prove that a
natural generalization of their algorithm converges to a
$(1-\eps)$-approximation for \emph{any} supermodular function $f$;
the key to our proof is to consider an LP formulation that is
derived via the \Lovasz extension of a supermodular function. For
\dsg the bound on the number of iterations we prove is $O(\frac{\Delta
\ln |V|}{\lambda^*}\cdot \frac{1}{\eps^2})$ where $\Delta$ is
the maximum degree and $\lambda^*$ is the optimum value. Our work suggests
that iterative peeling can be an effective heuristic for
several objectives considered in the literature.
Finally, we show that the $2$-approximation for densest-at-least-$k$
subgraph \cite{ks-09} extends to the supermodular setting. We also
give a unified analysis of the peeling algorithm for this problem, and
via this analysis derive an approximation guarantee for a
generalization of \dssp to maximize $f(S)/g(|S|)$ for a concave
function $g$.
more »
« less
Determinant Maximization via Matroid Intersection Algorithms
Determinant maximization problem gives a general framework that models problems arising in as diverse fields as statistics [Puk06], convex geometry [Kha96], fair allocations
[AGSS16], combinatorics [AGV18], spectral graph theory [NST19a], network design, and random processes [KT12]. In an instance of a determinant maximization problem, we are given a collection of vectors U = {v1, . . . , vn} ⊂ Rd , and a goal is to pick a subset S ⊆ U of given vectors to maximize the determinant of the matrix ∑i∈S vivi^T. Often, the set S of picked vectors must satisfy additional combinatorial constraints such as cardinality constraint (|S| ≤ k) or matroid constraint (S is a basis of a matroid defined on the vectors).
In this paper, we give a polynomial-time deterministic algorithm that returns a r
O(r)-approximation for any matroid of rank r ≤ d. This improves previous results that give e
O(r^2)-approximation algorithms relying on e^O(r)-approximate estimation algorithms [NS16, AG17,AGV18, MNST20] for any r ≤ d. All previous results use convex relaxations and their relationship to stable polynomials and strongly log-concave polynomials. In contrast, our algorithm builds on combinatorial algorithms for matroid intersection, which iteratively improve any solution by finding an alternating negative cycle in the exchange graph defined by the matroids. While the det(.) function is not linear, we show that taking appropriate linear approximations at each iteration suffice to give the improved approximation algorithm.
more »
« less
- NSF-PAR ID:
- 10362731
- Date Published:
- Journal Name:
- Annual Symposium on Foundations of Computer Science
- ISSN:
- 0272-5428
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
We consider the problem of maximizing the multilinear extension of a submodular function subject a single matroid constraint or multiple packing constraints with a small number of adaptive rounds of evaluation queries. We obtain the first algorithms with low adaptivity for submodular maximization with a matroid constraint. Our algorithms achieve a $1-1/e-\epsilon$ approximation for monotone functions and a $1/e-\epsilon$ approximation for non-monotone functions, which nearly matches the best guarantees known in the fully adaptive setting. The number of rounds of adaptivity is $O(\log^2{n}/\epsilon^3)$, which is an exponential speedup over the existing algorithms. We obtain the first parallel algorithm for non-monotone submodular maximization subject to packing constraints. Our algorithm achieves a $1/e-\epsilon$ approximation using $O(\log(n/\epsilon) \log(1/\epsilon) \log(n+m)/ \epsilon^2)$ parallel rounds, which is again an exponential speedup in parallel time over the existing algorithms. For monotone functions, we obtain a $1-1/e-\epsilon$ approximation in $O(\log(n/\epsilon)\log(m)/\epsilon^2)$ parallel rounds. The number of parallel rounds of our algorithm matches that of the state of the art algorithm for solving packing LPs with a linear objective (Mahoney et al., 2016). Our results apply more generally to the problem of maximizing a diminishing returns submodular (DR-submodular) function.more » « less
-
more » « less
Abstract We consider the problem of covering multiple submodular constraints. Given a finite ground set
N , a weight function$$w: N \rightarrow \mathbb {R}_+$$ r monotone submodular functions$$f_1,f_2,\ldots ,f_r$$ N and requirements$$k_1,k_2,\ldots ,k_r$$ $$S \subseteq N$$ $$f_i(S) \ge k_i$$ $$1 \le i \le r$$ Multi-Submod-Cover and it was recently considered by Har-Peled and Jones (Few cuts meet many point sets. CoRR.arxiv:abs1808.03260 Har-Peled and Jones 2018) who were motivated by an application in geometry. Even with$$r=1$$ Multi-Submod-Cover generalizes the well-known Submodular Set Cover problem (Submod-SC ), and it can also be easily reduced toSubmod-SC . A simple greedy algorithm gives an$$O(\log (kr))$$ $$k = \sum _i k_i$$ Multi-Submod-Cover that covers each constraint to within a factor of$$(1-1/e-\varepsilon )$$ $$O(\frac{1}{\epsilon }\log r)$$ $$f_i$$ Partial-SC ), covering integer programs (CIPs ) and multiple vertex cover constraints Bera et al. (Theoret Comput Sci 555:2–8 Bera et al. 2014). Both these algorithms are based on mathematical programming relaxations that avoid the limitations of the greedy algorithm. We demonstrate the implications of our algorithms and related ideas to several applications ranging from geometric covering problems to clustering with outliers. Our work highlights the utility of the high-level model and the lens of submodularity in addressing this class of covering problems. -
Berry, Jonathan ; Shmoys, David ; Cowen, Lenore ; Naumann, Uwe (Ed.)Continuous DR-submodular functions are a class of functions that satisfy the Diminishing Returns (DR) property, which implies that they are concave along non-negative directions. Existing works have studied monotone continuous DR-submodular maximization subject to a convex constraint and have proposed efficient algorithms with approximation guarantees. However, in many applications, e. g., computing the stability number of a graph and mean-field inference for probabilistic log-submodular models, the DR-submodular function has the additional property of being strongly concave along non-negative directions that could be utilized for obtaining faster convergence rates. In this paper, we first introduce and characterize the class of strongly DR-submodular functions and show how such a property implies strong concavity along non-negative directions. Then, we study L-smooth monotone strongly DR-submodular functions that have bounded curvature, and we show how to exploit such additional structure to obtain algorithms with improved approximation guarantees and faster convergence rates for the maximization problem. In particular, we propose the SDRFW algorithm that matches the provably optimal approximation ratio after only iterations, where c ∈ [0,1] and μ ≥ 0 are the curvature and the strong DR-submodularity parameter. Furthermore, we study the Projected Gradient Ascent (PGA) method for this problem and provide a refined analysis of the algorithm with an improved approximation ratio (compared to ½ in prior works) and a linear convergence rate. Given that both algorithms require knowledge of the smoothness parameter L, we provide a novel characterization of L for DR-submodular functions showing that in many cases, computing L could be formulated as a convex optimization problem, i. e., a geometric program, that could be solved efficiently. Experimental results illustrate and validate the efficiency and effectiveness of our algorithms.more » « less
-
We study the classic Maximum Independent Set problem under the notion of stability introduced by Bilu and Linial (2010): a weighted instance of Independent Set is γ-stable if it has a unique optimal solution that remains the unique optimal solution under multiplicative perturbations of the weights by a factor of at most γ ≥ 1. The goal then is to efficiently recover this “pronounced” optimal solution exactly. In this work, we solve stable instances of Independent Set on several classes of graphs: we improve upon previous results by solving \tilde{O}(∆/sqrt(log ∆))-stable instances on graphs of maximum degree ∆, (k − 1)-stable instances on k-colorable graphs and (1 + ε)-stable instances on planar graphs (for any fixed ε > 0), using both combinatorial techniques as well as LPs and the Sherali-Adams hierarchy. For general graphs, we give an algorithm for (εn)-stable instances, for any fixed ε > 0, and lower bounds based on the planted clique conjecture. As a by-product of our techniques, we give algorithms as well as lower bounds for stable instances of Node Multiway Cut (a generalization of Edge Multiway Cut), by exploiting its connections to Vertex Cover. Furthermore, we prove a general structural result showing that the integrality gap of convex relaxations of several maximization problems reduces dramatically on stable instances. Moreover, we initiate the study of certified algorithms for Independent Set. The notion of a γ-certified algorithm was introduced very recently by Makarychev and Makarychev (2018) and it is a class of γ-approximation algorithms that satisfy one crucial property: the solution returned is optimal for a perturbation of the original instance, where perturbations are again multiplicative up to a factor of γ ≥ 1 (hence, such algorithms not only solve γ-stable instances optimally, but also have guarantees even on unstable instances). Here, we obtain ∆-certified algorithms for Independent Set on graphs of maximum degree ∆, and (1 + ε)-certified algorithms on planar graphs. Finally, we analyze the algorithm of Berman and Fürer (1994) and prove that it is a ((∆+1)/3 + ε)-certified algorithm for Independent Set on graphs of maximum degree ∆ where all weights are equal to 1.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- The DOI is not currently available.
