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

Faster FPTASes for counting and random generation of Knapsack solutions

INFORMATION AND COMPUTATION 2019年 267卷 135-144页

作者： Rizzi, Romeo Tomescu, Alexandru, I Univ Verona Dept Comp Sci Verona Italy Univ Helsinki Dept Comp Sci HIIT Helsinki Finland

In the #P-complete problem of counting 0/1 Knapsack solutions, the input consists of a sequence of n nonnegative integer weights w(1), ..., w(n) and an integer C, and we have to find the number of subsequences (subsets of indices) with total weight at most C. We give faster and simpler fully polynomial-time approximation schemes (FPTASes) for this problem, and for its random generation counterpart. Our method is based on dynamic programming and discretization of large numbers through floating-point arithmetic. We improve both deterministic counting FPTASes from Gopalan et al. (2011) [9], Stefankovic et al. (2012) [6] and the randomized counting and random generation algorithms in Dyer (2003) [5]. Our method is general, and it can be directly applied on top of combinatorial decompositions (such as dynamic programming solutions) of various problems. For example, we also improve the complexity of the problem of counting 0/1 Knapsack solutions in an arc-weighted DAG. (C) 2019 The Authors. Published by Elsevier Inc.

关键词： 0/1 Knapsack problem approximation algorithm Counting problem Sampling Dynamic programming Directed acyclic graph

来源：评论

学校读者我要写书评

暂无评论

Improved PTAS for the constrained k-means problem

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2019年第4期37卷 1091-1110页

作者： Feng, Qilong Hu, Jiaxin Huang, Neng Wang, Jianxin Cent South Univ Sch Informat Sci & Engn Changsha 410083 Hunan Peoples R China

The k-means problem has been paid lots of attention in many fields, and each cluster of the k-means problem always satisfies locality property. In this paper, we study the constrained k-means problem, where the clusters do not satisfy locality property and can be an arbitrary partition of the set of points. Ding and Xu presented a unified framework with running time O(2poly(k/)(log n) k+ 1nd) by applying uniform sampling and simplex lemma techniques such that a collection of size O(2poly(k/)(log n) k+ 1) of candidate sets containing approximate centers is obtained. Then, the collection is enumerated to get the one that can induce a (1 + )-approximation solution for the constrained k-means problem. By applying D2-sampling technique, Bhattacharya, Jaiswal, and Kumar presented an algorithm with running time O(2 O (k/) nd), which is bounded by O(2k (2123ek 3) 64k/knd). The algorithm outputs a collection of size O(2k (2123ek 3) 64k/) of candidate sets containing approximate centers. In this paper, we present an algorithm with running time O((1891ek 2) 8k/nd) such that a collection of size O((1891ek 2) 8k/n) of candidate sets containing approximate centers can be obtained.

关键词： k-means approximation algorithm PTAS

来源：评论

学校读者我要写书评

暂无评论

Two-agent scheduling problems with the general position-dependent processing time

引用

THEORETICAL COMPUTER SCIENCE 2019年 796卷 90-98页

作者： Yang, Liya Lu, Xiwen East China Univ Sci & Technol Sch Sci Dept Math Shanghai 200237 Peoples R China

Two-agent scheduling problems with the general position-dependent processing time are studied in this paper. Under the constraint that the makespan of one agent is upper bounded, we show that the problem to minimize the other agent's makespan on a single machine is NP-hard. A polynomial time algorithm is proposed for the problem with learning or deteriorating effects. To minimize the total completion time of one agent's jobs on a single machine, we design a dynamic programming algorithm and an FPTAS. Moreover, we also provide dynamic programming algorithms and FPTASs for the problem to minimize one agent's makespan and the problem to minimize the total completion time of the other agent's jobs on parallel machines. (C) 2019 Elsevier B.V. All rights reserved.

关键词： Position-dependent scheduling Learning effect Deteriorating effect approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Fast Deployment of UAV Networks for Optimal Wireless Coverage

引用

IEEE TRANSACTIONS ON MOBILE COMPUTING 2019年第3期18卷 588-601页

作者： Zhang, Xiao Duan, Lingjie Singapore Univ Technol & Design Engn Syst & Design Pillar Singapore 487372 Singapore

Unmanned Aerial Vehicle (UAV) networks have emerged as a promising technique to rapidly provide wireless coverage to a geographical area, where a flying UAV can be fast deployed to serve as cell site. Existing work on UAV-enabled wireless networks overlook the fast UAV deployment for wireless coverage, and such deployment problems have only been studied recently in sensor networks. Unlike sensors, UAVs should be deployed to the air and they are generally different in flying speed, operating altitude and wireless coverage radius. By considering such UAV heterogeneity to cover the whole target area, this paper studies two fast UAV deployment problems: one is to minimize the maximum deployment delay among all UAVs (min-max) for fairness consideration, and the other is to minimize the total deployment delay (min-sum) for efficiency consideration. We prove both min-max and min-sum problems are NP-complete in general. When dispatching UAVs from the same location, we present an optimal algorithm of low computational complexity O(n(2)) for the min-max problem. When UAVs are dispatched from different locations, we propose to preserve their location order during deployment and successfully design a fully polynomial time approximation scheme (FPTAS) of computation complexity O(n(2)log 1/epsilon) to arbitrarily approach the global optimum with relative error epsilon. The min-sum problem is more challenging. When UAVs are dispatched from the same initial location, we present an approximation algorithm of linear time. As for the general case, we further reformulate it as a dynamic program and propose a pseudo polynomial-time algorithm to solve it optimally.

关键词： Unmanned aerial vehicle networks wireless coverage fast deployment approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Identifying structural hole spanners to maximally block information propagation

引用

INFORMATION SCIENCES 2019年 505卷 100-126页

作者： Xu, Wenzheng Li, Tong Liang, Weifa Yu, Jeffrey Xu Yang, Ning Gao, Shaobing Sichuan Univ Coll Comp Sci Chengdu 610065 Sichuan Peoples R China Australian Natl Univ Canberra ACT 0200 Australia Chinese Univ Hong Kong Dept Syst Engn & Engn Management Hong Kong Peoples R China

An individual can obtain high profits by playing a bridge role among different communities in a social network, thus acquiring more potential resources from the communities or having control over the information transmitted within the network. Such an individual usually is referred to as a structural hole spanner in the network. Existing studies on the identification of important structural hole spanners focused on only whether a person bridges multiple communities without emphasizing the tie strength of that person connecting to his bridged communities. However, a recent study showed that such tie strength heavily affects the profit the person obtains by playing the bridge role. In this study, we aim to identify the most important hole spanners in a large-scale social network who have strong ties with their bridged communities. Accordingly, we first formulate the top-k structural hole spanner problem to identify k nodes in the network such that their removals will block the maximum numbers of information propagations within the network. Due to the NP-hardness of the problem, we then propose a novel (1 - epsilon)-approximation algorithm, where epsilon is a given constant with 0 < epsilon < 1. Although the approximate solution provides a guaranteed performance, it takes some time to deliver the solution, which may not be acceptable in practice. Therefore, we devise a fast, yet scalable, heuristic algorithm for the problem. Finally, we evaluate the performance of the proposed algorithms through extensive experiments, using real-world datasets. The experimental results show that the proposed algorithms are very promising. Especially, the found hole spanners block more than 24% of the information propagations compared to existing algorithms. (C) 2019 Elsevier Inc. All rights reserved.

关键词： Social networks Top-k structural hole spanners Block information propagations approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Bounds on the burning numbers of spiders and path-forests

引用

THEORETICAL COMPUTER SCIENCE 2019年 794卷 12-19页

作者： Bonato, Anthony Lidbetter, Thomas Ryerson Univ Dept Math Toronto ON M5B 2K3 Canada Rutgers State Univ Dept Management Sci & Informat Syst Newark NJ 07102 USA

Graph burning is one model for the spread of memes and contagion in social networks. The corresponding graph parameter is the burning number of a graph G, written b(G), which measures the speed of the social contagion. While it is conjectured that the burning number of a connected graph of order n is at most [root n], this remains open in general and in many graph families. We prove the conjectured bound for spider graphs, which are trees with exactly one vertex of degree at least 3. To prove our result for spiders, we develop new bounds on the burning number for path-forests, which in turn leads to a 3/2-approximation algorithm for computing the burning number of path-forests. (C) 2018 Elsevier B.V. All rights reserved.

关键词： Graphs Burning number Trees Spiders Path-forest approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Minimum budget for misinformation blocking in online social networks

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2019年第4期38卷 1101-1127页

作者： Pham, Canh V. Phu, Quat V. Hoang, Huan X. Pei, Jun Thai, My T. Vietnam Natl Univ Univ Engn & Technol Hanoi Vietnam Univ Florida Dept Comp & Informat Sci & Engn Gainesville FL 32611 USA Peoples Secur Acad Hanoi Vietnam Hefei Univ Technol Sch Management Hefei Anhui Peoples R China

Preventing misinformation spreading has recently become a critical topic due to an explosive growth of online social networks. Instead of focusing on blocking misinformation with a given budget as usually studied in the literatures, we aim to find the smallest set of nodes (minimize the budget) whose removal from a social network reduces the influence of misinformation (influence reduction) greater than a given threshold, called the Targeted Misinformation Blocking problem. We show that this problem is #P-hard under Linear Threshold and NP-hard under Independent Cascade diffusion models. We then propose several efficient algorithms, including approximation and heuristic algorithms to solve the problem. Experiments on real-world network topologies show the effectiveness and scalability of our algorithms that outperform other state-of-the-art methods.

关键词： Misinformation Social network approximation algorithm Optimization

来源：评论

学校读者我要写书评

暂无评论

On the expected diameter, width, and complexity of a stochastic convex hull

引用

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS 2019年 82卷 16-31页

作者： Xue, Jie Li, Yuan Janardan, Ravi Univ Minnesota Twin Cities Dept Comp Sci & Engn Minneapolis MN 55455 USA

We investigate several computational problems related to the stochastic convex hull (SCH). Given a stochastic dataset consisting of n points in R-d each of which has an existence probability, a SCH refers to the convex hull of a realization of the dataset, i.e., a random sample including each point with its existence probability. We are interested in computing certain expected statistics of a SCH, including diameter, width, and combinatorial complexity. For diameter, we establish a deterministic 1.633-approximation algorithm with a time complexity polynomial in both n and d. For width, two approximation algorithms are provided: a deterministic O(1)-approximation running in O(n(d+1) log n) time, and a fully polynomial-time randomized approximation scheme (FPRAS). For combinatorial complexity, we propose an exact O(n(d))-time algorithm. Our solutions exploit many geometric insights in Euclidean space, some of which might be of independent interest. (C) 2019 Elsevier B.V. All rights reserved.

关键词： Convex hull Uncertain data Expectation approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Approximately Coloring Graphs Without Long Induced Paths

引用

algorithmICA 2019年第8期81卷 3186-3199页

作者： Chudnovsky, Maria Schaudt, Oliver Spirkl, Sophie Stein, Maya Zhong, Mingxian Princeton Univ Princeton NJ 08544 USA Univ Cologne Cologne Germany Rhein Westfal TH Aachen Aachen Germany Rutgers State Univ Piscataway NJ 08854 USA Univ Chile Santiago Chile Columbia Univ New York NY 10027 USA CUNY Lehman Coll Bronx NY 10468 USA

It is an open problem whether the 3-coloring problem can be solved in polynomial time in the class of graphs that do not contain an induced path on t vertices, for fixed t. We propose an algorithm that, given a 3-colorable graph without an induced path on t vertices, computes a coloring with max 5, 2 t-1 2 -2 many colors. If the input graph is triangle-free, we only need max 4, t-1 2 + 1 many colors. The running time of our algorithm is O((3t-2 + t2) m + n) if the input graph has n vertices and m edges.

关键词： Graph coloring Forbidden induced paths approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

algorithm Design and Analysis for Wireless Relay Network Deployment Problem

引用

IEEE TRANSACTIONS ON MOBILE COMPUTING 2019年第10期18卷 2257-2269页

作者： Gao, Xiaofeng Lu, Junwei Wang, Haotian Wu, Fan Chen, Guihai Shanghai Jiao Tong Univ Dept Comp Sci & Engn Shanghai Key Lab Scalable Comp & Syst Shanghai 200000 Peoples R China SUNY Stony Brook Dept Comp Sci Stony Brook NY 11794 USA

Wireless relay network has been widely used in many applications to improve the wireless service. In this paper, we aim to maximize users' satisfaction by deploying limited number of relays in a target region to form a wireless relay network, and define the Deployment of Cooperative Relay (DoCR) problem, which is proved to be NP-complete. We first propose two approximation algorithms, an O(log n) algorithm that utilizes the algorithms for budget weighted Steiner tree problem with novel position weighting assignment, and an O(root k) algorithm that iteratively scans potential positions and determines relay placement plan with the help of submodular function theory, partition technique, and greedy strategy. We name them Relay Effective Deployment Algoirthm (REDA) and Submodular Iterative Deployment algorithm (SIDA), respectively. We further propose Gradient-Descent Based algorithm (GDBA), a heuristic method, to solve the DoCR problem releasing potential location constraints. Our extensive experiments indicate that the algorithms we propose can significantly improve the total satisfaction of the network. Furthermore, we establish a testbed using USRP to showcase our designs in real scenarios. To the best of our knowledge, we are the first to propose approximation algorithms for relay placement problem to maximize user satisfaction, which has both theoretical and practical significance in the related area.

关键词： Wireless relay networks approximation algorithm steiner tree submodular function

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：