检索结果-内蒙古大学图书馆

Approximation Algorithm and Applications for Connected submodular function maximization Problems

IEEE TRANSACTIONS ON NETWORKING 2025年第1期33卷 241-254页

作者： Wang, Ziming Li, Jing Xue, He Xu, Wenzheng Liang, Weifa Xu, Zichuan Peng, Jian Zhou, Pan Jia, Xiaohua Das, Sajal K. Sichuan Univ Coll Comp Sci Chengdu 610065 Peoples R China Sichuan Univ West China Hosp 2 Chengdu 610065 Peoples R China City Univ Hong Kong Dept Comp Sci Hong Kong Peoples R China Sichuan Fire Sci & Technol Res Inst MEM Chengdu 610065 Peoples R China Dalian Univ Technol Sch Software Dalian 116621 Peoples R China Huazhong Univ Sci & Technol Sch Cyber Sci & Engn Wuhan 430074 Peoples R China Missouri Univ Sci & Technol Dept Comp Sci Rolla MO 65409 USA

In this paper, we study a connected submodular function maximization problem, which arises from many applications including deploying UAV networks to serve users and placing sensors to cover Points of Interest (PoIs). Specifically, given a budget K , the problem is to find a subset S with K nodes from a graph G , so that a given submodular function f(S) on S is maximized and the induced subgraph G[S] by the nodes in S is connected, where the submodular function f can be used to model many practical application problems, such as the number of users within different service areas of the deployed UAVs in S , the sum of data rates of users served by the UAVs, the number of covered PoIs by placed sensors, etc. We then propose a novel 1-1/e/2h+2 -approximation algorithm for the problem, improving the best approximation ratio 1-1/e/2h+3 for the problem so far, through estimating a novel upper bound on the problem and designing a smart graph decomposition technique, where e is the base of the natural logarithm, h is a parameter that depends on the problem and its typical value is 2. In addition, when h=2 , the algorithm approximation ratio is at least 1-1/e/5 and may be as large as 1 in some special cases when K <= 23 , and is no less than 1-1/e/6 when K >= 24 , compared with the current best approximation ratio 1-1/e/7(=1-1/e/2h+3) for the problem. Finally, experimental results in the application of deploying a UAV network demonstrate that, the number of users within the service area of the deployed UAV network by the proposed algorithm is up to 7.5% larger than those by existing algorithms, and the throughput of the deployed UAV network by the proposed algorithm is up to 9.7% larger than those by the algorithms. Furthermore, the empirical approximation ratio of the proposed algorithm is between 0.7 and 0.99, which is close to the theoretical maximum value one.

关键词： Sensors Autonomous aerial vehicles Approximation algorithms Disasters Wireless sensor networks Capacitive sensors Water pollution Social networking (online) Contamination Computer science UAV deployment sensor placement submodular function maximization approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

submodular function maximization VIA THE MULTILINEAR RELAXATION AND CONTENTION RESOLUTION SCHEMES

引用

SIAM JOURNAL ON COMPUTING 2014年第6期43卷 1831-1879页

作者： Chekuri, Chandra Vondrak, Jan Zenklusen, Rico Univ Illinois Dept Comp Sci Urbana IL 61801 USA IBM Almaden Res Ctr San Jose CA 95120 USA ETH Dept Math CH-8092 Zurich Switzerland Johns Hopkins Univ Dept Appl Math & Stat Baltimore MD 21218 USA

We consider the problem of maximizing a nonnegative submodular set function f : 2(N) -> R+ over a ground set N subject to a variety of packing-type constraints including (multiple) matroid constraints, knapsack constraints, and their intersections. In this paper we develop a general framework that allows us to derive a number of new results, in particular, when f may be a nonmonotone function. Our algorithms are based on (approximately) maximizing the multilinear extension F of f over a polytope P that represents the constraints, and then effectively rounding the fractional solution. Although this approach has been used quite successfully, it has been limited in some important ways. We overcome these limitations as follows. First, we give constant factor approximation algorithms to maximize F over a downward-closed polytope P described by an efficient separation oracle. Previously this was known only for monotone functions. For nonmonotone functions, a constant factor was known only when the polytope was either the intersection of a fixed number of knapsack constraints or a matroid polytope. Second, we show that contention resolution schemes are an effective way to round a fractional solution, even when f is nonmonotone. In particular, contention resolution schemes for different polytopes can be combined to handle the intersection of different constraints. Via linear programming duality we show that a contention resolution scheme for a constraint is related to the correlation gap of weighted rank functions of the constraint. This leads to an optimal contention resolution scheme for the matroid polytope. Our results provide a broadly applicable framework for maximizing linear and submodular functions subject to independence constraints. We give several illustrative examples. Contention resolution schemes may find other applications.

关键词： submodular function maximization approximation algorithms randomized algorithms contention resolution

来源：评论

学校读者我要写书评

暂无评论

submodular function maximization via the Multilinear Relaxation and Contention Resolution Schemes 11

Submodular Function Maximization via the Multilinear Relaxat...

引用

43rd ACM Symposium on Theory of Computing

作者： Chekuri, Chandra Vondrak, Jan Zenklusen, Rico Univ Illinois Dept Comp Sci Urbana IL 61801 USA

ISBN: (纸本)9781450306911

We consider the problem of maximizing a non-negative submodular set function f : 2(N) -> R+ over a ground set N subject to a variety of packing type constraints including (multiple) matroid constraints, knapsack constraints, and their intersections. In this paper we develop a general framework that allows us to derive a number of new results, in particular when f may be a non-monotone function. Our algorithms are based on (approximately) solving the multilinear extension F of f [5] over a polytope P that represents the constraints, and then effectively rounding the fractional solution. Although this approach has been used quite successfully in some settings [6, 22, 24, 13, 3], it has been limited in some important ways. We overcome these limitations as follows. First, we give constant factor approximation algorithms to maximize F over an arbitrary down-closed polytope P that has an efficient separation oracle. Previously this was known only for monotone functions [36]. For non-monotone functions, a constant factor was known only when the polytope was either the intersection of a fixed number of knapsack constraints [24] or a matroid polytope [37, 30]. Second, we show that contention resolution schemes are an effective way to round a fractional solution, even when f is non-monotone. In particular, contention resolution schemes for different polytopes can be combined to handle the intersection of different constraints. Via LP duality we show that a contention resolution scheme for a constraint is related to the correlation gap [1] of weighted rank functions of the constraint. This leads to an optimal contention resolution scheme for the matroid polytope. Our results provide a broadly applicable framework for maximizing linear and submodular functions subject to independence constraints. We give several illustrative examples. Contention resolution schemes may find other applications.

关键词： Approximation algorithm submodular function maximization matroid contention resolution scheme independence constraint

来源：评论

学校读者我要写书评

暂无评论

Semi-streaming Algorithms for submodular function maximization Under b-Matching, Matroid, and Matchoid Constraints

引用

ALGORITHMICA 2024年第11期86卷 3598-3628页

作者： Huang, Chien-Chung Sellier, Francois Univ PSL DI ENS CNRS Ecole Normale Super Paris France Ecole Polytech Inst Polytech Paris Palaiseau France

We consider the problem of maximizing a non-negative submodular function under the b-matching constraint, in the semi-streaming model. When the function is linear, monotone, and non-monotone, we obtain the approximation ratios of 2+epsilon, 3+2 root 2 approximate to 5.828, and 4+2 root 3 approximate to 7.464, respectively. We also consider a generalized problem, where a k-uniform hypergraph is given, along with an extra matroid or a k '-matchoid constraint imposed on the edges, with the same goal of finding a b-matching that maximizes a submodular function. When the extra constraint is a matroid, we obtain the approximation ratios of k + 1 + epsilon, k + 2 root k+1 + 2, and k + 2 root k+2 +3 for linear, monotone and non-monotone submodular functions, respectively. When the extra constraint is a k '-matchoid, we attain the approximation ratio 8/3k + 64/9k '+O(1) for general submodular functions.

关键词： Maximum weight matching submodular function maximization Streaming Matroid Matchoid

来源：评论

学校读者我要写书评

暂无评论

APPROXIMABILITY OF MONOTONE submodular function maximization UNDER CARDINALITY AND MATROID CONSTRAINTS IN THE STREAMING MODEL

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2022年第1期36卷 355-382页

作者： Huang, Chien-Chung Kakimura, Naonori Mauras, Simon Yoshida, Yuichi PSL CNRS ENS F-75005 Paris France Keio Univ Yokohama Kanagawa 2238522 Japan Univ Paris CNRS IRIF F-75013 Paris France Natl Inst Informat Chiyoda Ku Tokyo 1018430 Japan

Maximizing a monotone submodular function under various constraints is a classical and intensively studied problem. However, in the single-pass streaming model, where the elements arrive one by one and an algorithm can store only a small fraction of input elements, there is large gap in our knowledge, even though several approximation algorithms have been proposed in the literature. In this work, we present the first lower bound on the approximation ratios for cardinality and matroid constraints that beat 1 - 1/e the single-pass streaming model. Let n be the number of elements in the stream. Then, we prove that any (randomized) streaming algorithm for a cardinality constraint with approximation ratio 2-root 2+epsilon requires Omega(n/K-2) space for any epsilon > 0, where K is the size limit of the output set. We also prove that any (randomized) streaming algorithm for a (partition) matroid constraint with approximation ratio K/2K-1 requires Omega(n/K-2) space for any epsilon > 0, where K is the rank of the given matroid. In addition, we give streaming algorithms that assume access to the objective function via a weak oracle that can only be used to evaluate function values on feasible sets. Specifically, we show weak-oracle streaming algorithms for cardinality and matroid constraints with approximation ratios K/2K-1 and 1/2, respectively, whose space complexity is exponential in K but is independent of n. The former one exactly matches the known inapproximability result for a cardinality constraint in the weak oracle model. The latter one almost matches our lower bound of K for a matroid constraint, which almost settles the approximation ratio for a matroid constraint K/2K-1 that can be obtained by a streaming algorithm whose space complexity is independent of n.

关键词： submodular function maximization streaming model approximation algorithm inapproximability

来源：评论

学校读者我要写书评

暂无评论

Constraint generation approaches for submodular function maximization leveraging graph properties

引用

JOURNAL OF GLOBAL OPTIMIZATION 2024年第2期88卷 377-394页

作者： Csokas, Eszter Vinko, Tamas Univ Szeged Dept Computat Optimizat Szeged Hungary

submodular function maximization is an attractive optimization model and also a well-studied problem with a variety of algorithms available. Constraint generation (CG) approaches are appealing techniques to tackle the problem with, as the mixed-integer programming formulation of the problem suffers from the exponential size of the number of constraints. Most of the problems in these topics are of combinatorial nature and involve graphs on which the maximization is defined. Inspired by the recent work of Uematsu et al. (J Oper Res Soc Jpn 63:41-59, 2020), in this paper we introduce variants of the CG algorithm which take into account certain properties of the input graph aiming at informed selection of the constraints. Benchmarking results are shown to demonstrate the efficiency of the proposed methods.

关键词： submodular function maximization Combinatorial optimization Integer programming

来源：评论

学校读者我要写书评

暂无评论

Multi-Pass Streaming Algorithms for Monotone submodular function maximization

引用

THEORY OF COMPUTING SYSTEMS 2022年第1期66卷 354-394页

作者： Huang, Chien-Chung Kakimura, Naonori Ecole Normale Super CNRS Paris France Keio Univ Yokohama Kanagawa Japan

We consider maximizing a monotone submodular function under a cardinality constraint or a knapsack constraint in the streaming setting. In particular, the elements arrive sequentially and at any point of time, the algorithm has access to only a small fraction of the data stored in primary memory. We propose the following streaming algorithms taking O(epsilon(-1)) passes: (1) a (1-e(-1)-epsilon)-approximation algorithm for the cardinality-constrained problem, (2) a (0.5 - epsilon)-approximation algorithm for the knapsack-constrained problem. Both of our algorithms run deterministically in O* (n) time, using O* (K) space, where n is the size of the ground set and K is the size of the knapsack. Here the term O* hides a polynomial of log K and epsilon(-1). Our streaming algorithms can also be used as fast approximation algorithms. In particular, for the cardinality-constrained problem, our algorithm takes O (n epsilon(-1) log (epsilon(-1) log K)) time, improving on the algorithm of Badanidiyuru and Vondrak that takes O (n epsilon(-1)log (epsilon(-1) K)) time.

关键词： Streaming algorithms Approximation algorithms submodular function maximization

来源：评论

学校读者我要写书评

暂无评论

Simultaneous Approximation of Multi-criteria submodular function maximization

引用

Journal of the Operations Research Society of China 2014年第3期2卷 271-290页

作者： Dong-Lei Du Yu Li Nai-Hua Xiu Da-Chuan Xu Faculty of Business Administration University of New BrunswickFrederictonNB E3B 9Y2Canada Department of Mathematics School of ScienceBeijing Jiaotong University3 ShangyuancunHaidian DistrictBeijing 100044China Department of Applied Mathematics Beijing University of Technology100 PingleyuanChaoyang DistrictBeijing 100124China

Recently intensive interest has been raised on approximation of the NPhard submodular maximization problem due to their theoretical and practical *** this work,we extend this line of research by focusing on the simultaneous approximation of multiple submodular function *** address the existence and nonexistence results for both deterministic and randomized approximation when the submodular functions are symmetric and asymmetric,respectively,along with algorithmic *** offer complete characterization of the symmetric case and partial results on the asymmetric case.

关键词： Multi-criteria submodular function maximization Approximation algorithm Existence

来源：评论

学校读者我要写书评

暂无评论

Very Fast Streaming submodular function maximization

Very Fast Streaming Submodular Function Maximization

引用

21st Joint European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML PKDD)

作者： Buschjaeger, Sebastian Honysz, Philipp-Jan Pfahler, Lukas Morik, Katharina TU Dortmund Artificial Intelligence Grp Dortmund Germany

ISBN: (纸本)9783030865238;9783030865221

Data summarization has become a valuable tool in understanding even terabytes of data. Due to their compelling theoretical properties, submodular functions have been the focus of summarization algorithms. submodular function maximization is a well-studied problem with a variety of algorithms available. These algorithms usually offer worst-case guarantees to the expense of higher computation and memory requirements. However, many practical applications do not fall under this mathematical worst-case but are usually much more well-behaved. We propose a new submodular function maximization algorithm called ThreeSieves that ignores the worst-case and thus uses fewer resources. Our algorithm selects the most informative items from a data-stream on the fly and maintains a provable performance in most cases on a fixed memory budget. In an extensive evaluation, we compare our method against 6 state-of-the-art algorithms on 8 different datasets including data with and without concept drift. We show that our algorithm outperforms the current state-of-the-art in the majority of cases and, at the same time, uses fewer resources.

关键词： submodular function maximization Streaming data Data summarization

来源：评论

学校读者我要写书评

暂无评论

Approximation Algorithm for Connected submodular function maximization Problems 44

Approximation Algorithm for Connected Submodular Function Ma...

引用

44th IEEE International Conference on Distributed Computing Systems (ICDCS)

作者： Xu, Wenzheng Xue, He Li, Ling Liang, Weifa Xu, Zichuan Zhou, Pan Jia, Xiaohua Das, Sajal K. Sichuan Univ Coll Comp Sci Chengdu Peoples R China Sichuan Fire Sci & Technol Res Inst MEM Chengdu Peoples R China Hong Kong Polytech Univ Dept Comp Hong Kong Peoples R China City Univ Hong Kong Dept Comp Sci Hong Kong Peoples R China Dalian Univ Technol Sch Software Dalian Peoples R China Huazhong Univ Sci & Technol Sch Cyber Sci & Engn Wuhan Peoples R China Missouri Univ Sci & Technol Dept Comp Sci Rolla MO 65409 USA

ISBN: (纸本)9798350386066;9798350386059

In this paper, we study a connected submodular function maximization problem, which arises from many applications including deploying UAV networks to serve users and placing sensors to cover Points of Interest (PoIs). Specifically, given a budget K, the problem is to find a subset S with K nodes from a graph G so that a given submodular function f(S) on S is maximized while the induced subgraph G[S] by the nodes in S is connected, where the submodular function f can be used to model many practical application problems, such as the number of users within different service areas of the deployed UAVs in S, the sum of data rates of users served by the UAVs, the number of covered PoIs by placed sensors, etc. We then propose a novel 1-1/e/2h+2-approximation algorithm for the problem, improving the best approximation ratio 1-1/e/2h+2 for the problem so far, through estimating a novel upper bound on the problem and designing a smart graph decomposition technique, where e is the base of the natural logarithm, h is a parameter depends on the problem and its typical value is 2. In addition, when h = 2, the algorithm approximation ratio is at least 1-1/e/5 and may be as large as 1 in some special cases when K <= 21, and is no less than 1-1/e/6 when K >= 22, compared with the current best approximation ratio 1-1/e/7 (= 1-1/e/2h+3) for the problem. We finally evaluate the algorithm performance in the application of deploying a UAV network. Experimental results demonstrate the number of users within the service area of the deployed UAV network by the proposed algorithm is up to 7.5% larger than those by existing algorithms, and its empirical approximation ratio is between 0.7 and 0.99, which is close to the theoretical maximum value one.

关键词： UAV deployment sensor placement submodular function maximization approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：