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

15th RIVF International Conference on Computing and Communication Technologies (RIVF)

作者： Pham, Phuong N. H. Nguyen, Bich-Ngan T. Pham, Canh, V Nghia, Nghia D. Snasel, Vaclav HCMC Univ Food Ind Ho Chi Minh City Vietnam Phenikaa Univ Fac Comp Sci ORlab Hanoi Vietnam Peoples Secur Acad Fac Informat Secur Hanoi Vietnam Tech Univ Ostrava Ostrava Czech Republic

ISBN: (纸本)9781665404358

In the context of viral marketing in Online Social Networks (OSNs), companies often find some users (called a seed set) to initiate the spread of their product's information so that the benefit gained exceeds a given threshold. However, in a realistic scenario, marketing strategies often change so the selection of a seed set for a particular threshold is not enough to provide an effective solution. Motivated by this phenomenon, we investigate the Multiple Benefit Thresholds (MBT), defined as follows: Given a social network under an information diffusion and a set of thresholds T = {T-1, T-2, center dot center dot center dot , T-k}, the problem finds seed sets S-1, S-2, center dot center dot center dot , S-k with the minimal cost so that their benefit gained after the influence process are at least T-1, T-2, center dot center dot center dot , T-k, respectively. To find the solution, we propose an efficient algorithm with theoretical guarantees, named Efficient Sampling for Selecting Multiple seed sets (ESSM) by developing an algorithmic framework and utilizing the sampling technique for estimating the objective function. We perform extensive experiments using some real networks show that the effective and performance of our algorithm, which outperforms other algorithms in term both the cost and running time.

关键词： Social Network Influence Influence Maximization Multiple Benefits approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

REDUCING PATH TSP TO TSP

引用

SIAM JOURNAL ON COMPUTING 2022年第3期51卷 24-53页

作者： Traub, Vera Vygen, Jens Zenklusen, Rico Swiss Fed Inst Technol CH-8092 Zurich Switzerland Univ Bonn Res Inst Discrete Math D-53113 Bonn Germany Univ Bonn Hausdorff Ctr Math D-53113 Bonn Germany

We present a black-box reduction from the path version of the traveling salesman problem (Path TSP) to the classical tour version (TSP). More precisely, given an alpha -approximation algorithm for TSP, then, for any epsilon > 0, we obtain an (alpha + epsilon)-approximation algorithm for the more general Path TSP. This reduction implies that the approximability of Path TSP is the same as for TSP, up to an arbitrarily small error. This avoids future discrepancies between the best known approximation factors achievable for these two problems, as they have existed until very recently. A well-studied special case of TSP, Graph TSP, asks for tours in unit-weight graphs. Our reduction shows that any alpha -approximation algorithm for Graph TSP implies an (alpha + epsilon)-approximation algorithm for its path version. By applying our reduction to the 1.4-approximation algorithm for Graph TSP by Seb o and Vygen, we obtain a polynomial-time (1.4 + epsilon)-approximation algorithm for Graph Path TSP, improving on a recent 1.497-approximation algorithm of Traub and Vygen. We obtain our results through a variety of new techniques, including a novel way to set up a recursive dynamic program to guess significant parts of an optimal solution. At the core of our dynamic program we deal with instances of a new generalization of (Path) TSP which combines parity constraints with certain connectivity requirements. This problem, which we call phi -TSP, has a constant-factor approximation algorithm and can be reduced to TSP in certain cases when the dynamic program would not make sufficient progress.

关键词： traveling salesman problem Path TSP approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Distributed Independent Sets in Interval and Segment Intersection Graphs 47th

Distributed Independent Sets in Interval and Segment Interse...

引用

47th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM)

作者： Gorain, Barun Mondal, Kaushik Pandit, Supantha Indian Inst Technol Bhilai Raipur Chattisgarh India Indian Inst Technol Ropar Rupnagar Punjab India Dhirubhai Ambani Inst Informat & Commun Technol Gandhinagar Gujrat India

ISBN: (纸本)9783030677305;9783030677312

The Maximal Independent Set problem is a well-studied problem in the distributed community. We study Maximum and Maximal Independent Set problems on two geometric intersection graphs;interval graphs and axis-parallel segment intersection graphs, and present deterministic distributed algorithms in the local communication model. We compute the maximum independent set on interval graphs in O(k) rounds and O(n) messages, where k is the size of the maximum independent set and n is the number of nodes in the graph. We provide a matching lower bound of O(k) on the number of rounds whereas O(n) is a trivial lower bound on message complexity. Thus our algorithm is both time and message optimal. We also study the maximal independent set problem in bi-interval graphs, a special case of the interval graphs where the intervals have two different lengths. We prove that a maximal independent set can be computed in bi-interval graphs in constant rounds that is 1 6 -approximation. For axis-parallel segment intersection graphs, we design an algorithm that finds a maximal independent set in O(D) rounds, where D is the diameter of the graph. We further show that this independent set is a 1 2 -approximation. The results in this paper extend the results of Molla et al. [J. Parallel Distrib. Comput. 2019].

关键词： Maximal Independent Set Interval graph Segment intersection graph Distributed algorithm approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Improved Fast algorithms for Optimal Min-Max Line Barrier Coverage with Mobile Sensors on the Plane 21

Improved Fast Algorithms for Optimal Min-Max Line Barrier Co...

引用

24th International Conference on Modeling Analysis and Simulation of Wireless and Mobile Systems

作者： Yao, Pei Guo, Longkun Li, Peng Lin, Jiawei Fuzhou Univ Fuzhou Peoples R China Google Incorp Kirkland WA USA

ISBN: (纸本)9781450390774

Emerging applications raise the min-max line barrier coverage (LBC) problem that aims to minimize the maximum movement of the sensors for the sake of balancing energy consumption. In this paper, we devise an exact algorithm to optimally solve LBC within a runtime of O(n(2)), comparing favorably to the previous state-of-art runtime O(n(2) log n), where n is the number of sensors. To achieve the improvement, we accelerate the computation of optimum solutions by using a novel approximation algorithm. Numerical experiments demonstrated that our algorithms outperform all the other baselines, including the previous state-of-art algorithm.

关键词： Fast algorithm barrier coverage optimal solution mobile sensor approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Approximating Nash Social Welfare under Rado Valuations 2021

Approximating Nash Social Welfare under Rado Valuations

引用

53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC)

作者： Garg, Jugal Husic, Edin Vegh, Laszlo A. Univ Illinois Urbana IL 61801 USA London Sch Econ & Polit Sci London England

ISBN: (纸本)9781450380539

We consider the problem of approximating maximum Nash social welfare (NSW) while allocating a set of indivisible items to n agents. The NSW is a popular objective that provides a balanced tradeoff between the often conflicting requirements of fairness and efficiency, defined as the weighted geometric mean of the agents' valuations. For the symmetric additive case of the problem, where agents have the same weight with additive valuations, the first constant-factor approximation algorithm was obtained in 2015. Subsequent work has obtained constant-factor approximation algorithms for the symmetric case under mild generalizations of additive, and O(n)-approximation algorithms for subadditive valuations and for the asymmetric case. In this paper, we make significant progress towards both symmetric and asymmetric NSW problems. We present the first constant-factor approximation algorithm for the symmetric case under Rado valuations. Rado valuations form a general class of valuation functions that arise from maximum cost independent matching problems, including as special cases assignment (OXS) valuations and weighted matroid rank functions. Furthermore, our approach also gives the first constant-factor approximation algorithm for the asymmetric case under Rado valuations, provided that the maximum ratio between the weights is bounded by a constant.

关键词： Nash social welfare approximation algorithm Rado valuations

来源：评论

学校读者我要写书评

暂无评论

Approximate the Lower-Bounded Connected Facility Location Problem 27th

Approximate the Lower-Bounded Connected Facility Location Pr...

引用

27th International Computing and Combinatorics Conference (COCOON)

作者： Han, Lu Wu, Chenchen Xu, Yicheng Beijing Univ Posts & Telecommun Sch Sci Beijing 100876 Peoples R China Tianjin Univ Technol Coll Sci Tianjin 300384 Peoples R China Chinese Acad Sci Shenzhen Inst Adv Technol Shenzhen 518055 Peoples R China Guangxi Key Lab Cryptog & Informat Secur Guilin 541004 Peoples R China

ISBN: (纸本)9783030895433;9783030895426

This paper studies the lower-bounded connected facility location (LB ConFL) problem, which extends the well-known connected facility location (ConFL) and lower-bounded facility location (LBFL) problems. In the LB ConFL, we are given a graph G = (V, E), where V and E are all the vertices and edges, respectively. A facility set F subset of V, a client set D subset of V, a parameter M >= 1, and an integer lower bound L are also given. Each facility has an opening cost f(i), and each edge e is an element of E has a connection cost c(e). Denote by c(uv) the shortest path with respect to the connection costs from vertex u to v. Opening a facility i incurs its opening cost. Assigning a client j to some facility i incurs a connection cost c(ij). Connecting a facility subset S subset of F by a Steiner tree T incurs a cost of M Sigma(e is an element of T) c(e) called Steiner cost. The goal is to open some facilities S subset of F, assign each client j to some opened facility in S and connect all the opened facilities S by a Steiner tree, such that the number of clients connected to any opened facility is at least L, and the total incurred cost (i.e., the total opening, connection, and Steiner cost) is minimized. As our main contribution, we propose two approximation algorithms for the LB ConFL with ratios of 696 and 169. The first algorithm is based on an intuitive idea that finding a suitable Steiner tree before considering the lower bound constraints may give a good solution. The second algorithm effectively avoids the shortcoming of the first one and successfully improves the approximation ratio. Moreover, we consider the general LB ConFL (GLB ConFL) problem, in which each facility i has a non-uniform lower bound L-i. We give an approximation algorithm with a ratio related to the parameter M for the GLB ConFL.

关键词： Connected facility location Lower bounds approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Groups Influence with Minimum Cost in Social Networks 10th

Groups Influence with Minimum Cost in Social Networks

引用

10th International Conference on Computational Data and Social Networks (CSoNet)

作者： Pham, Phuong N. H. Pham, Canh V. Duong, Hieu V. Trung Thanh Nguyen Thai, My T. Ho Chi Minh city Univ Food Ind Fac Informat Technol Ho Chi Minh Vietnam Phenikaa Univ ORlab Fac Comp Sci Hanoi 12116 Vietnam Univ Florida Dept Comp & Informat Sci & Engn Gainesville FL USA

ISBN: (纸本)9783030914349;9783030914332

This paper studies a Group Influence with Minimum cost which aims to find a seed set with smallest cost that can influence all target groups, where each user is associated with a cost and a group is influenced if the total score of the influenced users belonging to the group is at least a certain threshold. As the group-influence function is neither submodular nor supermodular, theoretical bounds on the quality of solutions returned by the well-known greedy approach may not be guaranteed. To address this challenge, we propose a bi-criteria polynomial-time approximation algorithm with high certainty. At the heart of the algorithm is a novel group reachable reverse sample concept, which helps speed up the estimation of the group influence function. Finally, extensive experiments conducted on real social networks show that our proposed algorithm outperform the state-of-the-art algorithms in terms of the objective value and the running time.

关键词： Viral marketing Group influence approximation algorithm Online social network

来源：评论

学校读者我要写书评

暂无评论

Latency-aware VNF Protection for Network Function Virtualization in Elastic Optical Networks

Latency-aware VNF Protection for Network Function Virtualiza...

引用

IEEE Global Communications Conference (GLOBECOM)

作者： Peng, Chengzong Zheng, Danyang Cao, Xiaojun Georgia State Univ Dept Comp Sci Atlanta GA 30303 USA Soochow Univ Sch Elect & Informat Engn Suzhou Peoples R China

ISBN: (纸本)9781728181042

In network function virtualization (NFV), the customer may request a set of virtual network functions (VNFs) that the customer traffic will go through. To accommodate such requests, the service providers have to embed the requested VNFs onto the substrate network (SN) to form an actual traffic forwarding path called service function path (SFP). In the elastic optical network (EON), how to protect the running network services against VNF failures becomes an attractive research focus. Most existing work concentrates on the protection or restoration of the physical node or fiber link failures in the SN. Few research attention has been paid to the failure of the virtual machines running a VNF. In this paper, we study how to protect VNFs when a VNF failure occurs in an EON. We define a new VNF failure protection cover (VFPC) problem and mathematically formulate VFPC. We propose a protection cover list based VNF protection (PCL-VP) algorithm against any single VNF failure while satisfying the latency requirement. Extensive simulations and analysis show the effectiveness of the proposed algorithm.

关键词： Network function virtualization Virtual network function VNF failure approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Accepted Influence Maximization under Linear Threshold Model on Large-Scale Social Networks 20

Accepted Influence Maximization under Linear Threshold Model...

引用

20th IEEE International Conference on Trust, Security and Privacy in Computing and Communications (IEEE TrustCom)

作者： Yang, Xiaojuan Shang, Jiaxing Zheng, Linjiang Liu, Dajiang Fu, Shu Qiang, Baohua Chongqing Univ Coll Comp Sci Key Lab Dependable Serv Comp Cyber Phys Soc Minist Educ Chongqing Peoples R China Chongqing Univ Sch Microelect & Commun Engn Chongqing Peoples R China Guilin Univ Elect Technol Guangxi Key Lab Trusted Software Guilin Peoples R China

ISBN: (纸本)9781665416580

The influence maximization (IM) problem, which aims to find k most influential individuals from a social network to maximize the influence spread, has been extensively studied. Existing works all rely on the assumption that influenced individuals will definitely try to propagate the information to their neighbors through social trust. However, in real-world this assumption can be over-simplistic since trust-levels among different individuals usually exhibit high diversity. As a result, an influenced individual may choose not to further propagate the information to his neighbors. Motivated by the observation, in this paper we propose a new accepted influence maximization (AIM) problem where the influenced individuals are further divided into two subgroups, i.e., accepted and active, where only active individuals will continue to propagate the information. We prove this problem is NP-hard and the objective function is submodular, based on which a greedy algorithm is proposed with (1 - 1/e - epsilon) approximation guarantee. Considering the low computational efficiency of the greedy algorithm, we further propose a scalable path-based algorithm ALDAG. We conduct experiments on real datasets and the results demonstrate the effectiveness and efficiency of our method.

关键词： Influence Maximization Diffusion Model Trust in Social Networks Data Mining approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Efficient and Effective algorithms for Revenue Maximization in Social Advertising 21

Efficient and Effective Algorithms for Revenue Maximization ...

引用

ACM SIGMOD International Conference on Management of Data (SIGMOD)

作者： Han, Kai Wu, Benwei Tang, Jing Cui, Shuang Aslay, Cigdem Lakshmanan, Laks V. S. Univ Sci & Technol China SuZhou Res Inst Sch Comp Sci & Technol Hefei Peoples R China Univ Sci & Technol China Sch Comp Sci & Technol Hefei Peoples R China Natl Univ Singapore Sch Comp Singapore Singapore Aarhus Univ Dept Comp Sci Aarhus Denmark Univ British Columbia Dept Comp Sci Vancouver BC Canada

ISBN: (纸本)9781450383431

We consider the revenue maximization problem in social advertising, where a social network platform owner needs to select seed users for a group of advertisers, each with a payment budget, such that the total expected revenue that the owner gains from the advertisers by propagating their ads in the network is maximized. Previous studies on this problem show that it is intractable and present approximation algorithms. We revisit this problem from a fresh perspective and develop novel efficient approximation algorithms, both under the setting where an exact influence oracle is assumed and under one where this assumption is relaxed. Our approximation ratios significantly improve upon the previous ones. Furthermore, we empirically show, using extensive experiments on four datasets, that our algorithms considerably outperform the existing methods on both the solution quality and computation efficiency.

关键词： social advertising approximation algorithm influence

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：