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

Pricing Mechanisms for Crowd-Sensed Spatial-Statistics-Based Radio Mapping

IEEE TRANSACTIONS ON COGNITIVE COMMUNICATIONS AND NETWORKING 2017年第2期3卷 242-254页

作者： Ying, Xuhang Roy, Sumit Poovendran, Radha Univ Washington Dept Elect Engn Seattle WA 98195 USA

Networking on white spaces (i.e., locally unused spectrum) relies on active monitoring of spectrum usage. Spectrum databases based on empirical radio propagation models are widely adopted but shown to be error-prone, since they do not account for built environments (e.g., trees and man-made buildings). As an alternative, crowd-sensed radio mapping by mobile clients who acquire local spectrum data and transmit it to a central aggregator (platform) for processing, results in more accurate radio maps. Success of such crowd-sensing systems presumes some incentive mechanisms to attract user participation. In this paper, we assume that the platform who constructs radio environment maps makes one-time offers (the incentive for participation) to users, and collects data from those who accept the offers. We design pricing mechanisms based on expected utility (EU) maximization, where EU captures the tradeoff between radio mapping performance (location and data quality), crowd-sensing cost, and uncertainty in offer outcomes (i.e., possible expiration and rejection). Specifically, we consider both sequential offering, where one best price offer is sent to the best user in each round, and batched offering, where a batch of offers is made in each round. For the later, we show that EU is submodular in the discrete domain, and propose a mechanism that first fixes the pricing rule, and selects users based on unconstrained submodular maximization (USM);it then compares different pricing rules to find the best batch of offers in each round. We show that USM-based user selection has provable performance guarantee. Proposed mechanisms are evaluated and compared against utility-maximization-based baseline mechanisms.

关键词： Radio environment mapping spatial statistics crowd-sensing pricing mechanism expected utility maximization unconstrained submodular maximization

来源：评论

学校读者我要写书评

暂无评论

Deterministic Algorithms for submodular maximization Problems

引用

ACM TRANSACTIONS ON ALGORITHMS 2018年第3期14卷 1–20页

作者： Buchbinder, Niv Feldman, Moran Tel Aviv Univ Dept Stat & Operat Res IL-39040 Tel Aviv Israel Ecole Polytech Fed Lausanne Lausanne Switzerland Open Univ Israel Dept Math & Comp Sci IL-4353701 Raanana Israel

Randomization is a fundamental tool used in many theoretical and practical areas of computer science. We study here the role of randomization in the area of submodular function maximization. In this area, most algorithms are randomized, and in almost all cases the approximation ratios obtained by current randomized algorithms are superior to the best results obtained by known deterministic algorithms. Derandomization of algorithms for general submodular function maximization seems hard since the access to the function is done via a value oracle. This makes it hard, for example, to apply standard derandomization techniques such as conditional expectations. Therefore, an interesting fundamental problem in this area is whether randomization is inherently necessary for obtaining good approximation ratios. In this work, we give evidence that randomization is not necessary for obtaining good algorithms by presenting a new technique for derandomization of algorithms for submodular function maximization. Our high level idea is to maintain explicitly a (small) distribution over the states of the algorithm, and carefully update it using marginal values obtained from an extreme point solution of a suitable linear formulation. We demonstrate our technique on two recent algorithms for unconstrained submodular maximization and for maximizing a submodular function subject to a cardinality constraint. In particular, for unconstrained submodular maximization we obtain an optimal deterministic 1/2-approximation showing that randomization is unnecessary for obtaining optimal results for this setting.

关键词： submodular function maximization derandomization unconstrained submodular maximization

来源：评论

学校读者我要写书评

暂无评论

A fast double greedy algorithm for non-monotone DR-submodular function maximization

引用

DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS 2020年第1期12卷

作者： Gu, Shuyang Shi, Ganquan Wu, Weili Lu, Changhong Univ Texas Dallas Dept Comp Sci 800 W Campbell Rd Richardson TX 75080 USA East China Normal Univ Sch Math Sci Shanghai Key Lab PMMP Shanghai 200241 Peoples R China

We study the problem of maximizing non-monotone diminish return (DR)-submodular function on the bounded integer lattice, which is a generalization of submodular set function. DR-submodular functions consider the case that we can choose multiple copies for each element in the ground set. This generalization has many applications in machine learning. In this paper, we propose a 1/2-approximation algorithm with a running time of O(n log B), where n is the size of the ground set, B is the upper bound of integer lattice. Discovering important properties of DR-submodular function, we propose a fast double greedy algorithm which improves the running time.

关键词： DR-submodular bounded integer lattice unconstrained submodular maximization double greedy

来源：评论

学校读者我要写书评

暂无评论

Deterministic Algorithms for submodular maximization Problems 27

Deterministic Algorithms for Submodular Maximization Problem...

引用

27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)

ISBN: (纸本)9781510819672

关键词： submodular function maximization derandomization unconstrained submodular maximization

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：