In remote terrestrial-satellite networks, caching is a very promising technique to alleviate the burden of space cloudlet(e.g., cache-enabled satellite user terminal) and to improve subscribers' quality of experie...In remote terrestrial-satellite networks, caching is a very promising technique to alleviate the burden of space cloudlet(e.g., cache-enabled satellite user terminal) and to improve subscribers' quality of experience(Qo E) in terms of buffering delay and achievable video streaming rate. In this paper, we studied a Qo E-driven caching placement optimization problem for video streaming that takes into account the required video streaming rate and the social relationship among users. Social ties between users are used to designate a set of helpers with caching capability, which can cache popular files proactively when the cloudlet is idle. We model the utility function of Qo E as a logarithmic function. Then, the caching placement problem is formulated as an optimization problem to maximize the user's average Qo E subject to the storage capacity constraints of the helpers and the cloudlets. Furthermore, we reformulate the problem into a monotone submodular optimization problem with a partition matroid constraint, and an efficient greedy algorithm with 1-1 e approximation ratio is proposed to solve it. Simulation results show that the proposed caching placement approach significantly outperforms the traditional approaches in terms of Qo E, while yields about the same delay and hit ratio performance compare to the delay-minimized scheme.展开更多
In this work,we study a k-Cardinality Constrained Regularized Submodular Maximization(k-CCRSM)problem,in which the objective utility is expressed as the difference between a non-negative submodular and a modular funct...In this work,we study a k-Cardinality Constrained Regularized Submodular Maximization(k-CCRSM)problem,in which the objective utility is expressed as the difference between a non-negative submodular and a modular function.No multiplicative approximation algorithm exists for the regularized model,and most works have focused on designing weak approximation algorithms for this problem.In this study,we consider the k-CCRSM problem in a streaming fashion,wherein the elements are assumed to be visited individually and cannot be entirely stored in memory.We propose two multipass streaming algorithms with theoretical guarantees for the above problem,wherein submodular terms are monotonic and nonmonotonic.展开更多
Recent progress in maximizing submodular functions with a cardinality constraint through centralized and streaming modes has demonstrated a wide range of applications and also developed comprehensive theoretical guara...Recent progress in maximizing submodular functions with a cardinality constraint through centralized and streaming modes has demonstrated a wide range of applications and also developed comprehensive theoretical guarantees.The submodularity was investigated to capture the diversity and representativeness of the utilities,and the monotonicity has the advantage of improving the coverage.Regularized submodular optimization models were developed in the latest studies(such as a house on fire),which aimed to sieve subsets with constraints to optimize regularized utilities.This study is motivated by the setting in which the input stream is partitioned into several disjoint parts,and each part has a limited size constraint.A first threshold-based bicriteria(1/3,2/3/)-approximation for the problem is provided.展开更多
Viral advertising in social networks has arisen as one of the most promising ways to increase brand awareness and product sales. By distributing a limited budget, we can incentivize a set of users as initial adopters ...Viral advertising in social networks has arisen as one of the most promising ways to increase brand awareness and product sales. By distributing a limited budget, we can incentivize a set of users as initial adopters so that the advertising can start from the initial adopters and spread via sociM links to become viral. Despite extensive researches in how to target the most influential users, a key issue is often neglected： how to incentivize the initial adopters. In the problem of influence maximization, the assumption is that each user has a fixed cost for being initial adopters, while in practice, user decisions for accepting the budget to be initial adopters are often probabilistic rather than deterministic. In this paper, we study optimal budget allocation in social networks to maximize the spread of viral advertising. In particular, a concave probability model is introduced to characterize each user＇s utility for being an initial adopter. Under this model, we show that it is NP-hard to find an optimal budget allocation for maximizing the spread of viral advertising. We then present a novel discrete greedy algorithm with near optimal performance, and further propose scaling-up techniques to improve the time-efficiency of our algorithm. Extensive experiments on real-world social graphs are implemented to validate the effectiveness of our algorithm in practice. The results show that our algorithm can outperform other intuitive heuristics significantly in almost all cases.展开更多
基金supported by Natural Science Foundation of China under Grant No.91738202,91438206
文摘In remote terrestrial-satellite networks, caching is a very promising technique to alleviate the burden of space cloudlet(e.g., cache-enabled satellite user terminal) and to improve subscribers' quality of experience(Qo E) in terms of buffering delay and achievable video streaming rate. In this paper, we studied a Qo E-driven caching placement optimization problem for video streaming that takes into account the required video streaming rate and the social relationship among users. Social ties between users are used to designate a set of helpers with caching capability, which can cache popular files proactively when the cloudlet is idle. We model the utility function of Qo E as a logarithmic function. Then, the caching placement problem is formulated as an optimization problem to maximize the user's average Qo E subject to the storage capacity constraints of the helpers and the cloudlets. Furthermore, we reformulate the problem into a monotone submodular optimization problem with a partition matroid constraint, and an efficient greedy algorithm with 1-1 e approximation ratio is proposed to solve it. Simulation results show that the proposed caching placement approach significantly outperforms the traditional approaches in terms of Qo E, while yields about the same delay and hit ratio performance compare to the delay-minimized scheme.
基金This work was supported by the Beijing Natural Science Foundation Project(No.Z220004)the National Natural Science Foundation of China(Nos.11901544 and 12101587)the China Postdoctoral Science Foundation(No.2022M720329).
文摘In this work,we study a k-Cardinality Constrained Regularized Submodular Maximization(k-CCRSM)problem,in which the objective utility is expressed as the difference between a non-negative submodular and a modular function.No multiplicative approximation algorithm exists for the regularized model,and most works have focused on designing weak approximation algorithms for this problem.In this study,we consider the k-CCRSM problem in a streaming fashion,wherein the elements are assumed to be visited individually and cannot be entirely stored in memory.We propose two multipass streaming algorithms with theoretical guarantees for the above problem,wherein submodular terms are monotonic and nonmonotonic.
基金This work was supported by the Beijing Natural Science Foundation Project(No.Z200002)the National Natural Science Foundation of China(Nos.12001523,12131003,and 12101587)+1 种基金the National Innovation and Entrepreneurship Training Program for College Students of Beijing University of Technology(No.GJDC-2022-01-39)the China Postdoctoral Science Foundation(No.2022M720329).
文摘Recent progress in maximizing submodular functions with a cardinality constraint through centralized and streaming modes has demonstrated a wide range of applications and also developed comprehensive theoretical guarantees.The submodularity was investigated to capture the diversity and representativeness of the utilities,and the monotonicity has the advantage of improving the coverage.Regularized submodular optimization models were developed in the latest studies(such as a house on fire),which aimed to sieve subsets with constraints to optimize regularized utilities.This study is motivated by the setting in which the input stream is partitioned into several disjoint parts,and each part has a limited size constraint.A first threshold-based bicriteria(1/3,2/3/)-approximation for the problem is provided.
基金This work was partially supported by the National Natural Science Foundation of China under Grant Nos. 61373128, 61321491, 61472181, 91218302, the Natural Science Foundation of Jiangsu Province of China under Grant No. BK20151392, Jiangsu Key Technique Project （Industry） under Grant No. BE2013116, EU FP7 IRSES MobileCloud Project under Grant No. 612212, the Program B for Outstanding Ph.D. Candidate of Nanjing University, and the Collaborative Innovation Center of Novel Software Technology and Industrialization of Jiangsu Province of China.
文摘Viral advertising in social networks has arisen as one of the most promising ways to increase brand awareness and product sales. By distributing a limited budget, we can incentivize a set of users as initial adopters so that the advertising can start from the initial adopters and spread via sociM links to become viral. Despite extensive researches in how to target the most influential users, a key issue is often neglected： how to incentivize the initial adopters. In the problem of influence maximization, the assumption is that each user has a fixed cost for being initial adopters, while in practice, user decisions for accepting the budget to be initial adopters are often probabilistic rather than deterministic. In this paper, we study optimal budget allocation in social networks to maximize the spread of viral advertising. In particular, a concave probability model is introduced to characterize each user＇s utility for being an initial adopter. Under this model, we show that it is NP-hard to find an optimal budget allocation for maximizing the spread of viral advertising. We then present a novel discrete greedy algorithm with near optimal performance, and further propose scaling-up techniques to improve the time-efficiency of our algorithm. Extensive experiments on real-world social graphs are implemented to validate the effectiveness of our algorithm in practice. The results show that our algorithm can outperform other intuitive heuristics significantly in almost all cases.
