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

randomized approximation algorithms for set multicover problems with applications to reverse engineering of protein and gene networks

引用

DISCRETE APPLIED MATHEMATICS 2007年第6-7期155卷 733-749页

作者： Berman, Piotr DasGupta, Bhaskar Sontag, Eduardo Penn State Univ Dept Comp Sci & Engn University Pk PA 16802 USA Univ Illinois Dept Comp Sci Chicago IL 60607 USA Rutgers State Univ Dept Math New Brunswick NJ 08903 USA

In this paper we investigate the computational complexity of a combinatorial problem that arises in the reverse engineering of protein and gene networks. Our contributions are as follows: We abstract a combinatorial version of the problem and observe that this is "equivalent" to the set multicover problem when the "coverage" factor k is a function of the number of elements it of the universe. An important special case for our application is the case in which k = n - 1. We observe that the standard greedy algorithm produces an approximation ratio of Omega(log n) even if k is "large" i.e k = n - c for some constant c > 0. Let 1 < a < n denote the maximum number of elements in any given set in our set multicover problem. Then, we show that a non-trivial analysis of a simple randomized polynomial-time approximation algorithm for this problem yields an expected approximation ratio E vertical bar r(a, k)vertical bar that is an increasing function of a/k. The behavior of E vertical bar r(a, k)vertical bar is roughly as follows: it is about In(a/k) when a/k is at least about e(2) approximate to 7.39, and for smaller values of a/k it decreases towards 1 as a linear function of root a/k with lim(a/k -> 0) E vertical bar r(a, k)vertical bar = 1. Our randomized algorithm is a cascade of a deterministic and a randomized rounding step parameterized by a quantity beta followed by a greedy solution for the remaining problem. We also comment about the impossibility of a significantly faster convergence of E vertical bar r(a, k)vertical bar towards 1 for any polynomial-time approximation algorithm. (c) 2006 Elsevier B.V. All rights reserved.

关键词： set multicover randomized approximation algorithms reverse engineering biological networks

来源：评论

学校读者我要写书评

暂无评论

randomized approximation algorithms for set multicover problems with applications to reverse engineering of protein and gene networks

Randomized approximation algorithms for set multicover probl...

引用

7th International Workshop on approximation algorithms for Combinatorial Optimization Problems/8th International Workshop on Randomization and Computation

ISBN: (纸本)3540228942

关键词： set multicover randomized approximation algorithms reverse engineering biological networks

来源：评论

学校读者我要写书评

暂无评论

Triangle Counting in Dynamic Graph Streams

引用

ALGORITHMICA 2016年第1期76卷 259-278页

作者： Bulteau, Laurent Froese, Vincent Kutzkov, Konstantin Pagh, Rasmus Tech Univ Berlin Berlin Germany NEC Labs Europe Heidelberg Germany IT Univ Copenhagen Copenhagen Denmark Univ Lyon 1 Inria LBBE Lyon France

Estimating the number of triangles in graph streams using a limited amount of memory has become a popular topic in the last decade. Different variations of the problem have been studied, depending on whether the graph edges are provided in an arbitrary order or as incidence lists. However, with a few exceptions, the algorithms have considered insert-only streams. We present a new algorithm estimating the number of triangles in dynamic graph streams where edges can be both inserted and deleted. We show that our algorithm achieves better time and space complexity than previous solutions for various graph classes, for example sparse graphs with a relatively small number of triangles. Also, for graphs with constant transitivity coefficient, a common situation in real graphs, this is the first algorithm achieving constant processing time per edge. The result is achieved by a novel approach combining sampling of vertex triples and sparsification of the input graph. In the course of the analysis of the algorithm we present a lower bound on the number of pairwise independent 2-paths in general graphs which might be of independent interest. At the end of the paper we discuss lower bounds on the space complexity of triangle counting algorithms that make no assumptions on the structure of the graph.

关键词： randomized approximation algorithms Streaming algorithms Triangle counting

来源：评论

学校读者我要写书评

暂无评论

Distributed algorithms for Constructing Approximate Minimum Spanning Trees in Wireless Sensor Networks

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 2009年第1期20卷 124-139页

作者： Khan, Maleq Pandurangan, Gopal Kumar, V. S. Anil Virginia Tech Virginia Bioinformat Inst Network Dynam & Simulat Sci Lab Blacksburg VA 24061 USA Purdue Univ Dept Comp Sci W Lafayette IN 47907 USA

While there are distributed algorithms for the minimum spanning tree (MST) problem, these algorithms require relatively large number of messages and time, and are fairly involved, making them impractical for resource-constrained networks such as wireless sensor networks. In such networks, a sensor has very limited power, and any algorithm needs to be simple, local, and energy efficient. Motivated by these considerations, we design and analyze a class of simple and local distributed algorithms called Nearest Neighbor Tree (NNT) algorithms for energy-efficient construction of an approximate MST in wireless networks. Assuming that the nodes are uniformly distributed, we show provable bounds on both the quality of the spanning tree produced and the energy needed to construct them. We show that while NNT produces a close approximation to the MST, it consumes asymptotically less energy than the classical message-optimal distributed MST algorithm due to Gallagery, Humblet, and Spira. Further, the NNTs can be maintained dynamically with polylogarithmic rearrangements under node insertions/deletions. We also perform extensive simulations, which show that the bounds are much better in practice. Our results, to the best of our knowledge, demonstrate the first tradeoff between the quality of approximation and the energy required for building spanning trees on wireless networks, and motivate similar considerations for other important problems.

关键词： Distributed algorithms randomized approximation algorithms energy-efficient algorithms minimum spanning tree wireless networks sensor networks

来源：评论

学校读者我要写书评

暂无评论

randomized priority algorithms

引用

THEORETICAL COMPUTER SCIENCE 2010年第26-28期411卷 2542-2558页

作者： Angelopoulos, Spyros Borodin, Allan Max Planck Inst Comp Sci D-66123 Saarbrucken Germany Univ Toronto Dept Comp Sci Toronto ON M5S 3G4 Canada

Borodin, Nielsen and Rackoff [13] introduced the class of priority algorithms as a framework for modeling deterministic greedy-like algorithms. In this paper we address the effect of randomization in greedy-like algorithms. More specifically, we consider approximation ratios within the context of randomized priority algorithms. As case studies, we prove inapproximation results for two well-studied optimization problems, namely facility location and makespan scheduling. (C) 2010 Elsevier B.V. All rights reserved.

关键词： Greedy algorithms randomized approximation algorithms Facility location Makespan scheduling

来源：评论

学校读者我要写书评

暂无评论

Probabilistic verification and approximation

引用

ANNALS OF PURE AND APPLIED LOGIC 2008年第1-3期152卷 122-131页

作者： Lassaigne, Richard Peyronneta, Sylvain Univ Paris 07 CNRS UMR 7056 Equipe Logique F-75221 Paris 05 France Ecole Polytech LIX Lab Informat Paris France

We study the existence of efficient approximation methods to verify quantitative specifications of probabilistic systems. Models of such systems are labelled discrete time Markov chains and checking specifications consists of computing satisfaction probabilities of linear temporal logic formulas. We prove that, in general, there is no polynomial time randomized approximation scheme with relative error for probabilistic verification. However, in many applications, specifications can be expressed by monotone formulas or negation of monotone formulas and randomized approximation schemes with absolute error are sufficient. We show how some simple randomized approximation algorithms can improve the efficiency of verification of such probabilistic specifications and can be implemented in a probabilistic model checker. (c) 2007 Elsevier B.V. All rights reserved.

关键词： probabilistic verification randomized approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Algorithmic issues in reverse engineering of protein and gene networks via the modular response analysis method

引用

REVERSE ENGINEERING BIOLOGICAL NETWORKS: OPPORTUNITIES AND CHALLENGES IN COMPUTATIONAL METHODS FOR PATHWAY INFERENCE 2007年第1期1115卷 132-141页

作者： Berman, Piotr Dasgupta, Bhaskar Sontag, Eduardo Univ Illinois Dept Comp Sci MC 152 Chicago IL 60607 USA Penn State Univ Dept Comp Sci & Engn University Pk PA 16802 USA Rutgers State Univ Dept Math New Brunswick NJ 08903 USA

This paper studies a computational problem motivated by the modular response analysis method for reverse engineering of protein and gene networks. This set-cover problem is hard to solve exactly for large networks, bu... 详细信息

关键词： reverse engineering biological networks set multicover randomized approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

STRIP: Stream Learning of Influence Probabilities 13

STRIP: Stream Learning of Influence Probabilities

引用

19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD)

作者： Kutzkov, Konstantin Bifet, Albert Bonchi, Francesco Gionis, Aristides IT Univ Copenhagen Copenhagen Denmark Yahoo Res Barcelona Spain Aalto Univ Espoo Finland Aalto Univ Espoo Finland

ISBN: (纸本)9781450321747

Influence-driven diffusion of information is a fundamental process in social networks. Learning the latent variables of such process, i.e., the influence strength along each link, is a central question towards understanding the structure and function of complex networks, modeling information cascades, and developing applications such as viral marketing. Motivated by modern microblogging platforms, such as twitter, in this paper we study the problem of learning influence probabilities in a data-stream scenario, in which the network topology is relatively stable and the challenge of a learning algorithm is to keep up with a continuous stream of tweets using a small amount of time and memory. Our contribution is a number of randomized approximation algorithms, categorized according to the available space (superlinear, linear, and sublinear in the number of nodes n) and according to different models (landmark and sliding window). Among several results, we show that we can learn influence probabilities with one pass over the data, using O(n log n) space, in both the landmark model and the sliding-window model, and we further show that our algorithm is within a logarithmic factor of optimal. For truly large graphs, when one needs to operate with sublinear space, we show that we can still learn influence probabilities in one pass, assuming that we restrict our attention to the most active users. Our thorough experimental evaluation on large social graph demonstrates that the empirical performance of our algorithms agrees with that predicted by the theory.

关键词： Social network analysis Social Influence Streaming randomized approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Maximizing the effectiveness of a pediatric vaccine formulary while prohibiting extraimmunization

引用

HEALTH CARE MANAGEMENT SCIENCE 2008年第4期11卷 339-352页

作者： Hall, Shane N. Sewell, Edward C. Jacobson, Sheldon H. USAF Inst Technol Dept Operat Sci Wright Patterson AFB OH 45433 USA So Illinois Univ Dept Math & Stat Edwardsville IL 62026 USA Univ Illinois Dept Comp Sci Simulat & Optimizat Lab Urbana IL 61801 USA

The growing complexity of the United States Recommended Childhood Immunization Schedule has resulted in as many as five required injections during a single well-baby office visit. To reduce this number, vaccine manufacturers have developed combination vaccines that immunize against several diseases in a single injection. At the same time, a growing number of parents are challenging the safety and effectiveness of vaccinating children. They are also particularly concerned about the use of combination vaccines, since they believe that injecting a child with multiple antigens simultaneously may overwhelm a child's immune system. Moreover, combination vaccines make it more likely that extraimmunization (i.e., administering more than the required amount of vaccine antigens) occurs, resulting in greater concerns by parents and vaccine wastage costs borne by an already strained healthcare system. This paper formulates an integer programming model that solves for the maximum number of vaccines that can be administered without any extraimmunization. An exact dynamic programming algorithm and a randomized heuristic for the integer programming model is formulated and the heuristic is shown to be a randomized xi-approximation algorithm. Computational results are reported on three sets of test problems, based on existing and future childhood immunization schedules, to demonstrate their computational effectiveness and limitations. Given that future childhood immunization schedules may need to be solved for each child, on a case-by-case basis, the results reported here may provide a practical and valuable tool for the public health community.

关键词： Pediatric immunization Pediatric vaccines randomized approximation algorithms Discrete optimization Dynamic programming Heuristics Integer programming

来源：评论

学校读者我要写书评

暂无评论

Approximating average parameters of graphs

引用

RANDOM STRUCTURES & algorithms 2008年第4期32卷 473-493页

作者： Goldreich, Oded Ron, Dana Tel Aviv Univ Dept EE Syst Ramat Aviv Israel Weizmann Inst Sci Dept Comp Sci IL-76100 Rehovot Israel

Inspired by Feige (36th STOC, 2004), we initiate a study of sublinear randomized algorithms for approximating average parameters of a graph. Specifically, we consider the average degree of a graph and the average distance between pairs of vertices in a graph. Since our focus is on sublinear algorithms, these algorithms access the input graph via queries to an adequate oracle. We consider two types of queries. The first type is standard neighborhood queries (i.e., what is the ith neighbor of vertex v?), whereas the second type are queries regarding the quantities that we need to find the average of (i.e., what is the degree of vertex v? and what is the distance between u and v?, respectively). Loosely speaking, our results indicate a difference between the two problems: For approximating the average degree, the standard neighbor queries suffice and in fact are preferable to degree queries. In contrast, for approximating average distances, the standard neighbor queries are of little help whereas distance queries are crucial. (c) 2008 Wiley Periodicals, Inc.

关键词： sublinear-time algorithms randomized approximation algorithms Wiener Index

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：