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

Incremental algorithms for the maximum internal spanning tree problem

Science China(Information Sciences) 2021年第5期64卷 77-84页

作者： Xianbin ZHU Wenjun LI Yongjie YANG Jianxin WANG School of Computer Science and Engineering Central South University Hunan Provincial Key Laboratory of Intelligent Processing of Big Data on Transportation Changsha University of Science and Technology Chair of Economic Theory Saarland University

The maximum internal spanning tree（MIST） problem is utilized to determine a spanning tree in a graph G,with the maximum number of possible internal *** incremental maximum internal spanning tree（IMIST） problem is the incremental version of MIST whose feasible solutions are edge-sequences e1,e2,…,en-1such that the first k edges form trees for all k ∈ [n-1].A solution's quality is measured using maxk∈[n-1]opt（G,k）/|In（Tk）| with lower being ***,opt（G,k） denotes the number of internal vertices in a tree with k edges in G,which has the largest possible number of internal vertices,and |In（Tk）| is the number of internal vertices in the tree comprising the solution's first k *** first obtained an IMIST algorithm with a competitive ratio of 2,followed by a 12/7-competitive algorithm based on an approximation algorithm for MIST.

关键词： maximum internal spanning tree incremental problem approximation algorithm competitive ratio

来源：评论

学校读者我要写书评

暂无评论

Improved approximation for two dimensional Strip Packing with polynomial bounded width

引用

THEORETICAL COMPUTER SCIENCE 2019年 789卷 34-49页

作者： Jansen, Klaus Rau, Malin Univ Kiel Inst Comp Sci D-24118 Kiel Germany

We study the well-known two-dimensional Strip Packing problem. Given a set of rectangular axis-parallel items and a strip of width W with infinite height, the objective is to find a packing of all items into the strip, which minimizes the packing height. Lately, it has been shown that the lower bound of 3/2 of the absolute approximation ratio can be beaten when we allow a pseudo-polynomial running-time of type (nW)(f(1/epsilon)). If W is polynomially bounded by the number of items, this is a polynomial running-time. The currently best pseudo-polynomial approximation algorithm by Nadiradze and Wiese achieves an approximation ratio of 1.4 + epsilon. We present a pseudo-polynomial algorithm with improved approximation ratio 4/3 + epsilon. Furthermore, the presented algorithm has a significantly smaller running-time as the 1.4 + epsilon approximation algorithm. (C) 2019 Elsevier B.V. All rights reserved.

关键词： Strip Packing Pseudo polynomial Structural Lemma approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Improved approximation algorithms for Capacitated Fault-Tolerant k-Center 12th

引用

12th Latin American Symposium on Theoretical Informatics (LATIN)

作者： Fernandes, Cristina G. de Paula, Samuel P. Pedrosa, Lehilton L. C. Univ Sao Paulo Dept Comp Sci Sao Paulo Brazil Univ Estadual Campinas Inst Comp Campinas SP Brazil

ISBN: (纸本)9783662495285

In the -center problem, given a metric space V and a positive integer k, one wants to select k elements (centers) of V and an assignment from V to centers, minimizing the maximum distance between an element of V and its assigned center. One of the most general variants is the capacitated -fault-tolerant k-center, where centers have a limit on the number of assigned elements, and, if any centers fail, there is a reassignment from V to non-faulty centers. In this paper, we present a new approach to tackle fault tolerance, by selecting and pre-opening a set of backup centers, then solving the obtained residual instance. For the -capacitated case, we give approximations with factor 6 for the basic problem, and 7 for the so called conservative variant, when only clients whose centers failed may be reassigned. Our algorithms improve on the best previously known factors of 9 and 17, respectively. Moreover, we consider the case with general capacities. Assuming is constant, our method leads to the first approximations for this case. We also derive approximations for the capacitated fault-tolerant k-supplier problem.

关键词： Capacitated k-center Fault tolerance approximation algorithm Non-uniform capacities Linear Programming LP rounding

来源：评论

学校读者我要写书评

暂无评论

Collaborative Social Internet of Things in Mobile Edge Networks

引用

IEEE INTERNET OF THINGS JOURNAL 2020年第12期7卷 11473-11491页

作者： Wang, Chih-Hang Kuo, Jian-Jhih Yang, De-Nian Chen, Wen-Tsuen Acad Sinica Inst Informat Sci Taipei 11529 Taiwan Natl Chung Cheng Univ Dept Comp Sci & Informat Engn Chiayi 62102 Taiwan Acad Sinica Res Ctr Informat Technol Innovat Taipei 11529 Taiwan Natl Tsing Hua Univ Dept Comp Sci Hsinchu 30013 Taiwan

Artificial intelligence (AI) on chips has recently driven the expansion of the Social Internet of Things (SIoT), where a group of SIoT devices with social relations can collaboratively identify and handle local events without the help of remote servers. On the other hand, mobile-edge computing (MEC) is a favorable way to locally process SIoT data for reducing data transmission and computation among SIoT devices and backhaul networks. Nevertheless, the load sharing among SIoT devices, MEC, and remote servers brings about new challenges for the communication and computation tradeoff, cross-layer design in SIoT, and forwarding and aggregation tradeoff. To tackle these issues, we formulate a new optimization problem, namely, SIoT collaborative group and device selection problem (SCGDSP), and prove the NP-hardness. We first explore the intrinsic properties of a fundamental SCGDSP case by finding the optimal collaborative group for each user request. Then, we design an approximation algorithm for the general SCGDSP that first evaluates candidate collaborative groups under different social relations, and then selects the collaborative groups and SIoT devices properly. For scalability, the proposed algorithm also supports dynamic user requests and can be distributionally deployed in massive networks enabling collaborative MEC. Moreover, it also sustains local SIoT services, where the computation only involves SIoT devices and MEC servers. Simulation results demonstrate that effective SIoT and collaborative group selection (ESCGS) can reduce by more than 50% of the total communication and computation costs compared with baseline schemes in the real networks from topology zoo. Moreover, the distributed ESCGS reduces by 87% of the running time with total 16.5-MB message overhead, requiring no more than 0.05-ms transmission delay in a 100-Gb/s backbone network with eight MEC servers, 1000 SIoTs, and 800 monitored locations.

关键词： Servers Collaboration Monitoring Internet of Things Social networking (online) Artificial intelligence Optimization approximation algorithm mobile-edge computing (MEC) NP-hard Social Internet of Things (SIoT)

来源：评论

学校读者我要写书评

暂无评论

Simple approximation algorithms for Balanced MAX 2SAT 12th

引用

12th Latin American Symposium on Theoretical Informatics (LATIN)

作者： Paul, Alice Poloczek, Matthias Williamson, David P. Cornell Univ Sch Operat Res & Informat Engn Ithaca NY 14850 USA

ISBN: (纸本)9783662495285

We study simple algorithms for the balanced MAX 2SAT problem, where we are given weighted clauses of length one and two with the property that for each variable x the total weight of clauses that x appears in equals the total weight of clauses for . We show that such instances have a simple structural property in that any optimal solution can satisfy at most the total weight of the clauses minus half the total weight of the unit clauses. Using this property and a novel analysis of the computation tree, we are able to show that a large class of greedy algorithms, including Johnson's algorithm, gives a -approximation algorithm for balanced MAX 2SAT;a similar statement is false for general MAX 2SAT instances. We further give a spectral 0.81-approximation algorithm for balanced MAX E2SAT instances (in which each clause has exactly 2 literals) by a reduction to a spectral algorithm of Trevisan for the maximum colored cut problem. We provide experimental results showing that this spectral algorithm performs well and is slightly better than Johnson's algorithm and the Goemans-Williamson semidefinite programming algorithm on balanced MAX E2SAT instances.

关键词： Maximum satisfiability approximation algorithm Greedy algorithm Spectral algorithm Balanced instances Priority algorithm

来源：评论

学校读者我要写书评

暂无评论

New approximation algorithms for the Minimum Cycle Cover Problem 12th

New Approximation Algorithms for the Minimum Cycle Cover Pro...

引用

12th International Frontiers of algorithmics Workshop (FAW)

作者： Yu, Wei Liu, Zhaohui Bao, Xiaoguang East China Univ Sci & Technol Dept Math Shanghai 200237 Peoples R China Shanghai Ocean Univ Coll Informat Technol Shanghai 201306 Peoples R China

ISBN: (纸本)9783319784557;9783319784540

Given an undirected weighted graph G = (V, E) with nonnegative weight function obeying the triangle inequality, a set {C-1, C-2, ... , C-k} of cycles is called a cycle cover if V subset of U-i=1(k) V (C-i) and its cost is given by the maximum weight of the cycles. The Minimum Cycle Cover Problem aims to find a cycle cover of cost at most lambda with the minimum number of cycles. An O(n(2)) 24/5-approximation algorithm and an O(n(5)) 14/3-approximation algorithm are given by Yu and Liu (Theor Comput Sci 654:45-58, 2016). However, the original proofs for approximation ratios are incomplete. In this paper we first present a corrected simplified analysis on the 24/5-approximation algorithm. Then we give a new O(n(3)) approximation algorithm that achieves the same ratio 14/3 and has much simpler proof on the approximation ratio. Moreover, we derive an improved 32/7-approximation algorithm that runs in O(n(5)).

关键词： Vehicle routing Cycle cover Traveling Salesman Problem approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

MASA: An efficient framework for anomaly detection in multi-attributed networks

引用

COMPUTERS & SECURITY 2021年 102卷 102085-102085页

作者： Shao, Minglai Li, Jianxin Chang, Yue Zhao, Jun Chen, Xunxun Beihang Univ Bejing Adv Innovat Ctr Big Data & Brain Comp Beijing Peoples R China Beihang Univ Sch Comp Sci & Engn Beijing Peoples R China CNCERT Beijing Peoples R China

Anomalous connected subgraph detection has been widely used in multiple scenarios, such as botnet detection, fraud detection and event detection. Nevertheless, the huge search space makes a serious computational challenge. Moreover, the anomalous connected sub graph detection becomes much harder when the networks involve a large number of attributes and become the multi-attributed networks. With the multi-attributed characteristic, most existing approaches are unable to solve this problem effectively and efficiently since it involves the anomalous connected subgraph detection and attributes selection simultaneously. In view of this, this paper proposes a general framework, namely multi attributed anomalous subgraphs and attributes scanning (MASA), to solve this problem in multi-attributed networks. We formulate and optimize a great number of complicated non parametric scan statistic functions that are employed to measure the joint anomalousness of the connected subgraphs and the corresponding subset of attributes in multi-attributed networks. More specifically, we first propose to transform each formulated nonparametric scan statistic function into a set of sub-functions with the theoretical analysis. Then using techniques of the tree approximation priors and the dynamic algorithms, an efficient approximation algorithm is presented to solve each transformed sub-function. Finally, with three real-world datasets from different domains, we conduct extensive experimental evaluations to demonstrate the effectiveness and efficiency of the proposed approach. (c) 2020 Elsevier Ltd. All rights reserved.

关键词： Multi-attributed networks Anomalous attributes selection Nonparametric scan statistic approximation algorithm Anomalous connected subgraph detection

来源：评论

学校读者我要写书评

暂无评论

Tight approximation for partial vertex cover with hard capacities

引用

THEORETICAL COMPUTER SCIENCE 2019年 778卷 61-72页

作者： Kao, Mong-Jen Shiau, Jia-Yau Lin, Ching-Chi Lee, D. T. Natl Chung Cheng Univ Dept Comp Sci & Informat Engn Chiayi Taiwan Natl Taiwan Univ Grad Inst Elect Engn Taipei Taiwan Natl Taiwan Ocean Univ Dept Comp Sci & Engn Keelung Taiwan Acad Sinica Inst Informat Sci Taipei Taiwan

We consider the partial vertex cover problem with hard capacity constraints (Partial VC-HC) on hypergraphs. In this problem we are given a hypergraph G = (V, E) with a maximum edge size f and a covering requirement 72. Each edge is associated with a demand, and each vertex is associated with a capacity and an (integral) available multiplicity. The objective is to compute a minimum vertex multiset such that at least 72 units of demand from the edges are covered by the capacities of the vertices in the multiset and the multiplicity of each vertex does not exceed its available multiplicity. In this paper we present an f-approximation for this problem, improving over a previous result of (2f + 2)(1 + epsilon) by Cheung et al. to the tight extent possible. Our new ingredient of this work is a generalized analysis on the extreme points of the natural LP, developed from previous works, and a strengthened LP lower-bound obtained for the optimal solutions. (C) 2019 Elsevier B.V. All rights reserved.

关键词： approximation algorithm Capacitated cover Partial cover Hard capacity

来源：评论

学校读者我要写书评

暂无评论

Adaptive Influence Maximization: If Influential Node Unwilling to Be the Seed

引用

ACM TRANSACTIONS ON KNOWLEDGE DISCOVERY FROM DATA 2021年第5期15卷 84-84页

作者： Guo, Jianxiong Wu, Weili Univ Texas Dallas Dept Comp Sci 800 W Campbell Rd Richardson TX 75080 USA

Influence maximization problem attempts to find a small subset of nodes that makes the expected influence spread maximized, which has been researched intensively before. They all assumed that each user in the seed set we select is activated successfully and then spread the influence. However, in the real scenario, not all users in the seed set are willing to be an influencer. Based on that, we consider each user associated with a probability with which we can activate her as a seed, and we can attempt to activate her many times. In this article, we study the adaptive influence maximization with multiple activations (Adaptive-IMMA) problem, where we select a node in each iteration, observe whether she accepts to be a seed, if yes, wait to observe the influence diffusion process;if no, we can attempt to activate her again with a higher cost or select another node as a seed. We model the multiple activations mathematically and define it on the domain of integer lattice. We propose a new concept, adaptive dr-submodularity, and show our Adaptive-IMMA is the problem that maximizing an adaptive monotone and dr-submodular function under the expected knapsack constraint. Adaptive dr-submodular maximization problem is never covered by any existing studies. Thus, we summarize its properties and study its approximability comprehensively, which is a non-trivial generalization of existing analysis about adaptive submodularity. Besides, to overcome the difficulty to estimate the expected influence spread, we combine our adaptive greedy policy with sampling techniques without losing the approximation ratio but reducing the time complexity. Finally, we conduct experiments on several real datasets to evaluate the effectiveness and efficiency of our proposed policies.

关键词： Adaptive influence maximization social networks integer lattice adaptive dr-submodularity sampling techniques approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Implementing synchronous reactive components upon multiprocessor platforms

引用

JOURNAL OF SYSTEMS ARCHITECTURE 2021年 116卷 102027-102027页

作者： Baruah, Sanjoy Washington Univ St Louis MO 63110 USA

Model-based design methodologies based on the synchrony assumption are widely used in many safety-critical application domains. The synchrony assumption asserts that actions (such as the execution of code) occur instantaneously;however, physical platforms obviously do not possess this property. This paper considers a scheduling problem that arises when one seeks to implement programs that are written under the synchrony assumption upon actual multiprocessor platforms, and proposes algorithms for solving this problem exactly and approximately.

关键词： Synchronous programming Multiprocessor scheduling Deadlines Integer Linear Program approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：