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

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

来源：评论

学校读者我要写书评

暂无评论

Dilution with digital microfluidic biochips: How unbalanced splits corrupt target-concentration

arXiv

引用

arXiv 2019年

作者： Poddar, Sudip Wille, Robert Rahaman, Hafizur Bhattacharya, Bhargab B. Advanced Computing and Microelectronics Unit Indian Statistical Institute Kolkata700108 India Department of Computer Science & Engineering Indian Institute of Technology Kharagpur721 302 India Indian Statistical Institute Kolkata700108 India School of VLSI Technology Indian Institute of Engineering Science and Technology Shibpur711103 India Institute for Integrated Circuits Johannes Kepler University Linz Austria

Sample preparation is an indispensable component of almost all biochemical protocols, and it involves, among others, making dilutions and mixtures of fluids in certain ratios. Recent microfluidic technologies offer suitable platforms for automating dilutions on-chip, and typically on a digital microfluidic biochip (DMFB), a sequence of (1: 1) mix-split operations is performed on fluid droplets to achieve the target concentration factor (CF) of a sample. An (1: 1) mixing model ideally comprises mixing of two unit-volume droplets followed by a (balanced) splitting into two unit-volume daughter-droplets. However, a major source of error in fluidic operations is due to unbalanced splitting, where two unequal-volume droplets are produced following a split. Such volumetric split-errors occurring in different mix-split steps of the reaction path often cause a significant drift in the target-CF of the sample, the precision of which cannot be compromised in life-critical assays. In order to circumvent this problem, several error-recovery or error-tolerant techniques have been proposed recently for DMFBs. Unfortunately, the impact of such fluidic errors on a target-CF and the dynamics of their behavior have not yet been rigorously analyzed. In this work, we investigate the effect of multiple volumetric split-errors on various target-CFs during sample preparation. We also perform a detailed analysis of the worst-case scenario, i.e., the condition when the error in a target-CF is maximized. This analysis may lead to the development of new techniques for error-tolerant sample preparation with DMFBs without using any sensing operation. Copyright © 2019, The Authors. All rights reserved.

关键词： Digital microfluidics

来源：评论

学校读者我要写书评

暂无评论

Surface Code Design for Asymmetric Error Channels

arXiv

引用

arXiv 2021年

作者： Azad, Utkarsh Lipińska, Aleksandra Mahato, Shilpa Sachdeva, Rijul Bhoumik, Debasmita Majumdar, Ritajit Center for Computational Natural Sciences and Bioinformatics International Institute of Information Technology Hyderabad India Center for Quantum Science and Technology International Institute of Information Technology Hyderabad India Xanadu TorontoONM5G 2C8 Canada Faculty of Mathematics and Computer Science Jagiellonian University Kraków Poland Department of Physics Indian Institute of Technology Dhanbad India Jülich Supercomputing Center Forschungszentrum Jülich Germany RWTH Aachen University Germany Advanced Computing & Microelectronics Unit Indian Statistical Institute Kolkata India

Surface codes are quantum error correcting codes typically defined on 2D array of qubits. In this paper, a [dx,dz] surface code design is being introduced, where dx(dz) represents the distance of the code for bit (phase) error correction, motivated by the fact that the severity of bit flip and phase flip errors in the physical quantum system is asymmetric. We present pseudo-threshold and threshold values for the proposed surface code design for asymmetric error channels in the presence of various degrees of asymmetry of Pauli Xˆ, Ŷ, and Ẑ errors in a depolarization channel. We demonstrate that compared to symmetric surface codes, our asymmetric surface codes can provide almost double the pseudo-threshold rates while requiring less than half the number of physical qubits in the presence of increasing asymmetry in the error channel. Our results show that for low degree of asymmetry, it is advantageous to increase dx along with dz. However, as the asymmetry of the channel increases, higher pseudo-threshold is obtained with increasing dz when dx is kept constant at a low value. Additionally, we also show that the advantage in the pseudo-threshold rates begins to saturate for any possible degree of asymmetry in the error channel as the surface code asymmetry is continued to increase. © 2021, CC BY-NC-ND.

关键词： Error correction

来源：评论

学校读者我要写书评

暂无评论

25th Annual Computational Neuroscience Meeting CNS-2016, Seogwipo City, South Korea, July 2-7, 2016 Abstracts

引用

BMC NEUROSCIENCE 2016年第Sup1期17卷 54-54页

作者： [Anonymous] Computational Neurobiology Laboratory The Salk Institute for Biological Studies San Diego CA USA UNIC CNRS Gif sur Yvette France The European Institute for Theoretical Neuroscience (EITN) Paris France ATR Computational Neuroscience Laboratories 2-2 Hikaridai Seika-cho Soraku-gun Kyoto 619-0288 Japan Krembil Research Institute University Health Network Toronto ON M5T 2S8 Canada Department of Physiology University of Toronto Toronto ON M5S 1A8 Canada Department of Medicine (Neurology) University of Toronto Toronto ON M5T 2S8 Canada Department of Neurophysiology Nencki Institute of Experimental Biology Warsaw Poland Department of Theory Wigner Research Centre for Physics of the Hungarian Academy of Sciences Budapest 1121 Hungary Department of Mathematical Sciences KAIST Daejoen 34141 Republic of Korea Department of Mathematics University of Houston Houston TX 77004 USA Department of Biochemistry & Cell Biology and Institute of Biosciences and Bioengineering Rice University Houston TX 77005 USA Department of Biology and Biochemistry University of Houston Houston TX 77004 USA Grupo de Neurocomputación Biológica Dpto. de Ingeniería Informática Escuela Politécnica Superior Universidad Autónoma de Madrid Madrid Spain Department of Biological Sciences University of Southern California Los Angeles CA USA Center for Neuroscience Korea Institute of Science and Technology Hwarang-ro 14-gil 5 Seongbuk-gu Seoul 02792 South Korea Department of Neuroscience University of Science and Technology 217 Gajeong-ro Yuseong-gu Daejon 34113 South Korea Department of Psychology Yonsei University 50 Yonsei-ro Seodaemun-gu Seoul 03722 South Korea Department of Psychiatry Kyung Hee University Hospital at Gangdong 892 Dongnam-ro Gangdong-gu Seoul 05278 South Korea Department of Psychiatry Veterans Administration Boston Healthcare System and Harvard Medical School Brockton MA 02301 USA Center for Neural Science New York University New York NY 10003 USA Courant Institute

A1 Functional advantages of cell-type heterogeneity in neural circuits Tatyana O. Sharpee A2 Mesoscopic modeling of propagating waves in visual cortex Alain Destexhe A3 Dynamics and biomarkers of mental disorders Mitsuo Kawato F1 Precise recruitment of spiking output at theta frequencies requires dendritic h-channels in multi-compartment models of oriens-lacunosum/moleculare hippocampal interneurons Vladislav Sekulić, Frances K. Skinner F2 Kernel methods in reconstruction of current sources from extracellular potentials for single cells and the whole brains Daniel K. Wójcik, Chaitanya Chintaluri, Dorottya Cserpán, Zoltán Somogyvári F3 The synchronized periods depend on intracellular transcriptional repression mechanisms in circadian clocks. Jae Kyoung Kim, Zachary P. Kilpatrick, Matthew R. Bennett, Kresimir Josić O1 Assessing irregularity and coordination of spiking-bursting rhythms in central pattern generators Irene Elices, David Arroyo, Rafael Levi, Francisco B. Rodriguez, Pablo Varona O2 Regulation of top-down processing by cortically-projecting parvalbumin positive neurons in basal forebrain Eunjin Hwang, Bowon Kim, Hio-Been Han, Tae Kim, James T. McKenna, Ritchie E. Brown, Robert W. McCarley, Jee Hyun Choi O3 Modeling auditory stream segregation, build-up and bistability James Rankin, Pamela Osborn Popp, John Rinzel O4 Strong competition between tonotopic neural ensembles explains pitch-related dynamics of auditory cortex evoked fields Alejandro Tabas, André Rupp, Emili Balaguer-Ballester O5 A simple model of retinal response to multi-electrode stimulation Matias I. Maturana, David B. Grayden, Shaun L. Cloherty, Tatiana Kameneva, Michael R. Ibbotson, Hamish Meffin O6 Noise correlations in V4 area correlate with behavioral performance in visual discrimination task Veronika Koren, Timm Lochmann, Valentin Dragoi, Klaus Obermayer O7 Input-location dependent gain modulation in cerebellar nucleus neurons Maria Psarrou, Maria Schilstra, Neil Davey, Benjamin Torben-Ni

关键词： NEUROSCIENCES PATHOLOGICAL psychology DENDRITES

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：