Publication Search Results

Title	Author	Bibliographic	Date	Group	Links
On Linear Characterizations of Combinatorial Optimization Problems	R. M. Karp and C.H. Papadimitriou	Proceedings of the 21st Annual IEEE Symposium on Foundations of Computer Science, Syracuse, New York, pp. 1-9	October 1980	Algorithms
Random Walks, Universal Traversal Sequences, and the Complexity of Maze Problems	R. Aleliunas, R. M. Karp, R.J. Lipton, and L. Lovasz	Proceedings of the Computer Science and Statistics 12th Annual Symposium on the Interface, Waterloo, Ontario, Canada, pp. 174-6	May 1979	Algorithms
Random Walks, Universal Traversal Sequences, and the Complexity of Maze Problems	R. Aleliunas, R. M. Karp, R.J. Lipton, L. Lovasz, and C. Rackoff	Proceedings of the 20th Annual IEEE Symposium of Foundations of Computer Science, San Juan, Puerto Rico, pp. 218-23	October 1979	Algorithms
A Patching Algorithm for the Nonsymmetric Traveling-salesman Problem	R. M. Karp	SIAM Journal on Computing, Vol. 8, No. 4, pp. 561-73	November 1979	Algorithms
Recent Advances in the Probabilistic Analysis of Graph-theoretic Algorithms	R. M. Karp, Edited by: Maurer, H.A.	Automata, Languages and Programming, Graz, Austria, Springer-Verlag, pp. 338-9	July 1979	Algorithms
Probabilistic Analysis of Graph-theoretic Algorithms	R. M. Karp	Proceedings of the Computer Science and Statistics 12th Annual Symposium on the Interface, Waterloo, Ontario, pp. 173	May 1979	Algorithms
A Characterization of the Minimum Cycle Mean in a Digraph	R. M. Karp	Discrete Mathematics (Netherlands), Vol. 23, No. 3, pp. 309-11	September 1978	Algorithms
Probabilistic Analysis of Partitioning Algorithms for the Traveling-salesman Problem in the Plane	R. M. Karp	Mathematics of Operations Research, Vol. 2, No. 3, pp. 209-24	August 1977	Algorithms
On the Optimality of Huffman Trees	R. M. Karp and C.R. Glassey	SIAM Journal on Applied Mathematics, Vol. 31, No. 2, pp. 368-78	September 1976	Algorithms
Probabilistic Behavior of a Naive Coloring Algorithm on Random Graphs	R. M. Karp and D.W. Matula	Bulletin of the Operations Research Society of America, Vol. 23, supplement 2. Also in the proceedings of the ORSA/TIMS National Meeting (Abstracts only), Las Vegas, Nevada, pp. B264	1975	Algorithms
Near-optimal Solutions to a 2-dimensional Placement Problem	R. M. Karp, A.C. McKellar, and C.K. Wong	SIAM Journal on Computing, Vol. 4, No. 3, pp. 271-86	September 1975	Algorithms
Two Special Cases of the Assignment Problem	R. M. Karp and S. Li	Discrete Mathematics (Netherlands), Vol. 13, No. 2, pp. 129-42	October 1975	Algorithms
On the Optimality of Huffman Trees	R. M. Karp and C.R. Glassey	Report number ORC-74-21, University of California, Berkeley, California	June 1974	Algorithms
On the Computational Complexity of Combinatorial Problems	R. M. Karp	Networks, Vol. 5, No.1. Also in the Proceedings of the Symposium on Large-Scale Networks, Evanston, Illinois, pp. 45-68, April 1974	January 1975	Algorithms
An n5/2 Algorithm for Maximum Matchings in Bipartite Graphs	R. M. Karp and J.E. Hopcroft	SIAM Journal on Computing, Vol. 2, No. 4, pp. 225-31	December 1973	Algorithms
Theoretical improvements in algorithmic efficiency for network flow problems	J. Edmonds and R. M. Karp	Journal of the Association for Computing Machinery, Vol. 19, No. 2, p. 248-64	April 1972	Algorithms
A Phenomenon in the Theory of Sorting	D. Gale and R. M. Karp	Journal of Computer and System Sciences, Vol. 6, No. 2, p. 103-15	April 1972	Algorithms
Inference and Analysis of Haplotypes from Combined Genotyping Studies Deposited in dbSNP	N.A. Zaitlen, H.M. Kang, M.L. Feolo, S.T. Sherry, E. Halperin, and E. Eskin	Genome Research, Vol. 15, No. 11, pp.1594-1600	October 2005	Algorithms
A Computational Model of Tractable Reasoning -- Taking Inspiration from Cognition	L. Shastri	Proceedings of the 13th International Joint Conference on Artificial Intelligence (IJCAI 93), France, pp. 202-207	1993	Algorithms
Asymmetric K-Center Is Log* N-Hard to Approximate	J. Chuzhoy, S. Guha, E. Halperin, S. Khanna, G. Kortsarz, R. Krauthgamer, and J. Naor	Journal of the ACM, Vol. 52, Issue 4, pp. 538-551	July 2005	Algorithms
The Minimum-Entropy Set Cover Problem	E. Halperin and R. M. Karp	Theoretical Computer Science, Vol. 348, Issue 2, pp. 240-250	December 2005	Algorithms
A Probabilistic Model for the Survivability of Cells	I. Adler, H-S Ahn, R. M. Karp, and S.M. Ross	Journal of Applied Probability, Vol. 42, No. 4, pp. 919-931	December 2005	Algorithms
A Note on Optimally Phasing Long Genomic Regions Using Local Haplotype Predictions	E. Eskin, E. Halperin, and R. Sharan	Journal of Bioinformatics and Computational Biology, Vol. 4, No. 3, pp. 639-647	June 2006	Algorithms
Haplofreq - Estimating Haplotype Frequencies Efficiently	E. Halperin and E. Hazan	Proceedings of the 9th Annual International Conference on Research in Computational Molecular Biology (RECOMB'05), Cambridge, Massachusetts, pp. 553-568	May 2005	Algorithms
Generalization Error Bounds Using Unlabeled Data	M. Kaariainen	Proceedings of the 18th Annual Conference on Learning Theory (COLT 2005), Bertinoro, Italy, pp. 127-142	June 2005	Algorithms
A Comparison of Tight Generalization Error Bounds	M. Kaariainen and J. Langford	Proceedings of the 22nd International Conference on Machine Learning (ICML 2005), Bonn, Germany, pp. 409-416	August 2005	Algorithms
On Active Learning in the Non-Realizable Case	M. Kaariainen	Proceedings of the Foundations of Active Learning Workshop at the 19th Annual Conference on Neural Information Processing Systems (NIPS), Vancouver, Canada	December 2005	Algorithms
Lower Bounds for Reductions	M. Kaariainen and J. Langford	Presented at the Atomic Learning Workshop, Chicago, Illinois	March 2006	Algorithms
Optimal Flow Distribution Among Multiple Channels with Unknown Capacities	R. M. Karp, T. Nierhoff, and T. Tantau	Theoretical Computer Science: Essays in Memory of Shimon Even, O. Goldreich, A. L. Rosenberg, and A. L. Selman, eds., Lecture Notes in Computer Science, Vol. 3895, pp. 111-128, Springer-Verlag	2006	Algorithms	[PDF]
Fair Bandwidth Allocation Without Per-Flow State	R. M. Karp	In Essays in Theoretical Computer Science in Memory of Shimon Even, O. Goldreich, A. L. Rosenberg, and A. L. Selman, eds., pp. 88-110, Springer	2006	Algorithms
Optimization Problems Related to Internet Congestion Control	R. M. Karp	Graph Theory, Combinatorics and Algorithms: Interdisciplinary Applications, M.C. Golumbic and I.B.-A. Hartman, eds., Springer-Verlag, New York	2005	Algorithms
George Dantzig's Impact on the Theory of Computation	R. M. Karp	Discrete Optimization, Vol. 5, Issue 2, pp. 174-185	May 2006	Algorithms
Report of the SIGACT Committee on funding for Theoretical Computer Science	R. M. Karp	SIGACT (Special Interest Group on Algorithms and Computation Theory) News	December 2005	Algorithms
A Comparison of Phasing Algorithms for Trios and Unrelated Individuals	J. Marchini, D. Cutler, N. Patterson, M. Stephens, E. Eskin, E. Halperin, S. Lin, S. Qin, G. Abecassis, H. Munro, and P. Donnelly	American Journal of Human Genetics, Vol. 78, Issue 3, pp. 437-450	March 2006	Algorithms
Active Learning Under Arbitrary Distributions	C. Monteleoni and M. Kaariainen	Poster at the Value of Information in Inference, Learning, and Decision-Making Workshop at the 19th Annual Conference on Neural Information Processing Systems (NIPS), Vancouver, Canada	December 2005	Algorithms
Knowledge Discovery for Time Series	M. Saffell	Ph.D. Thesis, OGI School of Science and Engineering, Oregon Health and Science University	September 2005	Algorithms
Efficient Algorithms for Detecting Signaling Pathways in Protein Interaction Networks	J. Scott, T. Ideker, R. M. Karp, and R. Sharan	Proceedings of the 9th Annual International Conference on Research in Computational Molecular Biology (RECOMB'05), Cambridge, Massachusetts, pp. 133-144	May 2005	Algorithms
Conserved Patterns of Protein Interaction in Multiple Species	R. Sharan, S. Sutharan, R. Kelley, T. Kuhn, S. McCuine, T.Sittler, R. Karp, and T. Ideker	Proceedings of National Academy of Science, Vol. 102, Issue 6, pp. 1974-1979	February 2005	Algorithms	[PDF]
Fixed Parameter Tractability of Binary Near-Perfect Phylogenetic Tree Reconstruction	G.E. Blelloch, K. Dhamdhere, E. Halperin, R. Ravi, R. Schwartz, and S. Sridhar	Proceedings of the 33rd International Colloquium on Automata, Languages, and Programming (ICALP 2006), Venice, Italy, pp. 667-678	July 2006	Algorithms
Leveraging the HapMap Correlation Structure in Association Studies	N. Zaitlen, H. M. Kang, E. Eskin, and E. Halperin	American Journal of Human Genetics, Vol. 80, Issue 4, pp. 683-691	April 2007	Algorithms	[PDF]
An Efficient and Accurate Graph-based Approach to Detect Population Substructure	S. Sridhar, S. Rao, and E. Halperin	Proceedings of the 11th Annual International Conference on Research in Computational Molecular Biology (RECOMB 2007), Oakland, California, pp. 503-517	April 2007	Algorithms	[PDF]
Using DNA Pools for Genotyping Trios	K.B. Beckman, K.A. Abel, A. Braun, and E. Halperin	Nucleic Acids Research, Vol. 34, No. 19, electronic article no. 129	November 2006	Algorithms	[PDF]
A Rigorous Analysis of Population Stratification with Limited Data	K. Chaudhuri, E. Halperin, S. Rao, and S. Zhou	Proceedings of ACM-SIAM Symposium on Discrete Algorithms (SODA), New Orleans, Louisiana, pp. 1046-1055	January 2007	Algorithms	[PDF]
LAMP: Local Ancestry in adMixed Populations	S. Sankararaman, S. Sridhar, G. Kimmel, and E. Halperin	American Journal of Human Genetics, Vol. 82, Issue 2, American Society of Human Genetics, pp. 290-303	February 2008	Algorithms
Polymorphisms in the Estrogen Receptor 1 and Vitamin C and Matrix Metalloproteinase Gene Families Are Associated with Susceptibility to Lymphoma	C. F. Skibola, P. M. Bracci, E. Halperin, A. Nieters, A. Hubbard, R. A. Paynter, D. R. Skibola, A. Agana, N. Becker, P. Tessler, M. S. Forrest, S. Sankararaman, L. Conde, E. A. Holly, and M. T. Smith	PLoS ONE, Vol. 3, Issue 7, e2816	June 2008	Algorithms	[PDF]
On the Inference of Ancestries in Admixed Populations	S. Sankararaman, G. Kimmel, E. Halperin and M. I. Jordan	Genome Research, Vol 18, Issue 4, pp. 668-675	April 2008	Algorithms	[PDF]
Average Update Times for Fully-Dynamic All-Pairs Shortest Paths	T. Friedrich and N. Hebbinghaus	Proceedings of International Symposium on Algorithms and Computation (ISAAC), Gold Coast, Australia, pp. 693-704	December 2008	Algorithms	[PDF]
Approximating the Volume of Unions and Intersections of High-Dimensional Geometric Objects	K. Bringmann and T. Friedrich	Proceedings of International Symposium on Algorithms and Computation (ISAAC), Gold Coast, Australia, pp. 436-447	December 2008	Algorithms	[PDF]
Computing Single Source Shortest Paths Using Single-Objective Fitness Functions	S. Baswana, S. Biswas, DB. Doerr, T. Friedrich, P. Kurur, and F. Neumann	Proceedings of the 10th Foundations of Genetic Algorithms Workshop (FOGA X), Orlando, Florida, pp. 59-66	January 2009	Algorithms	[PDF]
Quasirandom Rumor Spreading: An Experimental Analysis	B. Doerr, T. Friedrich, M. Künneman, and T. Sauerwald	Proceedings of the Workshop on Algorithm Engineering and Experiments (ALENEX09), New York, New York, pp. 145-153	January 2009	Algorithms	[PDF]

Pages