MOTIVATION: Multiplex PCR-based enrichment is widely used in viral genome sequencing and pathogen surveillance. However, designing large sets of primers that maximize genome coverage while minimizing primer-primer interactions remains a major computational challenge. Existing methods such as SADDLE and Olivar use heuristics to optimize a Badness score for primer dimers but lack theoretical guarantees on solution quality. RESULTS: We introduce PRISM, a new framework that formulates multiplex primer design as a constrained submodular maximization problem. Our method defines an objective that balances genome coverage and dimer risk, and applies a local search algorithm with a constant-factor approximation guarantee. Evaluations on viral genome datasets demonstrate that PRISM consistently achieves lower Badness scores compared to PrimalScheme, Olivar, and primerJinn. These results highlight the scalability and theoretical rigor of submodular optimization in primer design. AVAILABILITY: PRISM is open-source and available at https://github.com/yhhan19/PRISM-new. The experimental data, scripts, and results used in this paper are archived on Figshare at https://doi.org/10.6084/m9.figshare.32806499.

Modern instances of combinatorial optimization problems often exhibit billion-scale ground sets, which have many uninformative or redundant elements. In this work, we develop light-weight pruning algorithms to quickly discard elements that are unlikely to be part of an optimal solution. Under mild assumptions on the instance, we prove theoretical guarantees on the fraction of the optimal value retained and the size of the resulting pruned ground set. Through extensive experiments on real-world datasets for various applications, we demonstrate that our algorithm, QuickPrune, efficiently prunes over 90% of the ground set and outperforms state-of-the-art classical and machine learning heuristics for pruning.

With the rapid growth of data in modern applications, parallel combinatorial algorithms for maximizing non-monotone submodular functions have gained significant attention. In the parallel computation setting, the state-of-the-art approximation ratio of $1/e$ is achieved by a continuous algorithm (Ene & Nguyen, 2020) with adaptivity $\mathcal O (log(n))$. In this work, we focus on size constraints and present the first combinatorial algorithm matching this bound – a randomized parallel approach achieving $1/e - \epsilon$ approximation ratio. This result bridges the gap between continuous and combinatorial approaches for this problem. As a byproduct, we also develop a simpler $(1/4 - \epsilon)$-approximation algorithm with high probability $(\ge 1 - 1/n)$. Both algorithms achieve $\mathcal O (log(n) log(k))$ adaptivity and $\mathcal O (n log(n) log(k)) query complexity. Empirical results show our algorithms achieve competitive objective values, with the $(1/4 - $\epsilon$)$-approximation algorithm particularly efficient in queries.

Combinatorial optimization (CO) problems on graphs arise in various applications across diverse domains. Many of these problems are NP-hard, and heuristics have been developed to provide near-optimal solutions. In the big data era, the high dimensionality of these problems poses significant challenges for existing heuristic methods, which struggle to scale efficiently. In this paper, we propose Hierarchical DeepPruner, an adaptive framework that employs a two-stage approach to efficiently prune the search space of CO problems on graphs. Compared to state-of-the-art pruning heuristics, our algorithm offers two key advantages: 1) it does not require extensive feature engineering or domain-specific knowledge, and 2) it outperforms all previous methods while consistently pruning over 95% of the ground set, resulting in up to several of tenfold speedups—typically with minimal impact on solution quality. Additionally, our algorithm can successfully reduce the search space of instances even if they lie outside the training distribution, resulting in small optimality gaps across multiple budgets

For constrained, not necessarily monotone submodular maximization, all known approximation algorithms with ratio greater than $1/e$ require continuous ideas, such as queries to the multilinear extension of a submodular function and its gradient, which are typically expensive to simulate with the original set function. For combinatorial algorithms, the best known approximation ratios for both size and matroid constraint are obtained by a simple randomized greedy algorithm of Buchbinder et al. [9]: $1/e \approx 0.367$ for size constraint and $0.281$ for the matroid constraint in $\mathcal O (kn)$ queries, where $k$ is the rank of the matroid. In this work, we develop the first combinatorial algorithms to break the $1/e$ barrier: we obtain approximation ratio of $0.385$ in $\mathcal O (kn)$ queries to the submodular set function for size constraint, and $0.305$ for a general matroid constraint. These are achieved by guiding the randomized greedy algorithm with a fast local search algorithm. Further, we develop deterministic versions of these algorithms, maintaining the same ratio and asymptotic time complexity. Finally, we develop a deterministic, nearly linear time algorithm with ratio $0.377$.

Distributed maximization of a submodular function in the MapReduce (MR) model has received much attention, culminating in two frameworks that allow a centralized algorithm to be run in the MR setting without loss of approximation, as long as the centralized algorithm satisfies a certain consistency property – which had previously only been known to be satisfied by the standard greedy and continous greedy algorithms. A separate line of work has studied parallelizability of submodular maximization in the adaptive complexity model, where each thread may have access to the entire ground set. For the size-constrained maximization of a monotone and submodular function, we show that several sublinearly adaptive (highly parallelizable) algorithms satisfy the consistency property required to work in the MR setting, which yields practical, parallelizable and distributed algorithms. Separately, we develop the first distributed algorithm with linear query complexity for this problem. Finally, we provide a method to increase the maximum cardinality constraint for MR algorithms at the cost of additional MR rounds.

We present combinatorial and parallelizable algorithms for the maximization of a submodular function, not necessarily monotone, with respect to a size constraint. We improve the best approximation factor achieved by an algorithm that has optimal adaptivity and nearly optimal query complexity to 1/6 − ε, and even further to 0.193 − ε by increasing the adaptivity by a factor of O(log(k)). The conference version of this work mistakenly employed a subroutine that does not work for non-monotone, submodular functions. In this version, we propose a fixed and improved subroutine to add a set with high average marginal gain, ThreshSeq, which returns a solution in O(log(n)) adaptive rounds with high probability. Moreover, we provide two approximation algorithms. The first has approximation ratio 1/6 − ε, adaptivity O(log(n)), and query complexity O(n log(k)), while the second has approximation ratio 0.193 − ε, adaptivity O(log(n) log(k)), and query complexity O(n log(k)). Our algorithms are empirically validated to use a low number of adaptive rounds and total queries while obtaining solutions with high objective value in comparison with state-of-the-art approximation algorithms, including continuous algorithms that use the multilinear extension.

MapReduce (MR) algorithms for maximizing monotone, submodular functions subject to a cardinality constraint (SMCC) are currently restricted to the use of the linear-adaptive (non-parallelizable) algorithm GREEDY. Low-adaptive algorithms do not satisfy the requirements of these distributed MR frameworks, thereby limiting their performance. We study the SMCC problem in a distributed setting and propose the first MR algorithms with sublinear adaptive complexity. Our algorithms, R-DASH, T-DASH and G-DASH provide 0.316 - ε, 3/8 - ε , and (1 - 1/e - ε) approximation ratios, respectively, with nearly optimal adaptive complexity and nearly linear time complexity. Additionally, we provide a framework to increase, under some mild assumptions, the maximum permissible cardinality constraint from O( n / ℓ^2) of prior MR algorithms to O( n / ℓ ), where n is the data size and ℓ is the number of machines; under a stronger condition on the objective function, we increase the maximum constraint value to n. Finally, we provide empirical evidence to demonstrate that our sublinear-adaptive, distributed algorithms provide orders of magnitude faster runtime compared to current state-of-the-art distributed algorithms.

In this work, we study the problem of finding the maximum value of a non-negative submodular function subject to a limit on the number of items selected, a ubiquitous problem that appears in many applications, such as data summarization and nonlinear regression. We provide the first deterministic, linear-time approximation algorithms for this problem that do not assume the objective is monotone. We present three deterministic, linear-time algorithms: a single-pass streaming algorithm with a ratio of 23.313 + ε, which is the first linear-time streaming algorithm; a simpler deterministic linear-time algorithm with a ratio of 11.657; and a (4 + O(ε))-approximation algorithm. Finally, we present a deterministic algorithm that obtains ratio of e + ε in O_ε (n log(n)) time, close to the best known expected ratio of e - 0.121 in polynomial time.

We study combinatorial, parallelizable algorithms for maximization of a submodular function, not necessarily monotone, with respect to a cardinality constraint k. We improve the best approximation factor achieved by an algorithm that has optimal adaptivity and query complexity, up to logarithmic factors in the size of the ground set, from 0.039 to nearly 0.193. Heuristic versions of our algorithms are empirically validated to use a low number of adaptive rounds and total queries while obtaining solutions with high objective value in comparison with state-of-the-art approximation algorithms, including continuous algorithms that use the multilinear extension.

We consider the problem of monotone, submodular maximization over a ground set of size $n$ subject to cardinality constraint $k$. For this problem, we introduce the first deterministic algorithms with linear time complexity; these algorithms are streaming algorithms. Our single-pass algorithm obtains a constant ratio in $\lceil n / c \rceil + c$ oracle queries, for any $c \ge 1$. In addition, we propose a deterministic, multi-pass streaming algorithm with a constant number of passes that achieves nearly the optimal ratio with linear query and time complexities. We prove a lower bound that implies no constant-factor approximation exists using $o(n)$ queries, even if queries to infeasible sets are allowed. An empirical analysis demonstrates that our algorithms require fewer queries (often substantially less than $n$) yet still achieve better objective value than the current state-of-the-art algorithms, including single-pass, multi-pass, and non-streaming algorithms.

For the problem of maximizing a monotone, submodular function with respect to a cardinality constraint $k$ on a ground set of size $n$, we provide an algorithm that achieves the state-of-the-art in both its empirical performance and its theoretical properties, in terms of adaptive complexity, query complexity, and approximation ratio; that is, it obtains, with high probability, query complexity of $O(n)$ in expectation, adaptivity of $O(\log(n))$, and approximation ratio of nearly $1-1/e$. The main algorithm is assembled from two components which may be of independent interest. The first component of our algorithm, LINEARSEQ, is useful as a preprocessing algorithm to improve the query complexity of many algorithms. Moreover, a variant of LINEARSEQ is shown to have adaptive complexity of $O( \log (n / k) )$ which is smaller than that of any previous algorithm in the literature. The second component is a parallelizable thresholding procedure THRESHOLDSEQ for adding elements with gain above a constant threshold. Finally, we demonstrate that our main algorithm empirically outperforms, in terms of runtime, adaptive rounds, total queries, and objective values, the previous state-of-the-art algorithm FAST in a comprehensive evaluation with six submodular objective functions.

MOTIVATION: The de Bruijn graph is one of the fundamental data structures for analysis of high throughput sequencing data. In order to be applicable to population-scale studies, it is essential to build and store the graph in a space- and time-efficient manner. In addition, due to the ever-changing nature of population studies, it has become essential to update the graph after construction, e.g. add and remove nodes and edges. Although there has been substantial effort on making the construction and storage of the graph efficient, there is a limited amount of work in building the graph in an efficient and mutable manner. Hence, most space efficient data structures require complete reconstruction of the graph in order to add or remove edges or nodes. RESULTS: In this article, we present DynamicBOSS, a succinct representation of the de Bruijn graph that allows for an unlimited number of additions and deletions of nodes and edges. We compare our method with other competing methods and demonstrate that DynamicBOSS is the only method that supports both addition and deletion and is applicable to very large samples (e.g. greater than 15 billion k-mers). Competing dynamic methods, e.g. FDBG cannot be constructed on large scale datasets, or cannot support both addition and deletion, e.g. BiFrost. AVAILABILITY AND IMPLEMENTATION: DynamicBOSS is publicly available at https://github.com/baharpan/dynboss. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

In this work, we study the Submodular Cost Submodular Cover problem, which is to minimize the submodular cost required to ensure that the submodular benefit function exceeds a given threshold. Existing approximation ratios for the greedy algorithm assume a value oracle to the benefit function. However, access to a value oracle is not a realistic assumption for many applications of this problem, where the benefit function is difficult to compute. We present two incomparable approximation ratios for this problem with an approximate value oracle and demonstrate that the ratios take on empirically relevant values through a case study with the Influence Threshold problem in online social networks.

A deterministic approximation algorithm is presented for the maximization of non-monotone submodular functions over a ground set of size $n$ subject to cardinality constraint $k$; the algorithm is based upon the idea of interlacing two greedy procedures. The algorithm uses interlaced, thresholded greedy procedures to obtain tight ratio $1/4 - \epsilon$ in $O \left( \frac{n}{\epsilon} \log \left( \frac{k}{\epsilon} \right) \right)$ queries of the objective function, which improves upon both the ratio and the quadratic time complexity of the previously fastest deterministic algorithm for this problem. The algorithm is validated in the context of two applications of non-monotone submodular maximization, on which it outperforms the fastest deterministic and randomized algorithms in prior literature.

While online social networks (OSNs) have become an important platform for information exchange, the abuse of OSNs to spread misinformation has become a significant threat to our society. To restrain the propagation of misinformation in its early stages, we study the Distance-constrained Misinformation Combat under Uncertainty problem, which aims to both reduce the spread of misinformation and enhance the spread of correct information within a given propagation distance. The problem formulation considers the competitive diffusion of misinformation and correct information. It also accounts for the uncertainty in identifying initial misinformation adopters. For competitive propagation with major-threshold activation, we propose a solution based on stochastic programming and provide an upper-bound in the presence of uncertainty. We propose an efficient Combat Seed Selection algorithm to tackle general-threshold activation, in which we define a measure, “effectiveness”, to evaluate the contribution of nodes to the fight against misinformation. Through extensive experiments, we validate that our algorithm outputs high-quality solution with very fast computation.

The vulnerability of interdependent networks has recently drawn much attention, especially in the key infrastructure networks such as power and communication networks. However, the existing works mainly considered a single cascade model across the networks and there is a need for more accurate models and analysis. In this paper, we focus on the interdependent power/communication networks to accurately analyze their vulnerability by considering heterogeneous cascade models. Accurately analyzing interdependent networks is challenging as the cascades are heterogeneous yet interdependent. Also, including multiple timescales into the context can further increase the complexity. To better depict the vulnerability of interdependent networks, we first propose a method to learn a threshold model from historical data to characterize the cascades in the power network and alleviate the need of calculating complicated power network dynamics. Next, we introduce message passing equations to generalize the threshold model in the power network and the percolation model in the communication network, based on which we derive efficient solution for finding the most critical nodes in the interdependent networks. Removing the most critical nodes can cause the largest cascade and thus characterizes the vulnerability. We evaluate the performance of the proposed methods in various datasets and discuss how network parameters, such as the timescales, can impact the vulnerability.

The optimization of submodular functions on the integer lattice has received much attention recently, but the objective functions of many applications are non-submodular. We provide two approximation algorithms for maximizing a non-submodular function on the integer lattice subject to a cardinality constraint; these are the first algorithms for this purpose that have polynomial query complexity. We propose a general framework for influence maximization on the integer lattice that generalizes prior works on this topic, and we demonstrate the efficiency of our algorithms in this context.

Previous approaches to caching for Device-to-Device (D2D) communication cache popular files during off-peak hours. Since the popularity of content may evolve quickly or be unavailable in advance, we propose a flexible approach to cellular device caching where files are cached or uncached dynamically as file popularity evolves Dynamic caching motivates a space-efficient optimization problem Minimum File Placement (MFP), which is to cache a single file in the least amount of cache space to ensure a specified cache hit rate. In order to estimate the future cache hit rate, we use historical heterogeneous contact and request patterns of the devices. We present a bicriteria greedy algorithm for MFP and incorporate this algorithm into a dynamic approach to caching from a library of files with evolving popularity distribution. In an extensive experimental evaluation, we analyze the effectiveness of our approach to mobile device caching and demonstrate its advantages over other static contact-pattern-aware caching and alternative dynamic approaches.

Motivation: The de Bruijn graph is fundamental to the analysis of next generation sequencing data and so, as datasets of DNA reads grow rapidly, it becomes more important to represent de Bruijn graphs compactly while still supporting fast assembly. Previous implementations of compact de Bruijn graphs have not supported node or edge deletion, however, which is important for pruning spurious elements from the graph. Results: Belazzougui et al. (2016b) recently proposed a compact and fully dynamic representation, which supports exact membership queries and insertions and deletions of both nodes and edges. In this paper, we give a practical implementation of their data structure, supporting exact membership queries and fully dynamic edge operations, as well as limited support for dynamic node operations. We demonstrate experimentally that its performance is comparable to that of state-of-the-art implementations based on Bloom filters. Availability and implementation: Our source-code is publicly available at https://github.com/csirac/dynamicDBG under an open-source license.

Motivated by online social networks that are linked together through overlapping users, we study the influence maximization problem on a multiplex, with each layer endowed with its own model of influence diffusion. This problem is a novel version of the influence maximization problem that necessitates new analysis incorporating the type of propagation on each layer of the multiplex. We identify a new property, generalized deterministic submodular, which when satisfied by the propagation in each layer, ensures that the propagation on the multiplex overall is submodular-for this case, we formulate influential seed finder (ISF), the greedy algorithm with approximation ratio (1-1/e). Since the size of a multiplex comprising multiple OSNs may encompass billions of users, we formulate an algorithm knapsack seeding of network (KSN) that runs on each layer of the multiplex in parallel. KSN takes an α-approximation algorithm A for the influence maximization problem on a single network as input, and has approximation ratio ((1 - ϵ)α)/((o + 1)k) for arbitrary ϵ > 0, o is the number of overlapping users, and k is the number of layers in the multiplex. Experiments on real and synthesized multiplexes validate the efficacy of the proposed algorithms for the problem of influence maximization in the heterogeneous multiplex. Implementations of ISF and KSN are available at http://www.alankuhnle.com/papers/mim/mim.html.

Motivated by the relevance of clustering or transitivity to a variety of network applications, we study the Triangle Interdiction Problem (TIP), which is to find a minimum-size set of edges that intersects all triangles of a network. As existing approximation algorithms for this NP-hard problem either do not scale well to massive networks or have poor solution quality, we formulate two algorithms, TARL and DART, with worst-case guarantees 5/2 and 3 with respect to optimal, respectively. Furthermore, DART is able to efficiently maintain its worst-case guarantee under dynamic edge insertion and removal to the network. In our comprehensive experimental evaluation, we demonstrate that DART is able to run on networks with billions of triangles within 2 hours and is able to dynamically update its solution in microseconds.

Online Social Networks (OSNs) are effective platforms for viral marketing. Due to their importance, viral marketing related problems in OSNs have been extensively studied in the past decade. However, none of the existing works can cope with the situation that the propagation rate dynamically increases for popular topics, as they all assume known propagation rates. In this paper, to better describe realistic information propagation in OSNs, we propose a novel model, Dynamic Influence Propagation (DIP), that allows propagation rate to change during the diffusion. We then define a new research problem: Threshold Activation Problem under DIP (TAP-DIP) to study the impact of DIP. TAP-DIP adds extra complexity on the already #P-hard TAP problem. Despite it hardness, we are able to approximate TAP-DIP with O(log|V|) ratio. Sitting in the core of our algorithm are the Lipschitz optimization technique and a novel solution to the general version of TAP, the Multi-TAP problem. Using various real OSN datasets, we experimentally demonstrate the impact of DIP and that our solution not only generates high-quality seed sets when being aware of the rate increase, but also is scalable.

We consider the Threshold Activation Problem (TAP): given social network G and positive threshold T, find a minimum-size seed set A that can trigger expected activation of at least T. We introduce the first scalable, parallelizable algorithm with performance guarantee for TAP suitable for datasets with millions of nodes and edges; we exploit the bicriteria nature of solutions to TAP to allow the user to control the running time versus accuracy of our algorithm through a parameter α ϵ (0, 1): given η > 0, with probability 1 - η our algorithm returns a solution A with expected activation greater than T - 2αT, and the size of the solution A is within factor 1-h 4α/T + log(T) of the optimal size. The algorithm runs in time O (α-2log (n/η) (n + m)|A|), where n, m, refer to the number of nodes, edges in the network. The performance guarantee holds for the general triggering model of internal influence and also incorporates external influence, provided a certain condition is met on the cost-effectivity of seed selection.

While online social networks provide access to a massive information source, they also enable wide dissemination of false or inaccurate content. Undesirable results caused by misinformation propagation make its timely detection very imperative. An important question is how many monitors are required to detect all misinformation cascades at their early stage. To answer this question, we define a Time Constrained Misinformation Detection (TCMD) problem. As we have proved, there is no polynomial time (1 - ε) ln n-approximation for the TCMD problem. The large number of independent misinformation cascades and heterogeneous delays make misinformation detection more challenging. Our approach includes stochastic programming and an O(ln(1 + n)) approximation algorithm for one-hop detection. This approach can provide a lower bound on the number of required monitors for general detection. Furthermore, we propose a network-compression based solution, whose effectiveness is validated by extensive experimental results.

Information propagation in online social networks (OSNs), which helps shaping consumers' purchasing decisions, has received a lot of attention. The ultimate goal of marketing and advertising in OSNs is to massively influence audiences and enlarge the number of product adoptions. Most of existing works focus on maximizing the influence of a single product or promoting the adoption of one product in competing campaigns. However, in reality, the majority of companies produce various products for supplying customers with different needs. Therefore, it is truly significant and also challenging to wisely distribute limited budget across multiple products in viral marketing. In this paper, we investigate a Profit Maximization with Multiple Adoptions (PM2A) problem, which aims at maximizing the overall profit across all products. The natural greedy fails to provide a bounded result. In order to select high quality seeds for information propagation, we first proposed the PMCE algorithm, which has a ratio 1/2 (1 - 1/e2). Moreover, we further improve this ratio to (1-1/e) by proposing the PMIS algorithm. Comprehensive experiments on three real social networks are conducted. And results show that our algorithms outperform other heuristics, and better distribute the budget in terms of profit maximization.

Smart Grid addresses the problem of existing power grid's increasing complexity, growing demand and requirement for greater reliability, through two-way communication and automated residential load control among others. These features also makes the Smart Grid a target for a number of cyber attacks. In the paper, we study the problem of rate alteration attack (RAA) through fabrication of price messages which induces changes in load profiles of individual users and eventually causes major alteration in the load profile of the entire network. Combining with cascading failure, it ends up with a highly damaging attack. We prove that the problem is NP-Complete and provide its inapproximability. We devise two approaches for the problem, former deals with maximizing failure of lines with the given resource and then extending the effect with cascading failure while the later takes cascading potential into account while choosing the lines to fail. To get more insight into the impact of RAA, we also extend our algorithms to maximize number of node failures. Empirical results on both IEEE Bus data and real network help us evaluate our approaches under various settings of grid parameters.

Many complex systems, from World Wide Web and online social networks to mobile networks, exhibit community structure in which nodes can be grouped into densely interconnected communities. This special structure has been exploited extensively to design better solutions for many operations and applications such as routing in wireless networks, worm containment and interest prediction in social networks. The outcome of these solutions are sensitive to the network structures, which raises an important question: can communities be broken easily in a network? To answer this question, we introduce a density-based problem formulation for analyzing the vulnerability of communities. Our approach includes the NP-completeness and a O(log k) approximation algorithm for solving the problem where k is the number of communities to be broken. Additionally, we analyze the vulnerability of communities in the context of arbitrary community detection algorithms. The empirical results show that communities are vulnerable to edge removal and in some cases the removal of a small fraction of edges can break the community structure.

Device-to-device (D2D) communications has recently emerged as a promising technology for boosting the capacity of cellular systems. D2D enables direct communication between mobile devices over the cellular band without utilizing infrastructure nodes such as base stations, thereby reducing the load on cellular base stations and increasing network throughput through spatial reuse of radio resources. Hence it is important to optimally allocate these radio resources. Furthermore, since the composition of a cellular macro cell is highly dynamic, it is critical to adaptively update the resource allocation for D2D communications rather than recomputing it from scratch. In this work, we develop the first online algorithm, namely ODSRA, for dynamic resource allocation while maximizing spatial reuse. At the core of the resource allocation problem is the online set multicover problem, for which we present the first deterministic O (log n log m)-competitive online algorithm, where n is the number of elements, and m the number of sets. By simulation, we show the efficacy of ODSRA by analyzing network throughput and other metrics, obtaining a large improvement in running time over offline methods.