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

Proceedings of the 2022 6th International Conference on Computer Science and Artificial Intelligence

作者： Ruiqing Sun Bin Deng Yunnan University China

ISBN: (纸本)9781450397773

In this paper, we consider the W-prize-collecting scheduling problem on a single machine, where each job has a profit. The objective is to minimize the makespan of the accepted jobs and the total rejection cost of the rejected jobs, conditional on their total profit no less than a given threshold. We first analyze the computational complexities when all jobs have the same parameter. Then, we present a 2-approximation algorithm. Furthermore, we provide two pseudo-polynomial time algorithms. Finally, a fully polynomial time approximation scheme (FPTAS) is given for this problem. Our numerical tests indicate that both dynamic programming algorithms can easily solve large-size problems.

关键词： Dynamic programming FPTAS approximation algorithm Scheduling with rejection NP-hard

来源：评论

学校读者我要写书评

暂无评论

A parallel game model-based intrusion response system for cross-layer security in industrial internet of things

引用

CONCURRENCY AND COMPUTATION-PRACTICE & EXPERIENCE 2023年第28期35卷 e7826-e7826页

作者： Yu, Siyang Wu, Fan Chen, Baoding Cao, Ronghui Yang, Zhibang Li, Keqin Hunan Univ Finance & Econ Coll Informat Technol & Management Changsha Peoples R China Hunan Univ Coll Comp Sci & Engn Changsha Hunan Peoples R China Changsha Univ Sci Technol Coll Comp & Commun Engn Changsha Hunan Peoples R China State Univ New York Dept Comp Sci New York NY USA Hunan Univ Coll Comp Sci & Engn Changsha 410008 Hunan Peoples R China

With the rise of industrialization, the importance of the industrial Internet of Things (IIoT) has increased significantly, and with it comes a variety of security threats. Therefore, the security of these networks is critical. Industrial Response Systems (IRSs), as the last line of security, plays an important role in the security system of the Industrial Internet of Things. In this paper, a new IRS model based on the non-cooperative game is proposed. First, by combining the Partially Observable Markov Decision Process (POMDP) model with the stochastic game model based on the expanded attack tree, our model could effectively perceive the changes at each node. Second, our model incorporates the alarms of intrusion detection system (IDS) and the physical quantities of sensors in Industrial Cyber-Physical System (ICPS) into the quantization system so that the model can respond to intruders more accurately and comprehensively. Finally, we develop this model based on multiprocessors to speed up the solution process, and adopt an approximation algorithm to reduce the number of iterations of the POMDP

关键词： approximation algorithm parallel partially observable Markov decision stochastic games

来源：评论

学校读者我要写书评

暂无评论

Sublinear approximation algorithms for boxicity and related problems

引用

DISCRETE APPLIED MATHEMATICS 2018年 236卷 7-22页

作者： Adiga, Abhijin Babu, Jasine Chandran, L. Sunil Virginia Tech Blacksburg VA 24061 USA Indian Inst Technol Palakkad India Indian Inst Sci Bangalore Karnataka India

The boxicity of a graph G(V, E) is the minimum integer k such that G can be represented as the intersection graph of axis parallel boxes in R-k. Cubicity is a variant of boxicity, where the axis parallel boxes in the intersection representation are restricted to be of unit length sides. Deciding whether the boxicity (resp. cubicity) of a graph is at most k is NP-hard, even for k = 2 or 3. Computing these parameters is inapproximable within O(n(1 -) (epsilon))-factor, for any epsilon > 0 in polynomial time unless NP = ZPP, even for many simple graph classes. In this paper, we give a polynomial time k(n) factor approximation algorithm for computing boxicity and a K(n)[log logn] factor approximation algorithm for computing the cubicity, where K(n) = 2 [n root loglogn / root logn]. These o(n) factor approximation algorithms also produce the corresponding box (resp. cube) representations. As a special case, this resolves the question posed by Spinrad (2003) about polynomial time construction of o(n) dimensional box representations for boxicity 2 graphs. Other consequences of our approximation algorithm include 0(K(n)) factor approximation algorithms for computing the following parameters: the partial order dimension (poset dimension) of finite posets, the interval dimension of finite posets, minimum chain cover of bipartite graphs, Ferrers dimension of digraphs and threshold dimension of split graphs and co-bipartite graphs. Each of these parameters is inapproximable within an O(n(1 -) (epsilon))-factor, for any e > 0 in polynomial time unless NP = ZPP and the algorithms we derive seem to be the first o(n) factor approximation algorithms known for all these problems. We note that obtaining a o(n) factor approximation for poset dimension was also mentioned as an open problem by Felsner et al. (2017). In the second part of this paper, parameterized approximation algorithms for boxicity using various edit distance parameters are derived. We also present a parameterized appr

关键词： Boxicity approximation algorithm Partial order dimension Threshold dimension Parameterization

来源：评论

学校读者我要写书评

暂无评论

Improved approximation algorithms for k-connected m-dominating set problems

引用

INFORMATION PROCESSING LETTERS 2018年 140卷 30-33页

作者： Nutov, Zeev Open Univ Israel Raanana Israel

A graph is k-connected if it has k pairwise internally node disjoint paths between every pair of its nodes. A subset S of nodes in a graph G is a k-connected set if the subgraph G[S] induced by S is k-connected;S is an m-dominating set if every v is an element of V\S has at least m neighbors in S. If S is both k-connected and m-dominating then S is a k-connected m-dominating set, or (k, m)-CdS for short. In the k-CONNECTED M-DOMINATING SET ((k, m)-CDS) problem the goal is to find a minimum weight (k, m)-cds in a node-weighted graph. We consider the case m >= k and obtain the following approximation ratios. For unit disc graphs we obtain ratio O(k ln k), improving the ratio O(k(2) ln k) of [1,2]. For general graphs we obtain the first non-trivial approximation ratio O(k(2) ln n). (C) 2018 Elsevier B.V. All rights reserved.

关键词： k-Connected graph m-Dominating set approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Integer Plane Multiflow Maximisation: Flow-Cut Gap and One-Quarter-approximation 1

引用

21st International Conference on Integer Programming and Combinatorial Optimization (IPCO)

作者： Garg, Naveen Kumar, Nikhil Sebo, Andras Indian Inst Technol Delhi Delhi India Univ Grenoble Alpes CNRS Lab G SCOP Grenoble France

ISBN: (数字)9783030457716

ISBN: (纸本)9783030457716;9783030457709

In this paper, we bound the integrality gap and the approximation ratio for maximum plane multiflow problems and deduce bounds on the flow-cut-gap. Planarity means here that the union of the supply and demand graph is planar. We first prove that there exists a multiflow of value at least half of the capacity of a minimum multicut. We then show how to convert any multiflow into a half-integer one of value at least half of the original multiflow. Finally, we round any half-integer multiflow into an integer multiflow, losing again at most half of the value, in polynomial time, achieving a 1/4-approximation algorithm for maximum integer multiflows in the plane, and an integer-flow-cut gap of 8.

关键词： Multicommodity flow Multiflow Multicut Network design Planar graphs Flow-cut Integrality gap approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

A semidefinite relaxation approach for the offloading problem in edge computing

引用

COMPUTERS & ELECTRICAL ENGINEERING 2022年 98卷 107728-107728页

作者： Han, Xinxin Gao, Guichen Ning, Li Wang, Yang Zhang, Yong Chinese Acad Sci Shenzhen Inst Adv Technol Shenzhen Peoples R China Univ Chinese Acad Sci Beijing Peoples R China Guangxi Key Lab Cryptog & Informat Secur Guilin Peoples R China

In traditional cloud computing, tasks will be offloaded to the could, which often leads to high latency and low quality of service. To avoid this disadvantage, edge computing was introduced. The fundamental issue in edge computing is selecting some tasks to be computed in the edge, which is called the offloading problem. In most previous studies, the communication cost between any two tasks is often assumed to be symmetric in different sides and is often ignored within the same side. In this paper, we consider a heterogeneous offloading model, where the communication cost exists everywhere and is asymmetric. With the help of semidefinite relaxation, we give an algorithm for the offloading problem. If the Laplacian matrix with respect to the offloading problem is positive semidefinite, the theoretical guarantee can be proved to be 2/pi. The performance of the proposed algorithm is also evaluated via numerical analysis. The experimental results show that the algorithm is very effective.

关键词： Edge computing Offloading approximation algorithm Semidefinite relaxation Performance ratio

来源：评论

学校读者我要写书评

暂无评论

A novel health prognosis method for system based on improved degenerated Hidden Markov model

引用

ROBOTICS AND COMPUTER-INTEGRATED MANUFACTURING 2022年第0期78卷

作者： Liu, Qinming Chen, Xiang Dong, Ming Chen, Frank Univ Shanghai Sci & Technol Business Sch Dept Ind Engn 516 Jungong Rd Shanghai 200093 Peoples R China Shanghai Jiao Tong Univ Antai Coll Econ & Management Dept Operat Management 1954 Huashan Rd Shanghai 200030 Peoples R China Univ Texas San Antonio Dept Mech Engn San Antonio TX 78249 USA

Health prognosis for power system is considered as a crucial process of condition-based maintenance. In order to solve the problem of large deviation between Hidden Markov Model and actual system health diagnosis, this paper developed an improved Degenerated Hidden Markov Model (DGHMM) with a core of the quasi power relation. First, the model adopts the degradation factors described the process of recession for equipment continuous decreasing in performance. Compared with the conventional exponential accelerated degradation, the quasi power relation accelerated degradation can better describe the process that the performance of the system decreases gradually with the increase of service age. Then, the improved genetic algorithm can replace the conventional EM algorithm for parameters estimation, which overcomes the limitation that the EM algorithm is easy to fall into local optimization. At the same time, in terms of the limitation of life prognosis problem as a result of the Hidden Markov Model must obey exponential distribution, an algorithm named greed approximation based on approximation algorithm and Viterbi algorithm can be proposed to seek maximum probability remaining observation for the purpose of seeking maximum probability dynamically surplus state path to predict the residual life of system. Finally, the proposed method is validated and evaluated with the data set of caterpillar hydraulic pumps. The results show that the method of system health diagnosis and life prognosis based on the improved degraded hidden Markov model is more effective in describing system degeneration and the accuracy of equipment state diagnosis, and is also feasible in the prediction of residual life.

关键词： Hidden Markov model Degradation health diagnostics Residual useful lifetime Genetic algorithm approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Energy-aware Preprocessing for Distributed Training in D2D Edge Network with Non-iid Data 12

Energy-aware Preprocessing for Distributed Training in D2D E...

引用

12th International Symposium on Parallel Architectures, algorithms and Programming (PAAP)

作者： Wu, Jiaxin Wu, Jigang Chen, Long Sun, Yifei Guangdong Univ Technol Sch Comp Sci & Technol Guangzhou Peoples R China

ISBN: (纸本)9781665496391

Inherent non-iid characteristic of heterogeneous devices' local dataset slows down the model training process and decreases the training accuracy. To tackle this problem, we propose a dataset reconstruction scheme to transform training device's non-iid dataset into iid dataset via data exchange among trusted devices. Two data exchange modes are proposed to serve the scheme. Considering the transmission overhead, we formulate an optimization problem named NORS to minimize the total energy consumption of devices. We then design an approximation algorithm named X-GTR to obtain a near-optimal auxiliary devices set for dataset reconstruction, while meeting the variance constraint of NORS. For comparison, we propose a baseline algorithm that randomly selects auxiliary devices for dataset reconstruction. Numerical results show that, with the total number of devices increasing, our proposed algorithm outperforms baseline algorithm on reducing energy consumption.

关键词： D2D distributed training approximation algorithm weighted set covering

来源：评论

学校读者我要写书评

暂无评论

Submodular Maximization Subject to a Knapsack Constraint Under Noise Models

引用

ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH 2022年第6期39卷 2250013-2250013页

作者： Ha, Dung T. K. Pham, Canh, V Hoang, Huan X. Univ Engn & Technol Vietnam Natl Univ Fac Informat Technol 144 Xuan Thuy St Hanoi 10000 Vietnam Phenikaa Univ Fac Comp Sci ORLab Yen Nghia Ward Hanoi 12116 Vietnam

The field of Submodular Maximization subject to a Knapsack constraint has recently expanded to a variety of application domains, which is facing some challenges such as data explosions or additional conditions. There exist plenty of objective functions that cannot be evaluated exactly in many real cases unless they are estimated with errors. It leads to solving the problem under noise models. Somewhat surprisingly, Submodular Maximization subject to a Knapsack constraint under Noise models (SMKN) has never been discussed a lot before. Hence, in this paper, we consider the problem with two kinds of noise models which are addition and multiplication. Inspired by the traditional Greedy algorithm, we first propose a Greedy algorithm under Noises with provable theoretical bounds. In order to find the solution when input data are extremely large, we then devise an efficient streaming algorithm that scans only a single pass over the data and guarantees theoretical approximations. Finally, we conduct some experiments on Influence Maximization problem under knapsack constraint, an instance of SMKN to show the performances of the proposed algorithms.

关键词： Submodular knapsack constraint approximation algorithm noises

来源：评论

学校读者我要写书评

暂无评论

Packet-in request redirection: A load-balancing mechanism for minimizing control plane response time in SDNs

引用

JOURNAL OF SYSTEMS ARCHITECTURE 2022年 129卷

作者： Xia, Rui Dai, Haipeng Zheng, Jiaqi Xu, Hong Li, Meng Chen, Guihai Nanjing Univ State Key Lab Novel Software Technol Nanjing 210023 Peoples R China Chinese Univ Hong Kong Dept Comp Sci & Engn Shatin Hong Kong Peoples R China

A distributed control plane is more scalable and robust in software defined networking. This paper focuses on controller load balancing using packet-in request redirection, that is, given the instantaneous state of the system, determining whether to redirect packet-in requests for each switch, such that the overall control plane response time (CPRT) is minimized. To address the above problem, we propose a framework based on Lyapunov optimization. First, we use the drift-plus-penalty algorithm to combine CPRT minimization problem with controller capacity constraints, and further derive a non-linear program, whose optimal solution is obtained with brute force using standard linearization techniques. Second, we present a greedy strategy to efficiently obtain a solution with a bounded approximation ratio. Third, we reformulate the program as a problem of maximizing a non-monotone submodular function subject to matroid constraints. We implement a controller prototype for packet-in request redirection, and conduct trace-driven simulations to validate our theoretical results. The results show that our algorithms can reduce the average CPRT by 81.6% compared to static assignment, and achieve a 3x improvement in maximum controller capacity violation ratio.

关键词： Software defined networking (SDN) Distributed control plane Load balancing Lyapunov optimization approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：