DIMACS Technical Reports Published in 1993

Obtaining Reports

Problems with Technical Reports?

• 93-01 Abstract: A Randomized Algorithm for Finding Maximum with O((log n)^2) Polynomial Tests Hing F. Ting and Andrew C. Yao
• 93-02 Abstract: Projective Orientations of MatroidsI. M. Gelfand, G. Rybnikov and D. Stone
• 93-03 Abstract: k-Neighborhood Covering and Independence Problems Shiow-Fen Hwang and Gerard J. Chang
• 93-04 Abstract: A Polynomial-time Algorithm for the Phylogeny Problem When the Number of Character States is Fixed R. Agarwala and D. Fernandez-Baca
• 93-05 Abstract: Monotone Gray Codes and the Middle Levels Problem Carla D. Savage and Peter Winkler
• 93-06 Abstract: Optimal Compression of Propositional Horn Knowledge Bases: Complexity and Approximation Peter L. Hammer and Alexander Kogan
• 93-07 Abstract: On Computing Algebraic Functions Using Logarithms and Exponentials Dima Grigoriev, Michael Singer, and Andrew Yao
• 93-08 Abstract: Hilbert Series of Group Representations and Grobner Bases for Generic Modules Shmuel Onn
• 93-09 Abstract: Asymptotic Results for Permutation Groups (Abstract only; please order paper copy.) Laszlo Pyber
• 93-10 Abstract: Probabilistically Checkable Debate Systems and Approximation Algorithms for PSPACE-Hard Functions Anne Condon, Joan Feigenbaum, Carsten Lund, Peter Shor
• 93-11 Abstract: The L(2,1)-Labeling Problem on Graphs Gerard J. Chang and David Kuo
• 93-12 Abstract: A Tight Bound for Edge Guards in Rectilinear Monotone Polygons Iliana Bjorling-Sachs
• 93-13 Abstract: Combinatorial Optimization and Computations in the Ring of Polynomials Alexander I. Barvinok
• 93-14 Abstract: Testing Simple Polygons Esther M. Arkin, Patrice Belleville, Joseph S.B. Mitchell, David Mount, Kathleen Romanik, Steven Salzberg, Diane L. Souvaine
• 93-15 Abstract: Enumerating Consecutive and Nested Partitions for Graphs G. J. Chang and F. K. Hwang
• 93-16 Abstract: Confluently Persistent Deques via Data-Structural Bootstrapping A. L. Buchsbaum and R. E. Tarjan
• 93-17 Abstract: On the Structure of Co-Critical Graphs Anna Galluccio, Miklos Simonovits, Gabor Simonyi
• 93-18 Abstract: Convex Relaxations of 0-1 Quadratic Programming Svatopluk Poljak and Henry Wolkowicz
• 93-19 Abstract: Indefinite Trust Region Subproblems and Nonsymmetric Eigenvalue Perturbations Ronald J. Stern and Henry Wolkowicz
• 93-20 Abstract: A First-Order Isomorphism Theorem Eric Allender, Jose Balcazar, and Neil Immerman
• 93-21 Abstract: Dept Reduction for Noncommutative Arithmetic Circuits Eric Allender and Jia Jiao
• 93-22 Abstract: A Robust Model for Finding Optimal Evolutionary Trees Martin Farach, Sampath Kannan, and Tandy Warnow
• 93-23 Abstract: Consecutive Cuts and Paths, and Bounds on k-Terminal Reliability Heidi J. Strayer and Charles J. Colbourn
• 93-24 Abstract: Weighted Independent Perfect Domination on Cocomparability Graphs Gerard J. Chang, C. Pandu Rangan and Satyan R. Coorg
• 93-25 Abstract: The Russian Option: Reduced Regret Larry Shepp and A. N. Shiryaev
• 93-26 Abstract: A Dual Russian Option for Selling Short Larry Shepp and A. N. Shiryaev
• 93-27 Abstract: Non-Stanley Bounds for Network Reliability Jason I. Brown and Charles J. Colbourn
• 93-28 Abstract: Some Open Problems on Reliability Polynomials Charles J. Colbourn
• 93-29 Abstract: Combinatorial Optimization: A Survey Martin Grotschel and Laszlo Lovasz
• 93-30 Abstract: Lazy Structure Sharing for Query Optimization Adam L. Buchsbaum, Rajamani Sundar and Robert E. Tarjan
• 93-31 Abstract: Constructing Language Instances Based on Partial Information Laura A. Sanchis
• 93-32 Abstract: Research Problems in Discrete Geometry: Packing and Covering (Abstract only; please order paper copy.) William Moser and Janos Pach
• 93-33 Abstract: Inverse Theorems in Additive Number Theory Melvyn B. Nathanson
• 93-34 Abstract: Trust Regions and the Quadratic Assignment Problem (Abstract only, please order paper copy.) Stefan E. Karisch, Franz Rendl, and Henry Wolkowicz
• 93-35 Abstract: Entropy Splitting Hypergraphs Gabor Simonyi
• 93-36 Abstract: Workshop on Parallel Algorithms for Unstructured & Dynamic Problems Bill Aiello, Albert G. Greenberg, Andrew Ogielski
• 93-37 Abstract: Quasi-Acyclic Propositional Horn Knowledge Bases: Optimal Compression Peter L. Hammer and Alexander Kogan
• 93-38 Abstract: Parallel Processing of Discrete Optimization Problems Grama Y. Ananth, Vipin Kumar, and Panos M. Pardalos
• 93-39 Abstract: The Simplex Algorithm with a New Primal and Dual Pivot Rule Hsin-Der Chen, Panos M. Pardalos, and Michael A. Saunders
• 93-40 Abstract: On Lattice-Free Polytopes Michel Deza and Shmuel Onn
• 93-41 Abstract: On Edge Bijections of Graphs A. K. Kelmans
• 93-42 Abstract: On a Covering Property of Maximal Sperner Families Peter L. Erdos and Niall Graham
• 93-43 Abstract: Relationships Among PL, #L, and the Determinant Eric Allender and Mitsunori Ogiwara
• 93-44 Abstract: Half-integral Flows in a Planar Graph With Four Holes (Abstract only; please order paper copy.) Alexander V. Karzanov
• 93-45 Abstract: An Efficient Algorithm for Dynamic Text Indexing Ming Gu, Martin Farach and Richard Beigel
• 93-46 Abstract: Fast Comparison of Evolutionary Trees Martin Farach and Mikkel Thorup
• 93-47 Abstract: A New Approach to the Construction of Optimal Designs R.H. Hardin and N.J.A. Sloane
• 93-48 Abstract: Covering Arrays and Intersecting Codes N.J.A. Sloane
• 93-49 Abstract: The Nordstrom-Robinson Code is the Binary Image of the Octacode G. David Forney, Jr., N.J.A. Sloane and Mitchell D. Trott
• 93-50 Abstract: A Linear Construction for Certain Kerdock and Preparata Codes A.R. Calderbank, A.R. Hammons, Jr., and P. Vijay Kumar
• 93-51 Abstract: Operating Manual for Gosset: A General-Purpose Program for Constructing Experimental Designs (Second Edition) R.H. Hardin and N.J.A. Sloane
• 93-52 Abstract: The Z sub 4-Linearity of Kerdock, Preparata, Goethals and Related Codes A.R. Hammons, Jr., P. Vijay Kumar, A.R. Calderbank, N.J.A. Sloane, and Patrick Sole
• 93-53 Abstract: Quaternary Constructions for the Binary Single-Error-Correcting Codes of Julin, Best and Others J.H. Conway and N.J.A. Sloane
• 93-54 Abstract: Expressing (a sup 2 + b sup 2 + c sup 2 + d sup 2) sup 3 as a Sum of 23 Sixth Powers R.H. Hardin and N.J.A. Sloane
• 93-55 Abstract: D sub 4, E sub 8, Leech and Certain Other Lattices are Symplectic J.H. Conway and N.J.A. Sloane
• 93-56 Abstract: A Pedestrian Approach to Ray Shooting: Shoot a Ray, Take a Walk John Hershberger and Subhash Suri
• 93-57 Abstract: Finding a Shortest Diagonal of a Simple Polygon in Linear Time John Hershberger and Subhash Suri
• 93-58 Abstract: Matrix Searching with the Shortest Path Metric John Hershberger and Subhash Suri
• 93-59 Abstract: Can Visibility Graphs Be Represented Compactly? Pankaj K. Agarwal, Noga Alon, Boris Aronov, Subhash Suri
• 93-60 Abstract: Shortcutting Planar Digraphs and (second part of this paper in postscript) Mikkel Thorup
• 93-61 Abstract: Controlled Grammatic Ambiguity First Part, Second Part, and Third Part. Mikkel Thorup
• 93-62 Abstract: Minors and the Chromatic Index of r-graphs K. Kilakos and B. Shepherd
• 93-63 Abstract: A Note on a Conjecture of Toft T. R. Jensen and F. B. Shepherd
• 93-64 Abstract: On Enumeration of Near to Best Solutions in Discrete and Dynamic Programming Joseph V. Romanovsky
• 93-65 Abstract: Instance-Hiding Proof Systems D. Beaver, J. Feigenbaum, R. Ostrovsky, and V. Shoup
• 93-66 Abstract: The Least Possible Value at Zero of Some Nonnegative Cosine Polynomials Szilard Gy. Revesz
• 93-67 Abstract: Approximation Clustering for Homogeneous Data Tables (Abstract only; please order paper copy.) Boris Mirkin
• 93-68 Abstract: Generalization of the Tetrad Representation Theorem Glenn Shafer, Alexander Kogan and Peter Spirtes
• 93-69 Abstract: Some Experimental and Theoretical Results on Test Case Generators for the Maximum Clique Problem Laura A. Sanchis and Arun Jagota
• 93-70 Abstract: Eigenvalues and Expansion of Regular Graphs Nabil Kahale
• 93-71 Abstract: A Randomized Linear-Time Algorithm for Finding Minimum Spanning Philip N. Klein and Robert E. Tarjan
• 93-72 Abstract: Symmetric Quasi-Definite Matrices Robert J. Vanderbei
• 93-73 Abstract: Affine-Scaling Trajectories Associated with a Semi-Infinite Linear Program Robert J. Vanderbei
• 93-74 Abstract: Brownian Bandits Avi Mandelbaum and Robert J. Vanderbei
• 93-75 Abstract: Interior-Point Methods for Max-Min Eigenvalue Problems Franz Rendl, Robert J. Vanderbei, and Henry Wolkowicz
• 93-76 Abstract: Bipartite Dimensions and Bipartite Degrees of Graphs Peter C. Fishburn and Peter L. Hammer
• 93-77 Abstract: An Analog of Freiman's Theorem in Groups Imre Z. Ruzsa
• 93-78 Abstract: On Reducing the Cut Ratio to the Multicut Problem Nabil Kahale
• 93-79 Abstract: Random Debaters and the Hardness of Approximating Stochastic Functions Anne Condon, Joan Feigenbaum, Carsten Lund and Peter Shor
• 93-80 Abstract: On Sums With Small Prime Factors (Abstract only; Please order paper copy.) Gabor Sarkozy
• 93-81 Abstract: Fast Parallel Algorithms or Finding Hamiltonian Cycles and Trees in Graphs (Abstract only; Please order paper copy.) Gabor Sarkozy
• 93-82 Abstract: A Geometric Approach for Denoting and Intersecting TR Subgroups of the Euclidean Group Yanxi Liu
• 93-83 Abstract: Isoperimetric Inequalities and Eigenvalues Nabil Kahale
• 93-84 Abstract: Notes on the Kolakoski Sequence Vasek Chvatal
• 93-85 Abstract: On the Diameter of the Symmetric Traveling Salesman Polytope (Abstract only; Please order paper copy.) Fred J. Rispoli
• 93-87 Abstract: Workshop on Models, Architectures, and Technologies for Parallel Computation (Abstract only. Please order paper copy.) P.B. Gibbons, R.M. Karp, C.E. Leiserson, G.M. Papadopoulos
• 93-88 Abstract: On Lattices Equivalent to Their Duals J. H. Conway and N.J.A. Sloane
• 93-89 Abstract: Optimization Methods for Computing Global Minima of Nonconvex Potential Energy Functions Panos M. Pardalos, David Shalloway, and Guoliang Xue
• 93-90 Abstract: Workshop on Parallel Algorithms: From Solving Combinatorial Problems to Solving Grand Challenge Problems (Abstract only. Please order paper copy.) James Flanagan, Yossi Matias, and Vijaya Ramachandran
• 93-91 Abstract: Balancing Updates vs Queries for the Partial Sum Problem (Abstract only. Please order paper copy.) Haripriyan Hampapuram and Michael L. Fredman
• 93-92 Abstract: DIMACS Annual Report
• 93-93 Abstract: On the Very Weak 0-1 Law for Random Graphs With Orders Saharon Shelah

Return to Tech Reports Page

DIMACS Homepage