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

Full matching in an observational study of coaching for the SAT

JOURNAL OF THE AMERICAN STATISTICAL ASSOCIATION 2004年第467期99卷 609-618页

作者： Hansen, BB Univ Michigan Dept Stat Ann Arbor MI 48109 USA

Among matching techniques for observational studies, full matching is in principle the best, in the sense that its alignment of comparable treated and control subjects is as good as that of any alternate method, and potentially much better. This article evaluates the practical performance of full matching for the first time, modifying it in order to minimize variance as well as bias and then using it to compare coached and uncoached takers of the SAT. In this new version, with restrictions on the ratio of treated subjects to controls within matched sets, full matching makes use of many more observations than does pair matching, but achieves far closer matches than does matching with k greater than or equal to 2 controls. Prior to matching, the coached and uncoached groups are separated on the propensity score by 1.1 SDs. Full matching reduces this separation to 1% or 2% of an SD. In older literature comparing matching and regression, Cochran expressed doubts that ani method of adjustment could substantially reduce observed bias of this magnitude. To accommodate missing data, regression-based analyses by ETS researchers rejected a subset of the available sample that differed significantly from the subsample they analyzed. Full matching on the propensity score handles the same problem simply and without rejecting observations. In addition, it eases the detection and handling of nonconstancy of treatment effects, which the regression-based analyses had obscured, and it makes fuller use of covariate information. It estimates a somewhat larger effect of coaching on the math score than did ETS's methods.

关键词： graph algorithm matching with multiple controls network flow optimal matching quasiexperiment propensity score

来源：评论

学校读者我要写书评

暂无评论

On the approximation of the generalized capacitated tree-routing problem

引用

JOURNAL OF DISCRETE algorithmS 2010年第3期8卷 311-320页

作者： Morsy, Ehab Nagamochi, Hiroshi Kyoto Univ Yoshida Honmachi Grad Sch Informat Dept Appl Math & Phys Kyoto 6068501 Japan Suez Canal Univ Fac Sci Dept Math Ismailia 22541 Egypt

In this paper, we study the generalized capacitated tree-routing problem (GCTR), which was introduced to unify the several known multicast problems in networks with edge/demand capacities. Let G = (V, E) be a connected underlying graph with a bulk edge capacity lambda > 0 and an edge weight w(e) >= 0, e is an element of E;we are allowed to construct a network on G by installing any edge capacity k(e)lambda with an integer ke >= 0 for each edge e is an element of E, where the resulting network costs Sigma e is an element of (E) k(e)w(e). Given a sink s is an element of V, a set M subset of V of terminals with a demand q(V) >= 0, V is an element of M and a demand capacity. > 0, we wish to construct the minimum cost network so that all the demands can be sent to s along a suitable collection T = {T1, T2,..., T p} of trees rooted at s, where the total demand collected by each tree Ti is bounded from above by., and the flow amount f (e) of T that goes through each edge e is bounded from above by the edge capacity ke lambda. In this paper, f (e) is defined as Sigma Ti is an element of T: e is an element of Ti-[ (alpha +) (beta qTi (e)]) for prescribed constants alpha, beta >= 0, where qTi (e) denotes the total demand that passes through the edge e along Ti. The term a means a fixed amount used to establish the routing Ti by separating the inside of Ti from the outside while the term alpha qTi (e) means the net capacity proportional to the demand qTi (e). The objective of GCTR is to construct a minimum cost network that admits a collection T of trees to send all demand to sink. It was left open to show whether GCTR with lambda< alpha+ beta k. is approximable by a constant factor or not. In this paper, we present a 13.037-approximation algorithm to GCTR for this case. (C) 2009 Elsevier B. V. All rights reserved.

关键词： Approximation algorithm graph algorithm Routing problems Network optimization Tree cover

来源：评论

学校读者我要写书评

暂无评论

Matchtigs: minimum plain text representation of k-mer sets

引用

GENOME BIOLOGY 2023年第1期24卷 1页

作者： Schmidt, Sebastian Khan, Shahbaz Alanko, Jarno N. Pibiri, Giulio E. Tomescu, Alexandru I. Univ Helsinki Dept Comp Sci Helsinki Finland Indian Inst Technol Roorkee Dept Comp Sci & Engn Roorkee India Dalhousie Univ Fac Comp Sci Halifax NS Canada Ca Foscari Univ Venice Dept Environm Sci Informat & Stat Venice Italy ISTI CNR Pisa Italy

We propose a polynomial algorithm computing a minimum plain-text representation of k-mer sets, as well as an efficient near-minimum greedy heuristic. When compressing read sets of large model organisms or bacterial pangenomes, with only a minor runtime increase, we shrink the representation by up to 59% over unitigs and 26% over previous work. Additionally, the number of strings is decreased by up to 97% over unitigs and 90% over previous work. Finally, a small representation has advantages in downstream applications, as it speeds up SSHash-Lite queries by up to 4.26x over unitigs and 2.10x over previous work.

关键词： k-mer sets Plain text compression graph algorithm Sequence analysis Genomic sequences Minimum-cost flow Chinese postman problem

来源：评论

学校读者我要写书评

暂无评论

Protein-fold recognition using an improved single-source K diverse shortest paths algorithm

引用

PROTEINS-STRUCTURE FUNCTION AND BIOINFORMATICS 2016年第4期84卷 467-472页

作者： Lhota, John Xie, Lei CUNY Hunter Coll Grad Ctr Dept Comp Sci New York NY USA CUNY Hunter Coll Dept Comp Sci 695 Pk Ave New York NY 10065 USA

Protein structure prediction, when construed as a fold recognition problem, is one of the most important applications of similarity search in bioinformatics. A new protein-fold recognition method is reported which combines a single-source K diverse shortest path (SSKDSP) algorithm with Enrichment of Network Topological Similarity (ENTS) algorithm to search a graphic feature space generated using sequence similarity and structural similarity metrics. A modified, more efficient SSKDSP algorithm is developed to improve the performance of graph searching. The new implementation of the SSKDSP algorithm empirically requires 82% less memory and 61% less time than the current implementation, allowing for the analysis of larger, denser graphs. Furthermore, the statistical significance of fold ranking generated from SSKDSP is assessed using ENTS. The reported ENTS-SSKDSP algorithm outperforms original ENTS that uses random walk with restart for the graph search as well as other state-of-the-art protein structure prediction algorithms HHSearch and Sparks-X, as evaluated by a benchmark of 600 query proteins. The reported methods may easily be extended to other similarity search problems in bioinformatics and chemoinformatics. The SSKDSP software is available at . Proteins 2016;84:467-472. (c) 2016 Wiley Periodicals, Inc.

关键词： similarity search structure prediction graph algorithm ENTS structural bioinformatics

来源：评论

学校读者我要写书评

暂无评论

Traversal with Enumeration of Geometric graphs in Bounded Space

引用

JOURNAL OF INTERCONNECTION NETWORKS 2019年第4期19卷

作者： Khakabimamaghani, Sahand Masjoody, Masood Stacho, Ladislav Simon Fraser Univ Dept Comp Sci 8888 Univ Dr Burnaby BC V5A 1S6 Canada Simon Fraser Univ Dept Math 8888 Univ Dr Burnaby BC V5A 1S6 Canada

In this paper, we provide an algorithm for traversing geometric graphs which visits all vertices and reports every vertex and edge exactly once. To achieve this, we combine a given geometric graph G with the integer lattice, seen as a graph, in such a way that the resulting hypothetical graph can be traversed using a known algorithm which is based on face routing. To overcome the problem with hypothetical vertices and edges, we develop an algorithm for visiting any k-th neighborhood of a vertex in a graph straight-line drawn in the plane using O(k log k) memory. The memory needed to complete the traversal of a geometric graph then turns out to depend on the maximum graph distance among pairs of distinct vertices of G whose Euclidean distance is greater than one and less than 2 root 2.

关键词： graph algorithm traversal geometric graph quasi-planar subdivision

来源：评论

学校读者我要写书评

暂无评论

Simpler multicoloring of triangle-free hexagonal graphs

引用

DISCRETE MATHEMATICS 2012年第1期312卷 181-187页

作者： Sau, Ignasi Sparl, Petra Zerovnik, Janez Univ Ljubljana FS Ljubljana 1000 Slovenia CNRS LIRMM F-34095 Montpellier 5 France Univ Maribor FOV SI-4000 Kranj Slovenia IMFM Ljubljana Slovenia

Given a graph G and a demand function p: V(G) -> N, a proper n-[p]coloring is a mapping f : V(G) -> 2([1.....n]) such that vertical bar f (v)vertical bar >= p(v) for every vertex v epsilon V(G) and f(v) boolean AND f(u) = emptyset for any two adjacent vertices u and v. The least integer n for which a proper n-[p]coloring exists, chi(p)(G), is called multichrornatic number of G. Finding multichromatic number of induced subgraphs of the triangular lattice (called hexagonal graphs) has applications in cellular networks. Weighted clique number of a graph G, omega(p)(G), is the maximum weight of a clique in G, where the weight of a clique is the total demand of its vertices. McDiarmid and Reed (2000) [8] conjectured that chi(p)(G) <= (9/8)omega(p)(G) + C for triangle-free hexagonal graphs, where C is some absolute constant. In this article, we provide an algorithm to find a 7-[3]coloring of triangle-free hexagonal graphs (that is, when p(v) = 3 for all v epsilon V (G)), which implies that chi(p)(G) <= (7/6)omega(p)(G) + C. Our result constitutes a shorter alternative to the inductive proof of Havet (2001) [5] and improves the short proof of Sudeep and Vishwanathan (2005) [17], who proved the existence of a 14-[6]coloring. (It has to be noted, however, that our proof makes use of the 4-color theorem.) All steps of our algorithm take time linear in vertical bar V(G)vertical bar, except for the 4-coloring of an auxiliary planar graph. The new techniques may shed some light on the conjecture of McDiarmid and Reed (2000) [8]. (C) 2011 Elsevier B.V. All rights reserved.

关键词： graph algorithm Approximation algorithm graph coloring Frequency planning Cellular networks

来源：评论

学校读者我要写书评

暂无评论

The complexity of the Clar number problem and an exact algorithm

引用

JOURNAL OF MATHEMATICAL CHEMISTRY 2018年第2期56卷 597-605页

作者： Berczi-Kovacs, Erika R. Bernath, Attila Eotvos Lorand Univ Dept Operat Res Pazmany Peter Setany 1-C H-1117 Budapest Hungary Eotvos Lorand Univ MTA ELTE Egervary Res Grp Dept Operat Res Pazmany Peter Setany 1-C H-1117 Budapest Hungary

The Clar number of a (hydro)carbon molecule, introduced by Clar (The aromatic sextet, 1972), is the maximum number of mutually disjoint resonant hexagons in the molecule. Calculating the Clar number can be formulated as an optimization problem on 2-connected plane graphs. Namely, it is the maximum number of mutually disjoint even faces a perfect matching can simultaneously alternate on. It was proved by Abeledo and Atkinson (Linear Algebra Appl 420(2):441-448, 2007) that the Clar number can be computed in polynomial time if the plane graph has even faces only. We prove that calculating the Clar number in general 2-connected plane graphs is -hard. We also prove -hardness of the maximum independent set problem for 2-connected plane graphs with odd faces only, which may be of independent interest. Finally, we give an exact algorithm that determines the Clar number of a given 2-connected plane graph. The algorithm has a polynomial running time if the length of the shortest odd join in the planar dual graph is fixed, which gives an efficient algorithm for some fullerene classes, such as carbon nanotubes.

关键词： Clar number Fullerene Carbon nanotubes Complexity Planar graph graph algorithm

来源：评论

学校读者我要写书评

暂无评论

A HYBRID algorithm FOR THE SHORTEST-PATH BETWEEN 2 NODES IN THE PRESENCE OF FEW NEGATIVE ARCS

引用

INFORMATION PROCESSING LETTERS 1983年第4期16卷 181-182页

作者： YAP, CK Courant Institute of Mathematical Sciences New York University New York NY 10012 U.S.A.

来源：评论

学校读者我要写书评

暂无评论

SENSITIVITY ANALYSIS OF MINIMUM SPANNING-TREES AND SHORTEST-PATH TREES

引用

INFORMATION PROCESSING LETTERS 1982年第1期14卷 30-33页

作者： TARJAN, RE Bell Laboratories Murray Hill NJ 07974 U.S.A.

The minimum spanning tree problem consists of determining for a connected and undirected graph a spanning tree of minimal total edge cost. The sensitivity analysis problem involves a determination of the extent to which each edge cost can be perturbed individually without upsetting the minimality of the subgraph. Sensitivity analysis also can be applied to the shortest path tree problem. This problem requires computing for a given directed graph and a given vertex a spanning tree rooted at the vertex and containing a minimum-cost path from the vertex to every other vertex. algorithms are presented for performing sensitivity analysis of minimum spanning trees and shortest path trees. The algorithms involve the use of an auxiliary graph called a transmuter. Figures.

关键词： Sensitivity analysis shortest path minimum spanning tree path compression graph algorithm network optimization transmuter

来源：评论

学校读者我要写书评

暂无评论

Approximation algorithms for Steiner Connected Dominating Set

引用

Journal of Computer Science & Technology 2005年第5期20卷 713-716页

作者： Ya-Feng Wu Yin-Long Xu Guo-Liang Chen National High Performance Computing Center at Hefei Department of Computer Science and Technology University of Science and Technology of China Hefei 230027 P.R. China

Steiner connected dominating set （SCDS） is a generalization of the famous connected dominating set problem, where only a specified set of required vertices has to be dominated by a connected dominating set, and known to be NP- hard. This paper firstly modifies the SCDS algorithm of Guha and Khuller and achieves a worst case approximation ratio of （2 ＋ 1/（m - 1））H（min（△, k））＋O（1）, which outperforms the previous best result （c ＋ 1）H（min（△, k））＋ O（1） in the case of m ≥ 1 ＋1/（c - 1）, where c is the best approximation ratio for Steiner tree, A is the maximum degree of the graph, k is the cardinality of the set of required vertices, m is an optional integer satisfying 0 ≤ m ≤ min（△, k） and H is the harmonic function. This paper also proposes another approximation algorithm which is based on a greedy approach. The second algorithm can establish a worst case approximation ratio of 2 ln（min（△, k））＋ O（1）, which can also be improved to 2 lnk if the optimal solution is greater than c·e^2c＋1/2（c＋1）.

关键词： approximation algorithm Steiner connected dominated set graph algorithm NP-hard

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：