DIMACS Technical Reports Published in 1995

Obtaining Reports

Problems with Technical Reports?

• 95-01 (abstract) Analysis of approximate algorithms for constrained and unconstrained edge-coloring of bipartite graphs R. Jain, J. Werth
• 95-02 (abstract) An Exact Dualigy Theory for Semidefinite Programming and it's Complexity Implications Motakuri Ramana
• 95-03 (abstract) Parallel Best-First Branch-and-Bound in Discrete Optimization Ricardo Correa and Afonso Ferreira
• 95-04 (abstract) DNA Sequence Classification Using Compression-Based Induction D. Lowenstern, H. Hirsh, M. Noordiwier, P. Yianilos
• 95-05 (abstract) Finding Cuts in the TSP (A preliminary report) D. Applegate, R. Bixby, V. Chvatal, B. Cook
• 95-06 (abstract) Relation between Protein Structure, Sequence Homology and Composition of Amino Acids I. Dubchack, E. Mayoraz, and I. Muchnik.
• 95-07 (abstract) Directed Rectangle-Visibility Graphs have Unbounded Dimension K. Romanik
• 95-08 (abstract) Optimization under Ordinal Scales: When is a Greedy Solution Optimal? Aleksandar Pekec
• 95-09 (abstract) Computationally Manageable Combinatorial Auctions Michael H. Rothkopf, Aleksandar Pekec, Ronald M. Harstad
• 95-10 (abstract) A Winning Strategy for the Ramsey Graph Game Aleksandar Pekec
• 95-11 (abstract) Airdisks and AirRAID: Modeling and scheduling periodic wireless data broadcast Ravi Jain, John Werth
• 95-12 (abstract) Equivalence between sorting and priority queues Mikkel Thorup
• 95-13 (abstract) Approximate Minimum-cost Multicommodity Flows in $\tilde 0(\eps^{-2}KNM)$ Time Michael D. Grigoriadis and L.G. Khachiyan
• 95-14 (abstract) Resolution Search Vasek Chvatal
• 95-15 (abstract) LINK: A Combinatorics and Graph Theory Workbench for Applications and Research Jon Berry, Nathaniel Dean, Patricia Fasel, Mark Goldberg, Elizabeth Johnson, John MacCuish, Gregory Shannon, Steven Skiena
• 95-16 (abstract) Bipartite Steinhaus Graphs Bhaskar DasGupta, Martin Furer
• 95-17 (abstract) Sample Complexity for Learning Recurrent Perceptron Mappings Bhaskar DasGupta, Eduardo Sontag
• 95-18 (abstract) Sorting with Fixed-Length Reversals Ting Chen and Steven S. Skiena
• 95-19 (abstract) Positional Sequencing by Hybridization Sridhar Hannenhalli, Pavel A. Pevzner, Herbert F. Lewis, Steven S. Skiena
• 95-20 (abstract) Single Machine Scheduling with Earliness and Tardiness Penalties: When is an Optimal Solution Not Optimal? N.V.R. Mahadev, A. Pekec, F.S. Roberts
• 95-21 (abstract) A Game-Theoretic Classification of Interactive Complexity Classes Joan Feigenbaum, Daphne Koller, Peter Shor
• 95-22 (abstract) The Use of Coding Theory in Computational Complexity Joan Feigenbaum
• 95-23 (abstract) Balanced Graphs and Network Flows Stephen Penrice
• 95-24 (abstract) Clique-like Dominating Sets Stephen Penrice
• 95-25 (abstract) Coloring with Defects Lenore Cowen, Esther Jesurum
• 95-26 (abstract) Defective Coloring of Toroidal Graphs and Graphs of Bounded Genus Lenore Cowen, Wayne Goddard
• 95-27 (abstract) A Formal Framework for Evaluating Heuristic Programs Lenore Cowen, Joan Feigenbaum, Sampath Kannan
• 95-28 (abstract) A Biologically Meaningful Model for Comparing Molecular Phylogenies Boris Mirkin, Ilya Muchnik, Temple F. Smith
• 95-29 (abstract) Some New Graph Labeling Problems: A Preliminary Report Stephen Penrice
• 95-30 (abstract) Algorithms for matrix groups and the Tits alternative Robert Beals
• 95-31 (abstract) Improved construction of negation-limited circuits Robert Beals
• 95-32 (abstract) Multiplicative equations over commuting matrices L. Babai, R. Beals, J-y. Cai, G. Ivanyos, E.M. Luks
• 95-33 (abstract) Algorithms for Polycyclic-by-finite Matrix Groups: Preliminary Report Gretchen Ostheimer
• 95-34 (abstract) Path Optimization for Graph Partitioning Problems Jonathan W. Berry, Mark K. Goldberg
• 95-35 (abstract) Constructive Training Methods for Feedforward Neural Networks with Binary Weights Eddy Mayoraz, Frederic Aviolat
• 95-36 (abstract) Nonoverlapping Local Alignments, Weighted Independent Sets of Axis Parallel Rectangles Vineet Bafna, Babu Narayanan, R. Ravi
• 95-37 (abstract) Improved Approximation Guarantees for Packing and Covering Integer Programs by Aravind Srinivasan
• 95-38 (abstract) Covering Polygonal Regions with Affine Images (Paper only.) Kiran B. Chilakamarri, Nathaniel Dean, Henry R. Gee
• 95-39 (abstract) On the Power of Democratic Networks (Paper only.) Eddy Mayoraz
• 95-40 (abstract) Localizing a Robot with Minimum Travel G. Rudek, K. Romanik, S. Whitesides
• 95-41 (abstract) A semidefinite bound for mixing rates of Markov chains Nabil Kahale
• 95-42 (abstract) Geometric Probing and Testing - A Survey Kathleen Romanik
• 95-43 (abstract) Steiner Minimal Trees in Simple Polygons Pawel Winter
• 95-44 (abstract) Monotone Linkage Clustering and Quasi-Convex Set Functions Yulia Kempner, Boris Mirkin
• 95-45 (abstract) On Point Covers of Multiple Intervals and Axis-Parallel Rectangles Gyula Karolyi, Gabor Tardos
• 95-46 (abstract) On the Approximability of Numerical Taxonomy... Richa Agarwala, Vineet bafna, Martin Farach, Babu Narayanan, Michael Patterson, Mikkel Thorup
• 95-47 (abstract) Higher Dimensional Representations of Graphs and Cover page Andreas Buja, Nathaniel Dean, Michael L. Littman, Deborah Swayne
• 95-48 (abstract) Proceedings of Phylogeny Workshop Simon Tavare, Host
• 95-49 (abstract) Ramsey-Type Results for Geometric Graphs Gyula Karolyi, Janos Pach, Geza Toth
• 95-50 (abstract) Zero one laws for graphs with edge probabilities decaying with distance Saharon Shelah
• 95-51 (abstract) Finite Canonization Saharon Shelah
• 95-52 (abstract) In the random Graph G(n,p),p=n^{-\alpha}: If \psi has probability O(n^{-\epsilon}) for every \epsilon>0, then it has probability O(e^{-n^{\epsilon}}) for some \epsilon>0 Saharon Shelah
• 95-53 (abstract) Very weak zero one law for random graphs with order and random binary functions Saharon Shelah
• 95-54 (abstract) On a Metric Generalization of Ramsey's Theorem Pal Erdos, Andras Hajnal, Janos Pach
• 95-55 (abstract) Asymptotically Good Covers in Hypergraphs: Extended Abstract of the Dissertation P. Mark Kayll
• 95-56 (abstract) Relational expressive power of local generic queries Oleg V. Belegradek, Alexei P. Stolboushkin, and Michael A. Taitslin

Return to Tech Reports Page

DIMACS Homepage