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

Tree decomposition based anomalous connected subgraph scanning for detecting and forecasting events in attributed social media networks

引用

NEUROCOMPUTING 2020年 407卷 83-93页

作者： Shao, Minglai Sun, Peiyuan Li, Jianxin Yan, Qiben Feng, Zhirui Beihang Univ Bejing Adv Innovat Ctr Big Data & Brain Comp Beijing Peoples R China Beihang Univ State Key Lab Software Dev Environm Beijing Peoples R China Michigan State Univ Comp Sci & Engn E Lansing MI 48824 USA

Event detection and forecasting in social media networks, such as disease outbreak and air pollution event detection, have been formulated as an anomalous connected subgraph detection problem. How-ever, the huge search space and the sparsity of anomaly events make it difficult to solve this problem effectively and efficiently. This paper presents a general framework, namely anomalous connected sub -graph scanning (GraphScan) which optimizes a large class of sophisticated nonlinear nonparametric scan statistic functions, to solve this problem in attributed social media networks. We first transform the so-phisticated nonlinear nonparametric scan statistics functions into the Price-Collecting Steiner Tree (PCST) problem with provable guarantees for evaluating the significance of connected subgraphs to indicate the ongoing or forthcoming events. Then, we use tree decomposition technique to divide the whole graph into a set of smaller subgraph bags, and arrange them into a tree structure, through which we can re-duce the search space dramatically. Finally, we propose an efficient approximation algorithm to solve the problem of anomalous subgraph detection using the tree of bags. With two real-world datasets from different domains, we conduct extensive experimental evaluations to demonstrate the effectiveness and efficiency of the proposed approach. (C) 2020 Elsevier B.V. All rights reserved.

关键词： Anomalous subgraph detection approximation algorithm Social media networks Nonparametric statistics Tree decomposition Event detection and forecasting

来源：评论

学校读者我要写书评

暂无评论

Stochastic greedy algorithms for maximizing constrained submodular plus supermodular functions

引用

CONCURRENCY AND COMPUTATION-PRACTICE & EXPERIENCE 2023年第17期35卷

作者： Ji, Sai Xu, Dachuan Li, Min Wang, Yishui Zhang, Dongmei Beijing Univ Technol Beijing Inst Sci & Engn Comp Beijing Peoples R China Chinese Acad Sci Acad Math & Syst Sci Beijing Peoples R China Shandong Normal Univ Sch Math & Stat Jinan Peoples R China Univ Sci & Technol Beijing Sch Math & Phys Beijing Peoples R China Shandong Jianzhu Univ Sch Comp Sci & Technol Jinan 250101 Peoples R China

The problem of maximizing the sum of a constrained submodular and a supermodular function has many applications such as social networks, machine learning, and artificial intelligence. In this article, we study the monotone submodular + supermodular maximization problem under a cardinality constraint and a p-system constraint, respectively. For each problem, we provide a stochastic algorithm and prove the approximation ratio of each algorithm theoretically. Since the algorithm of the latter problem can also solve the former problem, we do some numerical experiments of the two algorithms to compare the time as well as the quality of the two algorithms in solving the former problem.

关键词： approximation algorithm constrained stochastic greedy submodular plus supermodular maximization

来源：评论

学校读者我要写书评

暂无评论

Asymptotic Quasi-Polynomial Time approximation Scheme for Resource Minimization for Fire Containment 37

Asymptotic Quasi-Polynomial Time Approximation Scheme for Re...

引用

37th International Symposium on Theoretical Aspects of Computer Science (STACS)

作者： Rahgoshay, Mirmahdi Salavatipour, Mohammad R. Univ Alberta Dept Comp Sci Edmonton AB T6G 2E8 Canada

ISBN: (纸本)9783959771405

Resource Minimization Fire Containment (RMFC) is a natural model for optimal inhibition of harmful spreading phenomena on a graph. In the RMFC problem on trees, we are given an undirected tree G, and a vertex r where the fire starts at, called root. At each time step, the firefighters can protect up to B vertices of the graph while the fire spreads from burning vertices to all their neighbors that have not been protected so far. The task is to find the smallest B that allows for saving all the leaves of the tree. The problem is hard to approximate up to any factor better than 2 even on trees unless P = NP [11]. Chalermsook and Chuzhoy [6] presented a Linear Programming based O(log* n) approximation for RMFC on trees that matches the integrality gap of the natural Linear Programming relaxation. This was recently improved by Adjiashvili, Baggio, and Zenklusen [1] to a 12-approximation through a combination of LP rounding along with several new techniques. In this paper we present an asymptotic QPTAS for RMFC on trees. More specifically, let is an element of > 0, and I be an instance of RMFC where the optimum number of firefighters to save all the leaves is OPT (I). We present an algorithm which uses at most [(1 - is an element of)OPT(I)] many firefighters at each time step and runs in time n(O()(log log n/)(is an element of)). This suggests that the existence of an asymptotic PTAS is plausible especially since the exponent is O(log log n), not O(log n). Our result combines a more powerful height reduction lemma than the one in [1] with LP rounding and dynamic programming to find the solution. We also apply our height reduction lemma to the algorithm provided in [1] plus a more careful analysis to improve their 12-approximation and provide a polynomial time (5 + is an element of)-approximation.

关键词： Firefighter Problem Resource Management Fire Containment approximation algorithm Asymptotic approximation Scheme

来源：评论

学校读者我要写书评

暂无评论

A Constant Factor approximation for Lower-Bounded k-Median 1

引用

16th International Conference on Theory and Applications of Models of Computation (TAMC)

作者： Guo, Yutian Huang, Junyu Zhang, Zhen Cent South Univ Sch Comp Sci & Engn Changsha 410083 Peoples R China

ISBN: (数字)9783030592677

ISBN: (纸本)9783030592660;9783030592677

The lower-bounded k-median problem considers a set C of clients, a set F of facilities, and a parameter B, the goal is to open k facilities and connect each client to an opened facility, such that each opened facility is connected with at least B clients and the total connection cost is minimized. The problem is known to admit an O(1)-approximation algorithm, while the constant is implicit and seems to be a very large constant. In this paper, we give an approach that converts the lowerbounded k-median problem to the capacitated facility location problem, which yields a (516 + is an element of)-approximation for the lower-bounded k-median problem.

关键词： approximation algorithm k-median

来源：评论

学校读者我要写书评

暂无评论

Latency-Based Transmission Point Selection algorithms in Wireless Networks

引用

IEEE TRANSACTIONS ON VEHICULAR TECHNOLOGY 2020年第11期69卷 14072-14077页

作者： Kim, Eunkyung Lee, Yuro Lee, Heesoo Elect & Telecommun Res Inst ETRI Daejeon 34129 South Korea

In this paper, we propose transmission point selection algorithms to provide lower service time between an application server to end users by selecting the transmission point used by a newly identified metric, i.e., service latency. In particular, the proposed ordered service latency-based transmission point selection algorithm is beneficial in a sense that it does not increase average service time but decrease the maximum service time although it brings additional computational complexity slightly. We also provide the performance bounds with proven approximation ratios and verify that the proposed algorithm achieves lower maximum service time without degrading the average service time as well as waiting time through simulations in practical environments.

关键词： approximation algorithms Wireless networks Computational complexity Measurement Servers Computational modeling Ultra reliable low latency communication Low latency communication transmission point selection approximation algorithm URLLC

来源：评论

学校读者我要写书评

暂无评论

Towards Better approximation of Graph Crossing Number 61

Towards Better Approximation of Graph Crossing Number

引用

61st IEEE Annual Symposium on Foundations of Computer Science (FOCS)

作者： Chuzhoy, Julia Mahabadi, Sepideh Tan, Zihan Toyota Technol Inst Chicago Chicago IL 60637 USA Univ Chicago Chicago IL 60637 USA

ISBN: (纸本)9781728196213

Graph Crossing Number is a fundamental and extensively studied problem with wide ranging applications. In this problem, the goal is to draw an input graph G in the plane so as to minimize the number of crossings between the images of its edges. The problem is notoriously difficult, and despite extensive work, non-trivial approximation algorithms are only known for bounded-degree graphs. Even for this special case, the best current algorithm achieves a (O) over tilde(root n)-approximation, while the best current negative results do not rule out constant-factor approximation. All current approximation algorithms for the problem build on the same paradigm, which is also used in practice: compute a set E' of edges (called a planarizing set) such that G \ E' is planar;compute a planar drawing of G\E';then add the drawings of the edges of E' to the resulting drawing. Unfortunately, there are examples of graphs G, in which any implementation of this method must incur Omega(OPT2) crossings, where OPT is the value of the optimal solution. This barrier seems to doom the only currently known approach to designing approximation algorithms for the problem, and to prevent it from yielding a better than O(root n)-approximation. In this paper we propose a new paradigm that allows us to overcome this barrier. We show an algorithm, that, given a bounded-degree graph G and a planarizing set E' of its edges, computes another planarizing edge set E '' with E' subset of E '', such that vertical bar E ''vertical bar is relatively small, and there exists a near-optimal drawing of G in which no edges of G\E '' participate in crossings. This allows us to reduce the Crossing Number problem to Crossing Number with Rotation System - a variant of the Crossing Number problem, in which the ordering of the edges incident to every vertex is fixed as part of input. In our reduction, we obtain an instance G' of this problem, where vertical bar E(G')vertical bar is roughly bounded by the crossing numbe

关键词： approximation algorithm crossing number

来源：评论

学校读者我要写书评

暂无评论

M^pUFLP: Universal facility location problem in the p-th power of metric space

引用

THEORETICAL COMPUTER SCIENCE 2020年 838卷 58-67页

作者： Xu, Yicheng Xu, Dachuan Zhang, Yong Zou, Juan Chinese Acad Sci Shenzhen Inst Adv Technol Shenzhen 518055 Peoples R China Beijing Univ Technol Dept Operat Res & Informat Engn Beijing 100124 Peoples R China Qufu Normal Univ Sch Math Sci Qufu 273165 Shandong Peoples R China

We propose and study the (MUFLP)-U-p (universal facility location problem in the p-th power of metric space) in this paper, where the universal facility location problem (UFLP) extends several classical facility location problems like the uncapacitated facility location, hard-capacitated facility location, soft-capacitated facility location, incremental-cost facility location, concave-cost facility location, etc. In UFLP, a set of facilities, a set of clients, as well as the distances between them are given. Each facility has its specific cost function w.r.t. the amount of clients assigned to that facility. The goal is to assign the clients to facilities such that the sum of facility cost and service cost is minimized. In traditional facility location problems, the unit service cost is proportional to the distance between the client and its assigned facility and thus metric. However, in our work, this assumption is removed and a generalized version of universal facility location problem is proposed, which is the so-called (MUFLP)-U-n. When p = 2, it is also known as l(2)(2) measure considered by Jain and Vazirani [J. ACM'01 ] and Fernandes et al. [Math. Program.'15]. Particularly in this case, we extend their work to include the aforementioned variants of facility location and a local search based (11.18 + epsilon)-approximation algorithm is proposed. Furthermore, the reanalysis of the proposed algorithm gives a p-related performance guarantee for general p. (C) 2020 Elsevier B.V. All rights reserved.

关键词： Facility location Universal facility location approximation algorithm Squared metric p-th power metric

来源：评论

学校读者我要写书评

暂无评论

A Primal-Dual-Based Power Control Approach for Capacitated Edge Servers

引用

SENSORS 2022年第19期22卷 7582-7582页

作者： Zhang, Qinghui Li, Weidong Su, Qian Zhang, Xuejie Yunnan Univ Sch Informat Sci & Engn Kunming 650091 Yunnan Peoples R China Yunnan Univ Sch Math & Stat Kunming 650091 Yunnan Peoples R China

The intensity of radio waves decays rapidly with increasing propagation distance, and an edge server's antenna needs more power to form a larger signal coverage area. Therefore, the power of the edge server should be controlled to reduce energy consumption. In addition, edge servers with capacitated resources provide services for only a limited number of users to ensure the quality of service (QoS). We set the signal transmission power for the antenna of each edge server and formed a signal disk, ensuring that all users were covered by the edge server signal and minimizing the total power of the system. This scenario is a typical geometric set covering problem, and even simple cases without capacity limits are NP-hard problems. In this paper, we propose a primal-dual-based algorithm and obtain an m-approximation result. We compare our algorithm with two other algorithms through simulation experiments. The results show that our algorithm obtains a result close to the optimal value in polynomial time.

关键词： power control primal-dual approximation algorithm edge computing power cover

来源：评论

学校读者我要写书评

暂无评论

Approximating the minimal lookahead needed to win infinite games

引用

INFORMATION PROCESSING LETTERS 2022年 177卷

作者： Zimmermann, Martin Univ Liverpool Liverpool Merseyside England Aalborg Univ Aalborg Denmark

关键词： Formal methods Theory of computation Delay games approximation algorithm Infinite games

来源：评论

学校读者我要写书评

暂无评论

Efficient algorithms for flexible job shop scheduling with parallel machines

引用

NAVAL RESEARCH LOGISTICS 2020年第4期67卷 272-288页

作者： Kubiak, Wieslaw Feng, Yanling Li, Guo Sethi, Suresh P. Sriskandarajah, Chelliah Mem Univ Newfoundland Fac Business Adm St John NF Canada Beijing Univ Posts & Telecommun Sch Econ & Management Beijing Peoples R China Beijing Inst Technol Sch Management & Econ Beijing 100081 Peoples R China Beijing Inst Technol Ctr Energy & Environm Policy Res Beijing Peoples R China Univ Texas Dallas Naveen Jindal Sch Management Dallas TX USA Texas A&M Univ Mays Business Sch College Stn TX USA

Job shop scheduling with a bank of machines in parallel is important from both theoretical and practical points of view. Herein we focus on the scheduling problem of minimizing the makespan in a flexible two-center job shop. The first center consists of one machine and the second has k parallel machines. An easy-to-perform approximate algorithm for minimizing the makespan with one-unit-time operations in the first center and k-unit-time operations in the second center is proposed. The algorithm has the absolute worst-case error bound of k - 1, and thus for k = 1 it is optimal. Importantly, it runs in linear time and its error bound is independent of the number of jobs to be processed. Moreover, the algorithm can be modified to give an optimal schedule for k = 2.

关键词： absolute worst-case error bound approximation algorithm flexible job shop scheduling makespan

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：