DIMACS Technical Reports Published in 1990

Obtaining Reports

More recent technical reports are available on-line and we encourage downloading from WWW browsers or FTP. Reports that are not available may be ordered by email to tech@dimacs.rutgers.edu. Be sure to include the numbers of the reports needed and your full Postal Address.

Problems with Technical Reports?

We try to check on the accessibility of technical reports regularly, but mistakes do happen. If you have trouble obtaining reports, please send email to tech@dimacs.rutgers.edu identifying the report you had trouble with. We will try to assist you in obtaining the report.

90-1 A Primal Dual Path Following Algorithm for Linear Programming with Box Type Constraints Kaplan & Shamir
90-2 A Polynomial Algorithm for an Integer Quadratic Nonseparable Transportation Problem Hochbaum, Shamir & Shanthikumar
90-3 A Colored Version of Tverberg's Theorem Barany & Larman
90-4 Self Knowledgeable Inference Machines Cerans & Smith
90-5 A Role of Lower Semicontinuous Functions in the Combinatorial Complexity of Geometric Problems Jaromczyk & Swiatek
90-6 The Optimal Constant for the Colored Version Jaromczyk & Swiatek
90-7 Cutting Hyperplane Arrangement Jiri Matousek
90-8 Minkowski Addition of Polytopes: Computational Complexity and Applications to Grobner Bases Gritzmann & Sturmfels
90-9 Points and Triangles in the Plane and Halving Planes in Space Aronov, Chazelle, Edelsbrunner, Guibas, Sharir & Wenger
90-10 Repeated Angles in the Plane and Related Problems Pach & Sharir
90-11 Gaps in Difference Sets, and the Graph of Nearly Equal Distances Erdos, Makai, Pach, & Spencer
90-12 An Upper Bound on the Number of Planar k-Set Pach, Steiger & Szemeredi
90-13 Output-Sensitive Methods for Rectilinear Hidden Surface Removal Goodrich, Atallah, Overmars
90-14 The Matching Extendability of Surfaces Dean
90-15 Midpoints of Diagonals of Convex n-gons Erdos, Fishburn, Furedi
90-16 Regular Triangulations of Convex Polytopes Lee
90-17 Hamiltonian Simple Polytopes Prabhu
90-18 Sensitivity vs. Block Sensitivity of Boolean Functions Kenyon
90-19 Allowing Overlaps Makes Switchbox Layouts Nice Kaufmann
90-20 Selecting Distances in the Plane Agarwal, Aronov, Sharir, Suri
90-21 Fat Triangles Determine Linearly Many Holes Matousek, Sharir, Pach, Sifrony, Welzl
90-22 Diagonal Matrix Scaling and Linear Programming Khachiyan, Kalantari
90-23 On Packing Bipartite Graphs Hajnal, Szegedy
90-24 Davenport-Schinzel Theory of Matrices Furedi, Hajnal
90-25 Multi-level Permission Csirmaz
90-26 Intersection Queries in Sets of Disks Kreveld, Overmars, Agarwal
90-27 Efficient Algorithms for Minimum Cost Flow Problems with Convex Costs Pinton, Shamir
90-28 Induction and Peano Model Csirmaz
90-29 T X Preprocessor Csirmaz
90-30 A Turan-Type Theorem on Chords of a Convex Polygon Capoyleas, Pach
90-31 Workshop on Computer-Aided Verification Kurshan, Clarke
90-32 On Strong Separation from AC Allender, Gore
90-33 On Topological Questions of Real Complexity Theory and Combinatorial Optimization Vershik
90-34 Winding Numbers and the Generalized Lower-Bound Conjecture Lee
90-35 On Shift Stable Hypergraphs Boros
90-36 Chvatal Cuts and Odd Cycle Inequalities in Quadratic 0 - 1 Optimization Boros, Crama, Hammer
90-37 Cut-Polytopes, Boolean Quadric Polytopes and Nonnegative Quadratic Pseudo-Boolean Functions Boros, Hammer
90-38 Counting Facets and Incidences Agarwal, Aronov
90-39 Computational Results with a Cutting Plane Algorithm for Designing Communication Networks with Low-Connectivity Constraints Grotschel, Monma, Stoer
90-40 Facets for Polyhedra Arising in the Design of Communication Networks with Low-Connectivity Constraints Grotschel, Monma, Stoer
90-41 DIMACS Workshop on Distributed Computing and Cryptography Feigenbaum & Merritt
90-42 No-Hole 2-Distant Colorings Roberts
90-43 Balancing Rooted Data Flow Graphs Boros, Hammer, Shamir
90-44 A Still Better Performance Guarantee for Approximate Graph Coloring Halldorsson
90-45 On the Perimeter of a Point Set in the Plane Capoyleas, Pach
90-46 The Number of Edges of Many Faces in a Line Segment Arrangement Aronov, Edelsbrunner, Guibas, Sharir
90-47 Meaningfulness of Conclusions about Greedy Algorithms for T-Colorings Cozzens, Roberts
90-48 Do Projections go to Infinity? Barany, Goodman, Pollack
90-49 Counting Linear Extensions is #P-Complete Brightwell, Winkler
90-50 Geometric Permutations and Connected Components Wenger
90-51 Elementary Sequences, Sub-Fibonacci Sequences Fishburn, Roberts
90-52 On a Problem of Erdos and Lovasz Kahn
90-53 Coloring Nearly-Disjoint Hypergraphs with n+o(n) Colors Kahn
90-54 Euclidean Minimum Spanning Trees and Bichromatic Closest Pairs Agarwal, Edelsbrunner, Schwarzkopf, Welzl
90-55 Shortest Paths Help Solve Geometric Optimization Melissaratos, Souvaine
90-56 Circle Shooting in a Simple Polygon Agarwal, Sharir
90-57 Coloring Mixed Graphs Hansen, Kuplinsky, de Werra
90-58 Planar Geometric Location Problems Agarwal, Sharir
90-59 Complexity of Polytope Volume Computation Khachiyan
90-60 On the Conductance of Order Markov Chains Karzanov, Khachiyan
90-61 Circular Visibility in a Simple Polygon from a Point Agarwal, Sharir
90-62 Competitive Group Testing Du, Hwang
90-63 Construction of Multidimensional Spanner Graphs, with Applications to Minimum Spanning Trees Salowe
90-64 Off-Line Dynamic Maintenance of the Width of a Planar Point Set Agarwal, Sharir
90-65 Meeting Times for Random Walks on Graphs Tetali, Winkler
90-66 Characterizations of the Plurality Function Roberts
90-67 A Partially Ordered Set of Functionals Corresponding to Graphs Sidorenko
90-68 Neural Networks via Linear Programming and Convexity Poljak
90-69 On the Complexity of Nonnegative Matrix Scaling Kalantari, Khachiyan
90-70 DIMACS Annual Report
90-71 Monge and Feasibility Sequences in General Flow Problems Adler, Hoffman, Shamir
90-72 A Proof of Gilbert-Pollak's Conjecture on the Steiner Ratio Du, Hwang
90-73 Sigma-Phi-Sigma Threshold Formulas Radhakrishnan
90-74 Improved Bounds for Covering Complete Uniform Hypergraphs Radhakrishnan
90-75 Fully Persistent Lists with Catenation Driscoll, Sleator, Tarjan
90-76 Fast Algorithms on Graphs and Trees Booth
90-77 Lattices with Few Distances Conway, Sloane
90-78 Randomized vs. Deterministic Decision Tree Complexity for Read-Once Boolean Functions Heiman, Wigderson
90-79 Depth Reduction for Circuits of Unbounded Fan-In Allender, Hertrampf
90-80 How to Time-Stamp a Digital Document Habe, Stornetta
90-81 Relating Equivalence and Reducibility to Sparse Sets Allender, Hemachandra, Ogiwara, Watanabe
90-82 Rosen's Gradient Projection Method and Slope Lemmas Du

Return to Tech Reports Page

DIMACS Homepage

Report problems concerning Technical Reports to: tech@dimacs.rutgers.edu

Contacting the Center
Document last modified on January 15, 1998.