Every arrangement extends to a spread

Supported in part by NSA grant MDA904-89-H-2038, PSC-CUNY grant 662330, and the Center for Discrete Mathematics and Theoretical Computer Science (DIMACS), a National Science Foundation Science and Technology Center under NSF grant STC88-09648.     

Crossing families

Given a set of points in the plane, a crossing family is a collection of line segments, each joining two of the points, such that any two line segments intersect internally. Two setsA andB of points in the plane are mutually avoiding if no line subtended by a pair of points inA intersects the convex hull ofB, and vice versa. We show that any set ofn points in general position contains a pair of mutually avoiding subsets each of size at least . As a consequence we show that such a set possesses a crossing family of size at least , and describe a fast algorithm for finding such a family.Research supported in part by DARPA grant N00014-89-J-1988, Air Force AFOSR-89-0271, NSF grant DMS-8606225, and an ONR graduate fellowship. Further, part of this work was conducted at and supported by DIMACS (Center for Discrete Mathematics and Theoretical Computer Science), a National Science Foundation Science and Technology Center-NSF-STC8809648.     

Shortest paths algorithms: Theory and experimental evaluation

We conduct an extensive computational study of shortest paths algorithms, including some very recent algorithms. We also suggest new algorithms motivated by the experimental results and prove interesting theoretical results suggested by the experimental data. Our computational study is based on several natural problem classes which identify strengths and weaknesses of various algorithms. These problem classes and algorithm implementations form an environment for testing the performance of shortest paths algorithms. The interaction between the experimental evaluation of algorithm behavior and the theoretical analysis of algorithm performance plays an important role in our research. This work was done while Boris V. Cherkassky was visiting Stanford University Computer Science Department and supported by the NSF and Powell Foundation grants mentioned below. Andrew V. Goldberg was supported in part by ONR Young Investigator Award N00014-91-J-1855, NSF Presidential Young Investigator Grant CCR-8858097 with matching funds from AT&T, DEC, and 3M, and a grant from Powell Foundation. Corresponding author. This work was done while Tomasz Radzik was a Postdoctoral Fellow at SORIE, Cornell University, and supported by the National Science Foundation, the Air Force Office of Scientific Research, and the Office of Naval Research, through NSF grant DMS-8920550, and by the Packard Fellowship of éva Tardos.     

The Euler and Weierstrass conditions for nonsmooth variational problems

Necessary conditions are developed for a general problem in the calculus of variations in which the Lagrangian function, although finite, need not be Lipschitz continuous or convex in the velocity argument. For the first time in such a broadly nonsmooth, nonconvex setting, a full subgradient version of Euler's equation is derived for an arc that furnishes a local minimum in the classical weak sense, and the Weierstrass inequality is shown to accompany it when the arc gives a local minimum in the strong sense. The results are achieved through new techniques in nonsmooth analysis.This research was supported in part by funds from the U.S.-Israel Science Foundation under grant 90-00455, and also by the Fund for the Promotion of Research at the Technion under grant 100-954 and by the U.S. National Science Foundation under grant DMS-9200303.This article was processed by the author using the style filepljourlm from Springer-Verlag.     

Path problems in skew-symmetric graphs

We study path problems in skew-symmetric graphs. These problems generalize the standard graph reachability and shortest path problems. We establish combinatorial solvability criteria and duality relations for the skew-symmetric path problems and use them to design efficient algorithms for these problems. The algorithms presented are competitive with the fastest algorithms for the standard problems.This research was done while the first author was at Stanford University Computer Science Department, supported in part by ONR Office of Naval Research Young Investigator Award N00014-91-J-1855, NSF Presidential Young Investigator Grant CCR-8858097 with matching funds from AT&T, DEC, and 3M, and a grant from Powell Foundation.This research was done while the second author was visiting Stanford University Computer Science Department and supported by the above mentioned NSF and Powell Foundation Grants.     

Minimum steiner trees in normed planes

A minimum Steiner tree for a given setX of points is a network interconnecting the points ofX having minimum possible total length. In this note we investigate various properties of minimum Steiner trees in normed planes, i.e., where the unit disk is an arbitrary compact convex centrally symmetric domainD having nonempty interior. We show that if the boundary ofD is strictly convex and differentiable, then each edge of a full minimum Steiner tree is in one of three fixed directions. We also investigate the Steiner ratio(D) forD, and show that, for anyD, 0.623<(D)<0.8686.Part of this work was done while Ding-Zhu Du was at the Computer Science Department, Princeton University and the Center for Discrete Mathematics and Theoretical Computer Science at Rutgers. Supported by NSF under Grant STC88-09648.     

A polynomial algorithm for an integer quadratic non-separable transportation problem

We study the problem of minimizing the total weighted tardiness when scheduling unti-length jobs on a single machine, in the presence of large sets of identical jobs. Previously known algorithms, which do not exploit the set structure, are at best pseudo-polynomial, and may be prohibitively inefficient when the set sizes are large. We give a polynomial algorithm for the problem, whose number of operations is independent of the set sizes. The problem is reformulated as an integer program with a quadratic, non-separable objective and transportation constraints. Employing methods of real analysis, we prove a tight proximity result between the integer solution to that problem and a fractional solution of a related problem. The related problem is shown to be polynomially solvable, and a rounding algorithm applied to its solution gives the optimal integer solution to the original problem.Supported in part by the National Science Foundation under grant ECS-85-01988, and by the Office of Naval Research under grant N00014-88-K-0377.Supported in part by Allon Fellowship, by Air Force grants 89-0512 and 90-0008 and by DIMACS (Center for Discrete Mathematics and Theoretical Computer Science), a National Science Foundation Science and Technology Center—NSF-STC88-09648. Part of the research of this author was performed in DIMACS Center, Rutgers University.Supported in part by Air Force grant 84-0205.     

An Ω(n 4/3) lower bound on the randomized complexity of graph properties

We improve King's (n ^5/4) lower bound on the randomized decision tree complexity of monotone graph properties to (n ^4/3). The proof follows Yao's approach and improves it in a different direction from King's. At the heart of the proof are a duality argument combined with a new packing lemma for bipartite graphs.The paper was written while the author was a graduate student at the University of Chicago and was completed at M.I.T. The work was supported in part by NSF under GRANT number NSF 5-27561, the Air Force under Contract OSR-86-0076 and by DIMACS (Center for Discret Mathematics and Theoretical Computer Science), a National Science Foundation Science and Technology Center-NSF-STC88-09648.     

On packing bipartite graphs

G andH, two simple graphs, can be packed ifG is isomorphic to a subgraph of , the complement ofH. A theorem of Catlin, Spencer and Sauer gives a sufficient condition for the existence of packing in terms of the product of the maximal degrees ofG andH. We improve this theorem for bipartite graphs. Our condition involves products of a maximum degree with an average degree. Our relaxed condition still guarantees a packing of the two bipartite graphs.the paper was written while the authors were graduate students at the University of Chicago and was completed while the first author was at M.I.T. The work of the first author was supported in part by the Air Force under Contract OSR-86-0076 and by DIMACS (Center for Discrete Mathematics and Theoretical Computer Science), a National Science Foundation Science and Technology Center-NSF-STC88-09648. The work of the second author was supported in part by NSF grant CCR-8706518.     

Efficient construction of a small hitting set for combinatorial rectangles in high dimension

We describe a deterministic algorithm which, on input integersd, m and real number (0,1), produces a subset S of [m] ^d ={1,2,3,...,m} ^d that hits every combinatorial rectangle in [m] ^d of volume at least , i.e., every subset of [m] ^d the formR ₁×R ₂×...×R _d of size at least m ^d . The cardinality of S is polynomial inm(logd)/, and the time to construct it is polynomial inmd/. The construction of such sets has applications in derandomization methods based on small sample spaces for general multivalued random variables.A preliminary version of this paper appeared in Proceedings of the 25th Annual ACM Symposium on Theory of Computing, 1993.Research partially done while visiting the International Computer Science Institute. Research supported in part by a grant from the Israel-USA Binational Science Foundation.A large portion of this research was done while still at the International Computer Science Institute in Berkeley, California. Research supported in part by National Science Foundation operating grants CCR-9304722 and NCR-9416101, and United States-Israel Binational Science Foundation grant No. 92-00226.Supported in part by NSF under grants CCR-8911388 and CCR-9215293 and by AFOSR grants AFOSR-89-0512 AFOSR-90-0008, and by DIMACS, which is supported by NSF grant STC-91-19999 and by the New Jersey Commission on Science and Technology. Research partially done while visiting the International Computer Science Institute.Partially supported by NSF NYI Grant No. CCR-9457799. Most of this research was done while the author was at MIT, partially supported by an NSF Postdoctoral Fellowship. Research partially done while visiting the International Computer Science Institute.     

On component-size bounded Steiner trees

A Steiner tree is a tree interconnecting a given set of points in a metric space such that all leaves are given points. A (full) component of a Steiner tree is a subtree which results from splitting the Steiner tree at some given points. A k-size Steiner tree is a Steiner tree in which every component has at most k given points. The k-Steiner ratio is the largest lower bound for the ratio between lengths of a minimum Steiner tree and a minimum k-size Steiner tree for the same set of points. In this paper, we determine the 3-Steiner ratio in weighted graphs.     

A non-continuous “steiner point”

A new function is constructed on the space of compact, convex sets which has all the standard properties of the Steiner point except for continuity. Research supported in part by the National Science Foundation (NSF GP 19428).     

Two-letter group codes that preserve aperiodicity of inverse finite automata

We construct group codes over two letters (i.e., bases of subgroups of a two-generated free group) with special properties. Such group codes can be used for reducing algorithmic problems over large alphabets to algorithmic problems over a two-letter alphabet. Our group codes preserve aperiodicity of inverse finite automata. As an application we show that the following problems are PSpace-complete for two-letter alphabets (this was previously known for large enough finite alphabets): The intersection-emptiness problem for inverse finite automata, the aperiodicity problem for inverse finite automata, and the closure-under-radical problem for finitely generated subgroups of a free group. The membership problem for 3-generated inverse monoids is PSpace-complete. Both authors were supported in part by NSF grant DMS-9970471. The first author was also supported in part by NSF grant CCR-0310793. The second author acknowledges the support of the Excellency Center, “Group Theoretic Methods for the Study of Algebraic Varieties” of the Israeli Science Foundation.     

Identifying an optimal basis in linear programming

We propose a sufficient condition that allows an optimal basis to be identified from a central path point in a linear programming problem. This condition can be applied when there is a gap in the sorted list of slack values. Unlike previously known conditions, this condition is valid for real-number data and does not involve the number of bits in the data.This work is supported in part by the National Science Foundation, the Air Force Office of Scientific Research, and the Office of Naval Research, through NSF Grant DMS-8920550. Also supported in part by an NSF Presidential Young Investigator Award with matching funds received from AT&T and the Xerox Corporation. Part of this work was carried out while the author was visiting the Sandia National Laboratories, supported by the U.S. Department of Energy under Contract DE-AC04-76DP00789.The author is supported in part by NSF Grant DDM-9207347. Part of this work was carried out while the author was on a sabbatical leave from the University of Iowa and visiting the Cornell Theory Center, Cornell University, Ithaca, NY 14853, supported in part by the Cornell Center for Applied Mathematics and by the Advanced Computing Research Institute, a unit of the Cornell Theory Center, which receives major funding from the National Science Foundation and the IBM Corporation, with additional support from New York State and members of its Corporate Research Institute.     

Constructive lower bounds for off-diagonal Ramsey numbers

We describe an explicit construction whicy, for some fixed absolute positive constant ε, produces, for every integers>1 and all sufficiently largem, a graph on at least vertices containing neither a clique of sizes nor an independent set of sizem. Part of this work was done at the Institute for Advanced Study, Princeton, NJ 08540, USA. Research supported in part by a USA Israeli BSF grant, by a grant from the Israel Science Foundation and by the Hermann Minkowski Minerva Center for Geometry at Tel Aviv University. Research supported in part by a grant A1019901 of the Academy of Sciences of the Czech Republic and by a cooperative research grant INT-9600919/ME-103 from the NSF (USA) and the MŠMT (Czech Republic).     

On the Value of a Random Minimum Weight Steiner Tree

Consider a complete graph on n vertices with edge weights chosen randomly and independently from an exponential distribution with parameter 1. Fix k vertices and consider the minimum weight Steiner tree which contains these vertices. We prove that with high probability the weight of this tree is (1+o(1))(k-1)(log n-log k)/n when k =o(n) and n.* Research supported in part by NSF grant DSM9971788 Research supported in part by NSF grants DMS-0106589, CCR-9987845 and by the State of New Jersey. Part of this research was done while visiting IBM T. J. Watson Research Center.     

Aperiodic tilings of the hyperbolic plane by convex polygons

Several aperiodic hyperbolic tiling systems consisting of a single convex tile are constructed. Research partially supported by GIF grant no. G-454.213.06.95 and SFB 343 Bielefeld. The work of the first author was supported in part by NSF grant DMS-9424613. The work of the second author was supported in part by a grant of the Israel Academy of Sciences, and by the Edmund Landau Center for Research in Mathematical Analysis supported by the Minerva Foundation (Federal Republic of Germany).     

Computing the Detour and Spanning Ratio of Paths, Trees, and Cycles in 2D and 3D

The detour and spanning ratio of a graph G embedded in measure how well G approximates Euclidean space and the complete Euclidean graph, respectively. In this paper we describe O(nlog n) time algorithms for computing the detour and spanning ratio of a planar polygonal path. By generalizing these algorithms, we obtain O(nlog ² n)-time algorithms for computing the detour or spanning ratio of planar trees and cycles. Finally, we develop subquadratic algorithms for computing the detour and spanning ratio for paths, cycles, and trees embedded in , and show that computing the detour in is at least as hard as Hopcroft’s problem. This research was partly funded by CRM, FCAR, MITACS, and NSERC. P.A. was supported by NSF under grants CCR-00-86013 EIA-99-72879, EIA-01-31905, and CCR-02-04118, by ARO grants W911NF-04-1-0278 and DAAD19-03-1-0352, and by a grant from the U.S.-Israeli Binational Science Foundation. R.K. was supported by DFG grant Kl 655/14-1. M.S. was supported by NSF Grants CCR-97-32101 and CCR-00-98246, by a grant from the U.S.-Israeli Binational Science Foundation (jointly with P.A.), by a grant from the Israeli Academy of Sciences for a Center of Excellence in Geometric Computing at Tel Aviv University, and by the Hermann Minkowski–MINERVA Center for Geometry at Tel Aviv University. Some of these results have appeared in a preliminary form in [2, 20].     

The Essential Spectrum of Schrödinger, Jacobi, and CMV Operators

We provide a very general result which identifies the essential spectrum of broad classes of operators as exactly equal to the closure of the union of the spectra of suitable limits at infinity. Included is a new result on the essential spectra when potentials are asymptotic to isospectral tori. We also recover within a unified framework the HVZ Theorem and Krein's results on orthogonal polynomials with finite essential spectra. Supported in part by The Israel Science Foundation (grant No. 188/02). Supported in part by NSF grant DMS-01 40592. Research supported in part by grant No. 2002068 from the United States-Israel Binational Science Foundation (BSF), Jerusalem, Israel.     

Galerkin approximation for inverse problems for nonautonomous nonlinear distributed systems

We develop an abstract framework and convergence theory for Galerkin approximation for inverse problems involving the identification of nonautonomous, in general nonlinear, distributed parameter systems. We provide a set of relatively easily verified conditions which are sufficient to guarantee the existence of optimal solutions and their approximation by a sequence of solutions to a sequence of approximating finite-dimensional identification problems. Our approach is based upon the theory of monotone operators in Banach spaces and is applicable to a reasonably broad class of nonlinear distributed systems. Operator theoretic and variational techniques are used to establish a fundamental convergence result. An example involving evolution systems with dynamics described by nonstationary quasi-linear elliptic operators along with some applications and numerical results are presented and discussed.Part of this research was carried out while the first and third authors were visiting scientists at the Institute for Computer Applications in Science and Engineering (ICASE), NASA Langley Research Center. Hampton, VA, which is operated under NASA Contracts NAS1-17070 and NAS1-18107. Also, a portion of this research was carried out with computational resources made available through a grant to the second and third authors from the San Diego Supercomputer Center operated for the National Science Foundation by General Atomics, San Diego, CA. The research of the first author was supported in part under Grants NSF MCS-8504316, NASA NAG-1-517, AFOSR-84-0398, and AFOSR-F49620-86-C-0111. The second author's research was supported in part by the Fund for the Promotion of Research at the Technion and by the Technion VPR Fund. The research of the third author was supported in part under Grants AFOSR-84-0393 and AFOSR-87-0356.