Submodular maximization has found extensive applications in various domains within the field of artificial intelligence, including but not limited to machine learning, computer vision, and natural language processing. With increasing size datasets these domains, there is a pressing need develop efficient parallelizable algorithms for submodular maximization. One measure parallelizability algorithm its adaptive complexity, which indicates number sequential rounds where polynomial queries...

Submodular maximization algorithms have found wide applications in various fields such as data summarization, recommendation systems, and active learning. In recent years, deletion-robust submodular garnered attention due to their significant implications scenarios where some points may be removed user preferences or privacy concerns, systems influence maximization. this paper, we study the fundamental problem of with knapsack constraints propose a robust streaming algorithm for it. To best...

Data summarization, i.e., selecting representative subsets of manageable size out massive data, is often modeled as a submodular optimization problem. Although there exist extensive algorithms for optimization, many them incur large computational overheads and hence are not suitable mining big data. In this work, we consider the fundamental problem (non-monotone) function maximization with knapsack constraint, propose simple yet effective efficient it. Specifically, deterministic algorithm...

The problem of constrained subset selection from a large data stream for profit maximization has many applications in web mining and machine learning, such as social advertising, team formation recommendation systems. Such can be formulated maximizing regularized submodular function under certain constraints. In this paper, we consider generalized k-system constraint, which captures various requirements real-world applications. For problem, propose the first streaming algorithm with provable...

Submodular maximization has wide applications in machine learning and data mining, where massive datasets have brought the great need for designing efficient parallelizable algorithms. One measure of parallelizability a submodular algorithm is its adaptivity complexity, which indicates number sequential rounds polynomial queries to objective function can be executed parallel. In this paper, we study problem non-monotone subject knapsack constraint, propose first combinatorial achieving an...

Submodular optimization has been identified as a powerful tool for many data mining applications, where representative subset of moderate size needs to be extracted from large-scale dataset. In scenarios points possess sensitive attributes such age, gender, or race, it becomes imperative integrate fairness measures into submodular mitigate bias and discrimination. this paper, we study the fundamental problem fair maximization subject knapsack constraint propose first streaming algorithm with...

We consider the revenue maximization problem in social advertising, where a network platform owner needs to select seed users for group of advertisers, each with payment budget, such that total expected gains from advertisers by propagating their ads is maximized. Previous studies on this show it intractable and present approximation algorithms. revisit fresh perspective develop novel efficient algorithms, both under setting an exact influence oracle assumed one assumption relaxed. Our...

We study the problem of maximizing a non-monotone, non-negative submodular function subject to matroid constraint. The prior best-known deterministic approximation ratio for this is $\frac{1}{4}-ε$ under $\mathcal{O}(({n^4}/ε)\log n)$ time complexity. show that can be improved $\frac{1}{4}$ $\mathcal{O}(nr)$ complexity, and then present more practical algorithm dubbed TwinGreedyFast which achieves in nearly-linear running $\mathcal{O}(\frac{n}ε\log\frac{r}ε)$. Our approach based on novel...

Data summarization, a fundamental methodology aimed at selecting representative subset of data elements from large pool ground data, has found numerous applications in big processing, such as social network analysis [5, 7], crowdsourcing [6], clustering [4], design [13], and document/corpus summarization [14]. Moreover, it is well acknowledged that the "representativeness" dataset can often be modeled by submodularity - mathematical concept abstracting "diminishing returns" property real...

Biological contamination is an important issue in environmental pH detection, and our prepared electrochemically cleanable electrode may be effective solution.

A lot of applications in web economics need to maximize the revenue under a budget for payments and also guarantee truthfulness users, so Budget-Feasible Mechanism (BFM) Design has aroused great interests during last decade. Most existing BFMs concentrate on maximizing monotone submodular function subject knapsack constraint, which is insufficient many with complex objectives or constraints. Observing this, recent studies (e.g., [4, 5, 11]) have considered non-monotone more constraints such...

Due to the pervasive "diminishing returns" property appeared in data-intensive applications, submodular maximization problems have aroused great attention from both machine learning community and computation theory community. During last decades, a lot of algorithms been proposed for subject various constraints [4, 6, 8], these can be used numerous applications including sensor placement [9], clustering [5], network design [13], so on.

Due to the pervasive "diminishing returns" property appeared in data-intensive applications, submodular maximization problems have aroused great attention from both machine learning community and computation theory community. During last decades, a lot of algorithms been proposed for subject various constraints [4, 6, 8], these can be used numerous applications including sensor placement [9], clustering [5], network design [13], so on. The existing roughly classified into offline streaming...

Submodular maximization has found extensive applications in various domains within the field of artificial intelligence, including but not limited to machine learning, computer vision, and natural language processing. With increasing size datasets these domains, there is a pressing need develop efficient parallelizable algorithms for submodular maximization. One measure parallelizability algorithm its adaptive complexity, which indicates number sequential rounds where polynomial queries...

It is of great importance to design streaming algorithms for submodular maximization, as many applications (e.g., crowdsourcing) have large volume data satisfying the well-known ''diminishing returns'' property, which cannot be handled by offline requiring full access whole dataset. However, maximization has been less studied than due hardness brought more stringent requirements on memory consumption. In this paper, we consider fundamental problem Submodular Maximization under k -System and...

Understanding the mechanism of psychological factors on traffic policy is great practical significance to promote smooth implementation and improve mobility transportation system. In this paper, we aim study how individuals response tradable credit scheme (TCS) by introducing norm activation model (NAM). The proportion thresholds for shifting travel mode are analyzed distribution participants corresponding five displayed, latent explicit variable developed respectively investigate underlying...

In this paper, we present a 4-state solution to the Firing Squad Synchronization Problem (FSSP) based on hybrid rule 60/102 Cellular Automata(CA). This solves problem line of length 2^n with two generals. Previous work FSSP for systems focused mostly linear cellular automata, where synchronizes an infinite number lines but not all possible lines. We give time-optimal solutions synchronize by 60 and 102 respectively, construct states transition table. Compared known CA way is simpler faster,...

Submodular optimization has numerous applications such as crowdsourcing and viral marketing. In this paper, we study the fundamental problem of non-negative submodular function maximization subject to a $k$-system constraint, which generalizes many other important constraints in cardinality matroid $k$-extendible system constraint. The existing approaches for achieve best-known approximation ratio $k+2\sqrt{k+2}+3$ (for general function) based on deterministic algorithmic frameworks. We...

We consider the revenue maximization problem in social advertising, where a network platform owner needs to select seed users for group of advertisers, each with payment budget, such that total expected gains from advertisers by propagating their ads is maximized. Previous studies on this show it intractable and present approximation algorithms. revisit fresh perspective develop novel efficient algorithms, both under setting an exact influence oracle assumed one assumption relaxed. Our...

Data summarization, a fundamental methodology aimed at selecting representative subset of data elements from large pool ground data, has found numerous applications in big processing, such as social network analysis [5, 7], crowdsourcing [6], clustering [4], design [13], and document/corpus summarization [14]. Moreover, it is well acknowledged that the "representativeness" dataset can often be modeled by submodularity - mathematical concept abstracting "diminishing returns" property real...