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

The seeding algorithms for spherical k-means clustering

JOURNAL OF GLOBAL OPTIMIZATION 2020年第4期76卷 695-708页

作者： Li, Min Xu, Dachuan Zhang, Dongmei Zou, Juan Shandong Normal Univ Sch Math & Stat Jinan 250014 Peoples R China Beijing Univ Technol Beijing Inst Sci & Engn Comp Beijing 100124 Peoples R China Shandong Jianzhu Univ Sch Comp Sci & Technol Jinan 250101 Peoples R China Qufu Normal Univ Sch Math Sci Qufu 273165 Shandong Peoples R China

In order to cluster the textual data with high dimension in modern data analysis, the spherical k-means clustering is presented. It aims to partition the given points with unit length into k sets so as to minimize the within-cluster sum of cosine dissimilarity. In this paper, we mainly study seeding algorithms for spherical k-means clustering, for its special case (with separable sets), as well as for its generalized problem (alpha spherical k-means clustering). About the spherical k-means clustering with separable sets, an approximate algorithm with a constant factor is presented. Moreover, it can be generalized to the alpha-spherical separable k-means clustering. By slickly constructing a useful function, we also show that the famous seeding algorithms such as k-means++ and k-means|| for k-means problem can be applied directly to solve the alpha-spherical k-means clustering. Except for theoretical analysis, the numerical experiment is also included.

关键词： approximation algorithm Spherical k-means clustering k-means problem Separable set Seeding algorithm

来源：评论

学校读者我要写书评

暂无评论

A k-Hop Collaborate Game Model: Adaptive Strategy to Maximize Total Revenue

引用

IEEE TRANSACTIONS ON COMPUTATIONAL SOCIAL SYSTEMS 2020年第4期7卷 1058-1068页

作者： Guo, Jianxiong Wu, Weili Univ Texas Dallas Erik Jonsson Sch Engn & Comp Sci Dept Comp Sci Richardson TX 75080 USA

In online social networks (OSNs), interpersonal communication and information sharing are happening all the time, and it is real time. If a user initiates an activity (game) in OSNs, she will cause a certain impact on her friendship circle naturally, namely, some users in this initiator's friendship circle will be attracted to participate in this activity. Based on such a fact, we design a k-hop collaborated game model, which means that an activity initiated by a user can only influence those users whose distance is within k-hop from this initiator. We introduce the problem of revenue maximization under k-hop collaborate game (RMKCG), which identifies a limited number of initiators in order to obtain revenue as much as possible. The collaborated game model describes in detail how to quantify revenue and the logic behind it. We do not know how many followers would be attracted by activity in advance, and thus, we need to adopt an adaptive strategy, where the decision who is the next potential initiator depends on the results of past decisions. The adaptive RMKCG problem can be considered as a new stochastic optimization problem, and we prove it is NP-hard, adaptive monotone, but not adaptive submodular. But in some special cases, it is adaptive submodular, and thus, we design an adaptive greedy algorithm. Due to the complexity of our model, it is hard to compute the marginal gain for each candidate user, and then we propose an efficient computational method to estimate it. The effectiveness and correctness of our algorithms are validated by heavy simulation on real-world graphs finally.

关键词： Adaptive strategy approximation algorithm collaborated game model online social networks (OSNs) stochastic optimization submodularity

来源：评论

学校读者我要写书评

暂无评论

Effector Detection Problem in Social Networks

引用

IEEE TRANSACTIONS ON COMPUTATIONAL SOCIAL SYSTEMS 2020年第5期7卷 1200-1209页

作者： Zhang, Yapu Yang, Wenguo Wu, Weili Li, Yi Univ Chinese Acad Sci Sch Math Sci Beijing 100049 Peoples R China Univ Texas Dallas Dept Comp Sci Richardson TX 75080 USA Univ Texas Tyler Dept Comp Sci Tyler TX 75799 USA

Nowadays, different innovations spread rapidly in online social networks. An activation state can indicate whether each user adopts the target information. The effector detection problem aims to find a way to generate an activation state as close to an observed one as possible. In this article, based on the influence spread, the unconstrained and constrained effector detection problems are proposed. To tackle them, we design two approximation algorithms since the problem is NP-hard, and the objective function is nonsubmodular. For the unconstrained case, our objective function can be best provided with the difference of two submodular functions. Thus, we address this problem through the modular-modular algorithm. For the constrained case, we devise the solutions for the original function, submodular upper bound, and lower bound according to an idea of reverse influence sampling. Then, there is a data-dependent approximate solution using the sandwich approximation algorithm. Finally, we show the correctness and superiority of our methods through massive experiments in three real-world networks.

关键词： Integrated circuit modeling approximation algorithms Social network services Linear programming Biological system modeling Technological innovation approximation algorithm effector detection reverse influence sampling (RIS) social networks

来源：评论

学校读者我要写书评

暂无评论

Open-shop scheduling for unit jobs under precedence constraints

引用

THEORETICAL COMPUTER SCIENCE 2020年 803卷 144-151页

作者： Chen, Yong Goebel, Randy Lin, Guohui Su, Bing Zhang, An Hangzhou Dianzi Univ Dept Math Hangzhou Peoples R China Univ Alberta Dept Comp Sci Edmonton AB T6G 2E8 Canada Xian Technol Univ Sch Econ & Management Xian Peoples R China

We study open-shop scheduling for unit jobs under precedence constraints, where if one job precedes another job then it has to be finished before the other job can start to be processed. For the three-machine open-shop to minimize the makespan, we first present a simple 5/3-approximation algorithm based on a partition of the job set into agreeable layers using the natural layered representation of the precedence graph, which is directed acyclic. We then show a greedy algorithm to reduce the number of singleton job layers, resulting in an improved partition, which leads to a 4/3-approximation algorithm. Both approximation algorithms apply to the general m-machine open-shops too. (C) 2019 Elsevier B.V. All rights reserved.

关键词： Open-shop scheduling Precedence constraint Directed acyclic graph approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Learning the truth vector in high dimensions

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2020年第0期109卷 78-94页

作者： Ding, Hu Xu, Jinhui Univ Sci & Technol China Sch Comp Sci & Technol Hefei 230027 Peoples R China SUNY Buffalo Dept Comp Sci & Engn Buffalo NY 14260 USA

Truth Discovery is an important learning problem arising in data analytics related fields. It concerns about finding the most trustworthy information from a dataset acquired from a number of unreliable sources. The problem has been extensively studied and a number of techniques have already been proposed. However, all of them are of heuristic nature and do not have any quality guarantee. In this paper, we formulate the problem as a high dimensional geometric optimization problem, called Entropy based Geometric Variance. Relying on a number of novel geometric techniques, we further discover new insights to this problem. We show, for the first time, that the truth discovery problem can be solved with guaranteed quality of solution. Particularly, it is possible to achieve a (1 + epsilon) -approximation within nearly linear time under some reasonable assumptions. We expect that our algorithm will be useful for other data related applications. (C) 2019 Elsevier Inc. All rights reserved.

关键词： Truth discovery Entropy High dimension approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

COMPLEXITY AND APPROXIMABILITY OF OPTIMAL RESOURCE ALLOCATION AND NASH EQUILIBRIUM OVER

引用

SIAM JOURNAL ON OPTIMIZATION 2020年第1期30卷 885-914页

作者： Etesami, S. Rasoul Univ Illinois Dept Ind & Enterprise Syst Engn Urbana IL 61801 USA

Motivated by emerging resource allocation and data placement problems such as web caches and peer-to-peer systems, we consider and study a class of resource allocation problems over a network of agents (nodes). In this model, which can be viewed as a homogeneous data placement problem, nodes can store only a limited number of resources while accessing the remaining ones through their closest neighbors. We consider this problem under both optimization and gametheoretic frameworks. In the case of optimal resource allocation, we will first show that when there are only k = 2 resources, the optimal allocation can be found efficiently in O(n(2) log n) steps, where n denotes the total number of nodes. However, for k >= 3 this problem becomes NP-hard with no polynomial-time approximation algorithm with a performance guarantee better than 1 + 1/102k(2) even under metric access costs. We then provide a 3-approximation algorithm for the optimal resource allocation which runs only in O(kn(2)). Subsequently, we look at this problem under a selfish setting formulated as a noncooperative game and provide a 3-approximation algorithm for obtaining its pure Nash equilibria under metric access costs. We then establish an equivalence between the set of pure Nash equilibria and flip-optimal solutions of the Max-k-Cut problem over a specific weighted complete graph. While this reduction suggests that finding a pure Nash equilibrium using best response dynamics might be PLS-hard, it allows us to use tools from complementary slackness and quadratic programming to devise systematic and more efficient algorithms towards obtaining Nash equilibrium points.

关键词： resource allocation data placement problem facility location network games potential games approximation algorithm quadratic programming computational complexity

来源：评论

学校读者我要写书评

暂无评论

An FPTAS for the volume of some V-polytopes - It is hard to compute the volume of the intersection of two cross-polytopes

引用

THEORETICAL COMPUTER SCIENCE 2020年 833卷 87-106页

作者： Ando, Ei Kijima, Shuji Senshu Univ Tama Ku 2-1-1 Higashi Mita Kawasaki Kanagawa 2148580 Japan Kyushu Univ Nishi Ku 744 Motooka Fukuoka 8190395 Japan JST PRESTO Nishi Ku 744 Motooka Fukuoka 8190395 Japan

Given an n-dimensional convex body by a membership oracle in general, it is known that any polynomial-time deterministic algorithm cannot approximate its volume within ratio (n/logn)(n). There is a substantial progress on randomized approximation such as Markov chain Monte Carlo for a high-dimensional volume, and for many #P-hard problems, while only a few #P-hard problems are known to yield deterministic approximation. Motivated by the problem of deterministically approximating the volume of a V-polytope, that is a polytope with a small number of vertices and (possibly) exponentially many facets, this paper investigates the problem of computing the volume of a "knapsack dual polytope," which is known to be #P-hard due to Khachiyan (1989) [16]. We reduce an approximate volume of a knapsack dual polytope to that of the intersection of two cross-polytopesin a short distance, and give FPTASs for those volume computations. Interestingly, computing the volume of the intersection of two cross-polytopes (i.e., L-1-balls) is #P-hard, unlike the cases of L-infinity-balls or L-2-balls. (c) 2020 Elsevier B.V. All rights reserved.

关键词： Volume computation #P-hard problems approximation algorithm Deterministic FPTAS

来源：评论

学校读者我要写书评

暂无评论

Energy-Saving Deployment algorithms of UAV Swarm for Sustainable Wireless Coverage

引用

IEEE TRANSACTIONS ON VEHICULAR TECHNOLOGY 2020年第9期69卷 10320-10335页

作者： Zhang, Xiao Duan, Lingjie South Cent Univ Nationalities Coll Comp Sci Wuhan 430074 Peoples R China Hubei Prov Engn Res Ctr Intelligent Management Mf Wuhan 430074 Peoples R China Singapore Univ Technol & Design Engn Syst & Design Pillar Singapore 487372 Singapore

Recent years have witnessed increasingly more uses of Unmanned Aerial Vehicle (UAV) swarms for rapidly providing wireless coverage to ground users. Each UAV is constrained in its energy storage and wireless coverage, and it consumesmost energy on flying to the top of the target area, thus leaving limited leftover energy for hovering at its deployed position and keeping wireless coverage. The literature largely overlooks the sustainability issues of deploying UAV swarm and the UAV-to-UAV cooperation, and we aim to maximize the minimum leftover energy storage among all the UAVs after their deployment. Our new energy-saving deployment problem captures that each UAV's wireless coverage is adjustable by its service altitude, and also takes the no-fly-zone (NFZ) constraint into account. We show that a UAV with larger initial energy storage in theUAVswarm should be deployed further away from the UAV station, and we propose an optimal energysaving deployment algorithm by jointly balancing heterogeneous UAVs' flying distances on the ground and final service altitudes in the sky. When n UAVs with different initial energy storages are dispatched from different initial locations, we prove this problem is NP-hard in general by reduction from partition problem. Despite of this, we propose to preserve the UAVs' location order and successfully design an approximation algorithm of complexity n log 1/epsilon to arbitrarily approach the optimum with error epsilon. Inspiring by this proposed (1 - epsilon)-approximation algorithm, we present a heuristic algorithm to solve the general case by balancing the efficiency and computation complexity well.

关键词： UAV smarm energy-efficient deployment wireless coverage no-fly-zone approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Approximating the 2-machine flow shop problem with exact delays taking two values

引用

JOURNAL OF GLOBAL OPTIMIZATION 2020年第3期76卷 491-497页

作者： Ageev, Alexander Sobolev Inst Math Koptyuga Ave 4 Novosibirsk Russia

In the 2-Machine Flow Shop problem with exact delays the operations of each job are separated by a given time lag (delay). Leung et al. (Int J Found Comput Sci 18:341-359, 2007) established that the problem is strongly NP-hard when the delays may have at most two different values. We present further results for this case: we prove that the existence of (1.25-epsilon)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(1.25-\varepsilon )$$\end{document}-approximation implies P=NP\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\hbox {P}=\hbox {NP}$$\end{document} and develop a 2-approximation algorithm.

关键词： Scheduling problem Flow shop Exact delays approximation algorithm Inapproximability lower bound approximation factor

来源：评论

学校读者我要写书评

暂无评论

CHASE: Charging and Scheduling Scheme for Stochastic Event Capture in Wireless Rechargeable Sensor Networks

引用

IEEE TRANSACTIONS ON MOBILE COMPUTING 2020年第1期19卷 44-59页

作者： Dai, Haipeng Ma, Qiufang Wu, Xiaobing Chen, Guihai Yau, David K. Y. Tang, Shaojie Li, Xiang-Yang Tian, Chen Nanjing Univ State Key Lab Novel Software Technol Nanjing 210023 Jiangsu Peoples R China Univ Canterbury Wireless Res Ctr Christchurch 8041 New Zealand Singapore Univ Technol & Design Informat Technol Syst & Design Pillar Singapore 487372 Singapore Univ Texas Dallas Naveen Jindal Sch Management 800 W Campbell Rd Richardson TX 75080 USA Univ Sci & Technol China Sch Comp Sci & Technol Hefei 230026 Anhui Peoples R China

In this paper, we consider the scenario in which a mobile charger (MC) periodically travels within a sensor network to recharge the sensors wirelessly. We design joint charging and scheduling schemes to maximize the Quality of Monitoring (QoM) for stochastic events, which arrive and depart according to known probability distributions of time. Information is considered captured if it is sensed by at least one sensor. We focus on two closely related research issues, i.e., how to choose the sensors for charging and decide the charging time for each of them, and how to schedule the sensors' activation schedules according to their received energy. We formulate our problem as the maximum QoM CHArging and SchEduling problem (CHASE). We first ignore the MCs travel time and study the resulting relaxed version of the problem, which we call CHASE-R. We show that both CHASE and CHASE-R are NP-hard. For CHASE-R, we prove that it can be formulated as a submodular function maximization problem, which allows two algorithms to achieve $1/6$1/6- and $1/(4 + \epsilon)$1/(4+)-approximation ratios. Then, for CHASE, we propose approximation algorithms to solve it by extending the CHASE-R results. We conduct simulations to validate our algorithm design.

关键词： Mobile charging scheduling wireless rechargeable sensor network stochastic event capture submodular optimization approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：