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

Minimum Dominating Set Problem for unit Disks Revisited

International Journal of Computational Geometry and Applications 2015年第3期25卷 227-244页

作者： Carmi, Paz Das, Gautam K. Jallu, Ramesh K. Nandy, Subhas C. Prasad, Prajwal R. Stein, Yael Department of Computer Science Ben-Gurion University of the Negev Beer-Sheva 84105 Israel Department of Mathematics Indian Institute of Technology Guwahati Guwahati 781039 India Advanced Computing and Microelectronics Unit Indian Statistical Institute Kolkata 700108 India National Institute of Technology Karnataka Mangalore 575025 India

In this article, we study approximation algorithms for the problem of computing minimum dominating set for a given set S of n unit disks in R2. We first present a simple O(nlogk) time 5-factor approximation algorithm ... 详细信息

In this article, we study approximation algorithms for the problem of computing minimum dominating set for a given set S of n unit disks in R². We first present a simple O(nlogk) time 5-factor approximation algorithm for this problem, where k is the size of the output. The best known 4-factor and 3-factor approximation algorithms for the same problem run in time O(n8logn) and O(n15logn) respectively [M. De, G. K. Das, P. Carmi and S. C. Nandy, Approximation algorithms for a variant of discrete piercing set problem for unit disks, Int. J. of Computational Geometry and Appl., 22(6):461-477, 2013]. We show that the time complexity of the in-place 4-factor approximation algorithm for this problem can be improved to O(n6logn). A minor modification of this algorithm produces a 143-factor approximation algorithm in O(n5logn) time. The same techniques can be applied to have a 3-factor and a 4513-factor approximation algorithms in time O(n11logn) and O(n10logn) respectively. Finally, we propose a very important shifting lemma, which is of independent interest, and it helps to present 52-factor approximation algorithm for the same problem. It also helps to improve the time complexity of the proposed PTAS for the problem. © 2015 World Scientific Publishing Company.

关键词： approximation algorithm Minimum dominating set unit disk graph

来源：评论

学校读者我要写书评

暂无评论

Placing Two Axis-Parallel Squares to Maximize the Number of Enclosed Points

引用

International Journal of Computational Geometry and Applications 2015年第4期25卷 263-282页

作者： Mahapatra, Priya Ranjan Sinha Goswami, Partha P. Das, Sandip Department of Computer Science and Engineering University of Kalyani West-Bengal India Institute of Radiophysics and Electronics University of Calcutta Kolkata India Advance Computing and Microelectronics Unit Indian Statistical Institute Kolkata India

Let P be a set of n input points in the plane. An algorithm is proposed to place a pair of axis-parallel unit squares, either intersecting with no points in the intersection zone or disjoint, together enclosing the maximum number of input points. The time and space complexities of the algorithm are both O(n2). In case the input points are allowed to lie inside the intersection zone of two intersecting axis-parallel unit squares, two such unit squares enclosing the maximum number of input points can be placed in O(n2log2n) time using O(nlogn) space. © 2015 World Scientific Publishing Company.

关键词： computational geometry dynamic programming k-enclosing problem Maximal enclosing problem staircase

来源：评论

学校读者我要写书评

暂无评论

Web Service Selection with Correlations: A Feature-Based Abstraction Refinement Approach

Web Service Selection with Correlations: A Feature-Based Abs...

引用

IEEE International Conference on Service-Oriented computing and Applications (SOCA)

作者： Kaustabha Ray Ansuman Banerjee Swarup K. Mohalik Advanced Computing and Microelectronics Unit Indian Statistical Institute Ericsson Research Bangalore India

In this paper, we address the web service selection problem for linear workflows. Given a linear workflow specifying a set of ordered tasks and a set of candidate services providing different features for each task, the selection problem deals with the objective of selecting the most eligible service for each task, given the ordering specified. A number of approaches to solving the selection problem have been proposed in literature. With web services growing at an incredible pace, service selection at the Internet scale has resurfaced as a problem of recent research interest. In this work, we present our approach to the selection problem using an abstraction refinement technique to address the scalability limitations of contemporary approaches. Experiments on web service benchmarks show that our approach can add substantial performance benefits in terms of space when compared to an approach without our optimization.

关键词： Task analysis Web services Correlation Scalability Proposals Silicon compounds

来源：评论

学校读者我要写书评

暂无评论

SOK: An Evaluation of Quantum Authentication through Systematic Literature Review

SSRN

引用

SSRN 2021年

作者： Majumdar, Ritajit Das, Sanchari Advanced Computing and Microelectronics Unit Indian Statistical Institute Kolkata India University of Denver

Quantum computers are considered a blessing to the dynamic technological world that promises to solve complex problems much faster than their known classical counterparts. Such computational power imposes critical threats on modern cryptography where it has been proven that asymmetric key cryptosystem will be rendered useless in a quantum world. However, we can utilize such a powerful mechanism for improving computer security by implementing such technology to solve complex data security problems such as authentication, secrets management, and others. Mainly, Quantum Authentication (QA) is an emerging concept in computer security that creates robust authentication for organizations, systems, and individuals. To delve deeper into the concept, for this research, we have further investigated QA through a detailed systematic literature review done on a corpus of N = 859 papers. We briefly discuss the major protocols used by various papers to achieve QA, and also note the distribution of papers using those protocols. We analyzed the technological limitations mentioned by previous researchers and highlighted the lack of human-centered solutions for such modern inventions. We emphasize the importance of research in the user aspect of QA to make the users aware of its potential advantages and disadvantages as we move to the quantum age. © 2021, The Authors. All rights reserved.

关键词： Authentication

来源：评论

学校读者我要写书评

暂无评论

The p-center problem in tree networks revisited 15

The p-center problem in tree networks revisited

引用

15th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2016

作者： Banik, Aritra Bhattacharya, Binay Das, Sandip Kameda, Tsunehiko Song, Zhao Advanced Computing and Microelectronics Unit Indian Statistical Inst. Kolkata India School of Computing Science Simon Fraser University Vancouver Canada Department of Computer Science University of Texas Austin United States

ISBN: (纸本)9783959770118

We present two improved algorithms for weighted discrete p-center problem for tree networks with n vertices. One of our proposed algorithms runs in O(n log n + p log2 n log(n/p)) time. For all values of p, our algorithm thus runs as fast as or faster than the most efficient O(n log2 n) time algorithm obtained by applying Cole's speed-up technique [10] to the algorithm due to Megiddo and Tamir [20], which has remained unchallenged for nearly 30 years. Our other algorithm, which is more practical, runs in O(n log n + p2 log2 (n/p)) time, and when p = O(√ n) it is faster than Megiddo and Tamir's O(n log2 n log log n) time algorithm [20]. © Aritra Banik, Binay Bhattacharya, Sandip Das, Tsunehiko Kameda, and Zhao Song.

关键词： Forestry

来源：评论

学校读者我要写书评

暂无评论

Proactive Microservice Placement and Migration for Mobile Edge computing

Proactive Microservice Placement and Migration for Mobile Ed...

引用

IEEE/ACM Symposium on Edge computing (SEC)

作者： Kaustabha Ray Ansuman Banerjee Nanjangud C. Narendra Advanced Computing and Microelectronics Unit Indian Statistical Institute Ericsson Research Bangalore India

ISBN: (数字)9781728159430

ISBN: (纸本)9781728159447

In recent times, Mobile Edge computing (MEC) has emerged as a new paradigm allowing low-latency access to services deployed on edge nodes offering computation, storage and communication facilities. Vendors deploy their services on MEC servers to improve performance and mitigate network latencies often encountered in accessing cloud services. A service placement policy determines which services are deployed on which MEC servers. A number of mechanisms exist in literature to determine the optimal placement of services considering different performance metrics. However, for applications designed as microservice workflow architectures, service placement schemes need to be re-examined through a different lens owing to the inherent interdependencies which exist between microservices. Indeed, the dynamic environment, with stochastic user movement and service invocations, along with a large placement configuration space makes microservice placement in MEC a challenging task. Additionally, owing to user mobility, a placement scheme may need to be recalibrated, triggering service migrations to maintain the advantages offered by MEC. Existing microservice placement and migration schemes consider on-demand strategies. In this work, we take a different route and propose a Reinforcement Learning based proactive mechanism for microservice placement and migration. We use the San Francisco Taxi dataset to validate our approach. Experimental results show the effectiveness of our approach in comparison to other state-of-the-art methods.

关键词： Measurement Reinforcement learning Servers Task analysis Public transportation Edge computing Lenses

来源：评论

学校读者我要写书评

暂无评论

Fundamentals of IP and SoC Security 1

引用

1000年

作者： Swarup Bhunia Sandip Ray Susmita Sur-Kolay

来源：评论

学校读者我要写书评

暂无评论

Perception and Machine Intelligence 1

引用

丛书名： Lecture Notes in Computer Science

1000年

作者： Malay K. Kundu Sushmita Mitra Debasis Mazumdar Sankar K. Pal

ISBN: (数字)9783642273872

ISBN: (纸本)9783642273865

This book constitutes the proceedings of the First Indo-Japanese conference on Perception and Machine Intelligence, PerMIn 2012, held in Kolkata, India, in January 2012. The 41 papers, presented together with 1 keynote paper and 3 plenary papers, were carefully reviewed and selected for inclusion in the book. The papers are organized in topical sections named perception; human-computer interaction; e-nose and e-tongue; machine intelligence and application; image and video processing; and speech and signal processing.

关键词： Computer Science, general

来源：评论

学校读者我要写书评

暂无评论

A Verification Guided Approach for Selective Program Transformations for Approximate computing 25

A Verification Guided Approach for Selective Program Transfo...

引用

25th IEEE Asian Test Symposium, ATS 2016

作者： Mitra, Sayandeep Das, Moumita Banerjee, Ansuman Datta, Kausik Ho, Tsung-Yi Indian Statistical Institute Kolkata India Meghnad Saha Institute of Technology Kolkata India Mentor Graphics India Pvt. Ltd. India National Tsing Hua University Taiwan Advanced Computing and Microelectronics Unit Indian Statistical Institute 203 B.T. Road Kolkata West Bengal700108 India

ISBN: (纸本)9781509038084

In recent times, approximate computing is being looked at as a viable alternative for reducing the energy consumption of programs, while marginally compromising on the correctness of their computation. The idea behind approximate computing is to introduce approximations at various levels of the execution stack, with an attempt to realize the resource hungry computations on low resource consuming approximate hardware blocks. However approximate computing for program transformation faces a serious challenge of automatically identifying core program areas/statements where approximations can be introduced, with a quantifiable measure of the resulting program correctness compromise. Introducing approximations randomly can cause performance deterioration without much energy advantage, which is undesirable. In this paper, we introduce a verification-guided method to automatically identify program blocks which lend themselves to easy approximations, while not compromising significantly on program correctness. Our method is based on identifying regions of code which are less influential for the computation of the program outputs and therefore, can be compromised with, however still having a potential of significant resource reduction. We take the help of assertions to quantify the effect of the resulting transformations on program outputs. We show experimental results to support our proposal. © 2016 IEEE.

关键词： Energy utilization

来源：评论

学校读者我要写书评

暂无评论

A synoptic study on fault testing in reversible and quantum circuits 1st

A synoptic study on fault testing in reversible and quantum ...

引用

1st International Conference on Algorithms and Applications, ALAP 2018

作者： Dey, Ramyadeep Bandyopadhyay, Paramita Chandra, Somenath Majumdar, Ritajit Department of Computer Science & Engineering B. P. Poddar Institute of Management & Technology Maulana Abul Kalam Azad University of Technology Kolkata India Advanced Computing & Microelectronics Unit Indian Statistical Institute Kolkata India

ISBN: (纸本)9789811081019

Reversible computation, whose special class is quantum computation, arises from the desire to reduce power dissipation, which can be zero under ideal physical circumstances. Nowadays, error correction and fault testing are of utmost importance for the physical implementation of reversible and quantum circuits in a noisy environment. In this paper, we review various fault models in reversible and quantum circuits. In classical reversible circuits, we review (i) test pattern generation for Single Missing Gate Fault (SMGF), Partial Missing Gate Fault (PMGF), and Multiple Missing Gate Fault (MMGF) models and (ii) show that Universal Test Set (UTS) can be used to detect any of these faults. However, classical fault models do not capture all the logical failures found in quantum circuits. In quantum circuits, we review (i) depolarizing faults, initialization inaccuracy and measurement inaccuracy, and (ii) give some remedial strategies to deal with these fault models. Finally, we show that for a special class of quantum operators, detection of SMGF is sufficient to detect fault due to multiple occurrences of the gate also. Further, we argue with an example that it may not be possible to generate test patterns to detect any arbitrary SMGF in a quantum circuit. © Springer Nature Singapore Pte Ltd. 2018.

关键词： Error correction

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：