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

Bottleneck Crosstalk Minimization in Two- and Three-Layer Manhattan Channel Routing

IEEE ACCESS 2024年 12卷 148332-148373页

作者： Mandal, Tarak Nath Sarkar, Suvarthi Roy, Deborupa Khan, Abhinandan Mehera, Ranjan Datta, Alak Kumar Pal, Rajat Kumar Microsoft India R&D Pvt Ltd Microsoft Campus Hyderabad 500032 Telangana India Univ Calcutta Dept Comp Sci & Engn Kolkata 700106 India Indian Inst Technol Guwahati Dept Comp Sci & Engn Gauhati 781039 Assam India Oracle India Pvt Ltd Hyderabad 500081 India ARP Engn Kolkata 700056 India Anodot Inc Ashburn VA 20147 USA Visva Bharati Univ Dept Comp & Syst Sci Birbhum 731235 West Bengal India

VLSI physical design is a domain of work as old as more than five decades. Even then, as technology progresses, there are several challenging issues from the perspective of theoretical computer science as well as the high-performance requirements of the chip to be designed. Crosstalk is a threat to achieving routing solutions in high-performance VLSI circuits. As fabrication technology advances, closeness occurs among the devices and their interconnecting wires, the size of the devices and chips reduces, and circuits' operational frequencies increase. These result in crosstalk, a kind of electrical hazard, which over stresses wire segments that are placed sideways. In this paper, it has been proved that the bottleneck crosstalk minimisation problems in the reserved two- and three-layer Manhattan channel routing are NP-complete. It has also been established that the hardness proclaims in approximating all allied crosstalk minimisation problems. As a natural consequence, heuristics have been devised to realise two- and three-layer bottleneck crosstalk routing solutions for different predefined bottleneck values employed over already computed channel routing solutions. Exhaustive experimentation has been performed and promising experimental results have been accomplished often sacrificing a bit more channel area.

关键词： Routing Crosstalk Wires Minimization Very large scale integration Insulation life Delays Degradation Physical design Integrated circuit interconnections approximation algorithm bottleneck crosstalk channel routing problem crosstalk minimization heuristic high-performance routing NP-hardness two- and three-layer routing

来源：评论

学校读者我要写书评

暂无评论

A Multi-Feature Diffusion Model: Rumor Blocking in Social Networks

引用

IEEE-ACM TRANSACTIONS ON NETWORKING 2021年第1期29卷 386-397页

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

Online social networks provide a convenient platform for the spread of rumors, which could lead to serious aftermaths such as economic losses and public panic. The classical rumor blocking problem aims to launch a set of nodes as a positive cascade to compete with misinformation in order to limit the spread of rumors. However, most of the related researches were based on a one-dimensional diffusion model. In reality, there is more than one feature associated with an object. A user's impression on this object is determined not just by one feature but by her overall evaluation of all features associated with it. Thus, the influence spread of this object can be decomposed into the spread of multiple features. Based on that, we design a multi-feature diffusion model (MF-model) in this paper and formulate a multi-feature rumor blocking (MFRB) problem on a multi-layer network structure according to this model. To solve the MFRB problem, we design a creative sampling method called Multi-Sampling, which can be applied to this multi-layer network structure. Then, we propose a Revised-IMM algorithm and obtain a satisfactory approximate solution to MFRB. Finally, we evaluate our proposed algorithm by conducting experiments on real datasets, which shows the effectiveness of our Revised-IMM and its advantage to their baseline algorithms.

关键词： Social networking (online) approximation algorithms Computational modeling IEEE transactions Sampling methods Automobiles Multi-feature diffusion rumor blocking social networks sampling approximation algorithm martingale

来源：评论

学校读者我要写书评

暂无评论

Sampling-Based Approximate Skyline Query in Sensor Equipped IoT Networks

引用

Tsinghua Science and Technology 2021年第2期26卷 219-229页

作者： Ran Bi Akshita Maradapu Vera Venkata Sai Xiuzhen Cheng Wei Cheng Zhi Tian Yingshu Li Kennesaw State University MariettaGA 30060USA Georgia State University AtlantaGA 30303USA The George Washington University WashingtonDC 20052USA Department of Computer Science Virginia Commonwealth UniversityRichmondVA 23284USA Department of Electrical&Computer Engineering George Mason UniversityFairfaxVA 22030USA

Mobile-edge computing casts the computation-intensive and delay-sensitive applications of mobile devices onto network *** offloading incurs extra communication latency and energy cost,and extensive efforts have focused on offloading *** metrics of the system utility are defined to achieve satisfactory quality of ***,most existing works overlook the balance between throughput and *** study investigates the problem of finding an optimal offloading scheme in which the objective of optimization aims to maximize the system utility for leveraging between throughput and *** on Karush-Kuhn-Tucker condition,the expectation of time complexity is analyzed to derive the optimal scheme.A gradient-based approach for utility-aware task offloading is ***,we provide an increment-based greedy approximation algorithm with 1+1/(e-1)*** results show that the proposed algorithms can achieve effective performance in utility and accuracy.

关键词： utility approximation algorithm quality of experience mobile edge computing

来源：评论

学校读者我要写书评

暂无评论

A better LP rounding for feedback arc set on tournaments

引用

THEORETICAL COMPUTER SCIENCE 2024年 1015卷

作者： Ostovari, Mojtaba Zarei, Alireza Sharif Univ Technol Dept Math Sci Tehran Iran

We present a randomized algorithm to approximate the feedback arc set problem on weighted tournaments, a classic well-studied NP-hard problem. Our algorithm is based on rounding its standard linear programming relaxation. It improves the previously best-known LP rounding algorithm by achieving an approximation factor of 2.127 (best known was 2.5). As a result, we have found a better upper bound for the integrality gap of the corresponding LP.

关键词： approximation algorithm Feedback arc set Tournament LP rounding

来源：评论

学校读者我要写书评

暂无评论

VColor^(*):a practical approach for coloring large graphs

引用

Frontiers of Computer Science 2021年第4期15卷 133-149页

作者： Yun PENG Xin LIN Byron CHOI Bingsheng HE Department of Computer Science Hong Kong Baptist UniversityHong Kong 999077China School of Computer Science and Technology East China Normal UniversityShanghai 200062China School of Computing National University of SingaporeSingapore 119077Singapore

Graph coloring has a wide range of real world applications,such as in the operations research,communication network,computational biology and compiler optimization *** our recent work[1],we propose a divide-andconquer approach for graph coloring,called *** an approach has three generic subroutines.(i)Graph partition subroutine:VColor partitions a graph G into a vertex cut partition(VP),which comprises a vertex cut component(VCC)and small non-overlapping connected components(CCs).(ii)Component coloring subroutine:VColor colors the VCC and the CCs by efficient algorithms.(iii)Color combination subroutine:VColor combines the local colors by exploiting the maximum matchings of color combination bigraphs(CCBs).VColor has revealed some major bottlenecks of efficiency in these ***,in this paper,we propose VColor^(*),an approach which addresses these efficiency bottlenecks without using more colors both theoretically and *** technical novelties of this paper are the following.(i)We propose the augmented VP to index the crossing edges of the VCC and the CCs and propose an optimized CCB construction algorithm.(ii)For sparse CCs,we propose using a greedy coloring algorithm that is of polynomial time complexity in the worst case,while preserving the approximation ratio.(iii)We propose a distributed graph coloring *** extensive experimental evaluation on real-world graphs confirms the efficiency of VColor^(*).In particular,VColor^(*)is 20X and 50X faster than VColor and uses the same number of colors with VColor on the Pokec and PA datasets,***^(*)also significantly outperforms the state-ofthe-art graph coloring methods.

关键词： graph coloring approximation algorithm distributed algorithm

来源：评论

学校读者我要写书评

暂无评论

Maximum Profit Routing for Mobile Crowdsensing 21

Maximum Profit Routing for Mobile Crowdsensing

引用

21st ACM/IEEE International Conference on Information Processing in Sensor Networks (IPSN)

作者： Li, Zhiyao Zhang, Jiale Gao, Xiaofeng Chen, Guihai Shanghai Jiao Tong Univ Dept Comp Sci & Engn MoE Key Lab Artificial Intelligence Shanghai Peoples R China

ISBN: (纸本)9781665496247

Wireless sensor networks and mobile crowdsensing are two important paradigms in urban dynamic sensing. In both sensing paradigms, task allocation is a significant problem that may affect the completion quality of sensing tasks. In this paper, we focus on allocating sensing tasks for mobile crowdsensing. We propose a system model to illustrate how the allocation mechanism works in crowdsensing and define the task allocation problem as maximum profit routing for mobile crowdsensing (MPRMC). The NP-hardness of MPRMC is proved based on a special case analysis. To solve MPRMC, we consider the problem in two special cases: Temporal-MPRMC and Spatial-MPRMC. Correspondingly, we propose a fully polynomial-time approximation scheme for Temporal-MPRMC and a 2 gamma-approximation for Spatial-MPRMC, respectively. Then, we generalize the special cases and give a 2 gamma lg(2) n-approximation for MPRMC. To the best of our knowledge, our algorithms have the best approximation ratios for MPRMC. Finally, we conduct various experiments to validate the effectiveness of our designs.

关键词： Crowdsensing Task Allocation approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Schedule or Wait: Age-Minimization for IoT Big Data Processing in MEC via Online Learning 41

Schedule or Wait: Age-Minimization for IoT Big Data Processi...

引用

41st IEEE Conference on Computer Communications (IEEE INFOCOM)

作者： Xu, Zichuan Ren, Wenhao Liang, Weifa Xu, Wenzheng Xia, Qiufen Zhou, Pan Li, Mingchu Dalian Univ Technol Sch Software Dalian 116621 Peoples R China City Univ Hong Kong Dept Comp Sci Hong Kong Peoples R China Sichuan Univ Coll Comp Sci Chengdu 610065 Sichuan Peoples R China Dalian Univ Technol Int Sch Informat Sci & Engn Dalian 116621 Peoples R China Huazhong Univ Sci & Technol Hubei Engn Res Ctr Big Data Secur Sch Cyber Sci & Engn Wuhan 430074 Peoples R China

ISBN: (纸本)9781665458221

The age of data (AoD) is identified as one of the most novel and important metrics to measure the quality of big data analytics for Internet-of-Things (IoT) applications. Meanwhile, mobile edge computing (MEC) is envisioned as an enabling technology to minimize the AoD of IoT applications by processing the data in edge servers close to IoT devices. In this paper, we study the AoD minimization problem for IoT big data processing in MEC networks. We first propose an exact solution for the problem by formulating it as an Integer Linear Program (ILP). We then propose an efficient heuristic for the offline AoD minimization problem. We also devise an approximation algorithm with a provable approximation ratio for a special case of the problem, by leveraging the parametric rounding technique. We thirdly develop an online learning algorithm with a bounded regret for the online AoD minimization problem under dynamic arrivals of IoT requests and uncertain network delay assumptions, by adopting the Multi-Armed Bandit (MAB) technique. We finally evaluate the performance of the proposed algorithms by extensive simulations and implementations in a real test-bed. Results show that the proposed algorithms outperform existing approaches by reducing the AoD around 10%.

关键词： Mobile edge cloud Big data processing Age of data approximation algorithm Online learning

来源：评论

学校读者我要写书评

暂无评论

Maximizing Approximately Non-k-Submodular Monotone Set Function with Matroid Constraint 17th

Maximizing Approximately Non-k-Submodular Monotone Set Funct...

引用

17th Annual Conference on Theory and Applications of Models of Computation (TAMC)

作者： Jiang, Yanjun Wang, Yijing Yang, Ruiqi Ye, Weina Ludong Univ Sch Math & Stat Sci Yantai 264025 Peoples R China Chinese Acad Sci Acad Math & Syst Sci Beijing 100190 Peoples R China Beijing Univ Technol Beijing Inst Sci & Engn Comp Beijing 100124 Peoples R China Univ Chinese Acad Sci Sch Math Sci Beijing 100049 Peoples R China

ISBN: (纸本)9783031203497;9783031203503

Utilizing approximation algorithm, there has been a large quantity of work on optimization for submodular functions since the 1970s. As a variant, k-submodular function appears in many fields to match with the developing background, in which the outputted sets changes from one to k. Because of the application of submodularity, some concepts and parameters describing the closeness to submodular function are generated, for example approximately submodular set function and diminishing-return (DR) ratio. In our discussion, the k-dimension set function with matroid constraint we will maximize may not have access to the submodularity. However it is an approximately non-k-submodular set function which contains DR ratio. By the greedy technique, we obtain the approximation algorithms. When the value of the DR ratio is set one, some known results are covered.

关键词： k-submodular set function Matroid Greedy approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Improved Parallel algorithm for Minimum Cost Submodular Cover Problem 35

Improved Parallel Algorithm for Minimum Cost Submodular Cove...

引用

35th Conference on Learning Theory (COLT)

作者： Ran, Yingli Zhang, Zhao Tang, Shaojie Zhejiang Normal Univ Coll Math & Comp Sci Jinhua Zhejiang Peoples R China Univ Texas Dallas Naveen Jindal Sch Management Richardson TX 75083 USA

In the minimum cost submodular cover problem (MinSMC), we are given a monotone nondecreasing submodular function f : 2(V) -> Z(+), a linear cost function c : V -> R+, and an integer k <= f(V), the goal is to find a subset A subset of V with the minimum cost such that f(A) >= k. The MinSMC can be found at the heart of many machine learning and data mining applications. In this paper, we design a parallel algorithm for the MinSMC that takes at most O(log(km) log k(logm+log log(mk))/epsilon(4)) adaptive rounds, and it achieves an approximation ratio of H(min{Delta,k})/1-5 epsilon with probability at least 1 - 3 epsilon, where Delta = max(v subset of V) f(v), H(center dot) is the Harmonic number, m = vertical bar V vertical bar, and epsilon is a constant in (0, 1/5).

关键词： minimum cost submodular cover approximation algorithm parallel algorithm.

来源：评论

学校读者我要写书评

暂无评论

Bounded mixed batch scheduling with job release dates and rejection

引用

OPERATIONS RESEARCH LETTERS 2024年 57卷

作者： Xu, Jun Huang, Yong-Xing Zhang, Daxing Lin, Ran Fan, Guo-Qiang Xidian Univ Guangzhou Inst Technol Adv Mfg Technol Innovat Ctr Guangzhou 510555 Peoples R China Northwestern Polytech Univ Sch Mech Engn Dept Ind Engn Xian 710072 Peoples R China Zhengzhou Univ Sch Math & Stat Zhengzhou 450001 Peoples R China Xidian Univ Sch Econ & Management Xian 710126 Peoples R China

This paper investigates a bounded mixed batch scheduling problem with job release dates and rejection. The machine processes a batch containing several jobs that their number does not exceed the machine capacity. For the case with a certain release date, we present a polynomial-time exact algorithm. For the case with a constant number of release dates, a pseudo-polynomial-time exact algorithm is proposed. For the general problem, we provide a 2-approximation algorithm and a polynomial-time approximation scheme. (c) 2024 Elsevier B.V. All rights are reserved, including those for text and data mining, AI training, and similar technologies.

关键词： Mixed batch scheduling Rejection penalty Exact algorithm approximation algorithm Polynomial-time approximation scheme

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：