Volume Distortion for Subsets of Euclidean Spaces

In Rao (Proceedings of the 15th Annual Symposium on Computational Geometry, pp. 300–306, 1999), it is shown that every n-point Euclidean metric with polynomial aspect ratio admits a Euclidean embedding with k-dimensional distortion bounded by , a result which is tight for constant values of k. We show that this holds without any assumption on the aspect ratio and give an improved bound of . Our main result is an upper bound of independent of the value of k, nearly resolving the main open questions of Dunagan and Vempala (Randomization, Approximation, and Combinatorial Optimization, pp. 229–240, 2001) and Krauthgamer et al. (Discrete Comput. Geom. 31(3):339–356, 2004). The best previous bound was O(log n), and our bound is nearly tight, as even the two-dimensional volume distortion of an n-vertex path is . This research was done while the author was a postdoctoral fellow at the Institute for Advanced Study, Princeton, NJ.     

A PTAS for the sparsest 2-spanner of 4-connected planar triangulations

A t-spanner of an undirected, unweighted graph G is a spanning subgraph of G with the added property that for every pair of vertices in G, the distance between them in is at most t times the distance between them in G. We are interested in finding a sparsest t-spanner, i.e., a t-spanner with the minimum number of edges. In the general setting, this problem is known to be NP-hard for all t2. For t5, the problem remains NP-hard for planar graphs, whereas for t{2,3,4}, the complexity of this problem on planar graphs is still unknown. In this paper we present a polynomial time approximation scheme for the problem of finding a sparsest 2-spanner of a 4-connected planar triangulation.     

Generalized Hausdorff dimension distortion in Euclidean spaces under Sobolev mappings

We investigate how the integrability of the derivatives of Orlicz-Sobolev mappings defined on open subsets of Rn affect the sizes of the images of sets of Hausdorff dimension less than n. We measure the sizes of the image sets in terms of generalized Hausdorff measures.     

Laplacian eigenvalues and the maximum cut problem

We introduce and study an eigenvalue upper bound(G) on the maximum cut mc (G) of a weighted graph. The function(G) has several interesting properties that resemble the behaviour of mc (G). The following results are presented.We show that is subadditive with respect to amalgam, and additive with respect to disjoint sum and 1-sum. We prove that(G) is never worse that 1.131 mc(G) for a planar, or more generally, a weakly bipartite graph with nonnegative edge weights. We give a dual characterization of(G), and show that(G) is computable in polynomial time with an arbitrary precision.The research has been partially done when the second author visited LRI in September 1989.     

Bi-Lipschitz Embeddings of Trees into Euclidean Buildings

Let be the affine Bruhat-Tits (or Euclidean) building associated to a semisimple, simply connected linear algebraic group defined over a non-Archimedean local field. We prove that there exist locally finite trees of degree 3 which are bi-Lipschitz embedded in . As a consequence such a Euclidean building cannot be bi-Lipschitz embedded into a Hilbert space.     

Empirical Euclidean likelihood for general estimating equations under association dependence

Empirical Euclidean likelihood for general estimating equations for association dependent processes is investigated. The strong consistency and asymptotic normality of the blockwise maximum empirical Euclidean likelihood estimator are presented. We show that it is more efficient than estimator without blocking. The blockwise empirical Euclidean log-likelihood ratio asymptotically follows a chi-square distribution.     

Euclidean algorithms are Gaussian

We obtain a central limit theorem for a general class of additive parameters (costs, observables) associated to three standard Euclidean algorithms, with optimal speed of convergence. We also provide very precise asymptotic estimates and error terms for the mean and variance of such parameters. For costs that are lattice (including the number of steps), we go further and establish a local limit theorem, with optimal speed of convergence. We view an algorithm as a dynamical system restricted to rational inputs, and combine tools imported from dynamics, such as transfer operators, with various other techniques: Dirichlet series, Perron's formula, quasi-powers theorems, and the saddle-point method. Such dynamical analyses had previously been used to perform the average-case analysis of algorithms. For the present (dynamical) analysis in distribution, we require estimates on transfer operators when a parameter varies along vertical lines in the complex plane. To prove them, we adapt techniques introduced recently by Dolgopyat in the context of continuous-time dynamics (Ann. Math. 147 (1998) 357).     

Testing the diameter of graphs

We propose a general model for testing graph properties, which extends and simplifies the bounded degree model of Goldreich and Ron [Property Testing in Bounded Degree Graphs, Proc. 31st Annual ACM Symposium on the Theory of Computing, 1997, pp. 406–415.] In this model, we present a family of algorithms that test whether the diameter of a graph is bounded by a given parameter D, or is ?‐far from any graph with diameter at most β(D). The function β(D) ranges between D+4 and 4D+2, depending on the algorithm. All our algorithms run in time polynomial in 1/?. © 2002 Wiley Periodicals, Inc. Random Struct. Alg. 20: 165–183, 2002     

A note on the precedence-constrained class sequencing problem

We give a short proof of a result of Tovey [Non-approximability of precedence-constrained sequencing to minimize setups, Discrete Appl. Math. 134:351-360, 2004] on the inapproximability of a scheduling problem known as precedence-constrained class sequencing. In addition, we present an approximation algorithm with performance guarantee (c+1)/2, where c is the number of colors. This improves upon Tovey's c-approximation.     

带机器准备时间的平行机在线与半在线排序

本文研究带机器准备时间的m台平行机系统在线和半在线排序问题.对在线排序问题,我们证明了LS算法的最坏情况界为2-1/m.对已知工件加工时间递减,已知总加工时间和已知工件最大加工时间三个半在线模型,我们分析了它们的下界和所给算法的最坏情况界.对其中两台机情形均得到了最好近似算怯。     

The Pythagorean theorem and the Euclidean parallel postulate

In this note, we develop new, simple and very accurate asymptotic approximations for non-integer order derivatives of monomial functions by using the more accurate asymptotic approximations for large factorials that have recently appeared in the literature.     

几种特殊结构全光网中多播路由的波长分配算法

研究全光WDM网络中多播请求的路由与波长分配问题.给定网络拓扑和一组多播通信请求,要求对其进行路由和波长分配,满足波长连续性和波长无冲突约束,使得所用的波长总数最少.就几类特殊网络进行了研究.首先对二分树网络进行了研究,此时问题是多项式时间可求解的.其次对树网络进行了讨论,证明了即使是星网络,问题也不存在近似比小于m1/2-ρ(0＜ρ＜1))的近似算法,除非NP=ZPP,这里m是星图的边数.随后给出了近似比为(√m 1)(log r/√m 1 1)的近似算法,此结果对一般图也成立.最后考虑了环网和树环网,给出了近似比为3.6和2△的近似算法,这里△是图的最大度.     

Approximation Algorithms for the Achromatic Number

The achromatic number for a graph G = V, E is the largest integer m such that there is a partition of V into disjoint independent sets {V₁, …, V_m} such that for each pair of distinct sets V_i, V_j, V_i V_j is not an independent set in G. Yannakakis and Gavril (1980, SIAM J. Appl. Math.38, 364–372) proved that determining this value for general graphs is NP-complete. For n-vertex graphs we present the first o(n) approximation algorithm for this problem. We also present an O(n^5/12) approximation algorithm for graphs with girth at least 5 and a constant approximation algorithm for trees.     

A Characterization of Projective Spaces by a Set of Planes

This note deals with the following question: How many planes of a linear space (P, $\mathfrak{L}$ ) must be known as projective planes to ensure that (P, $\mathfrak{L}$ ) is a projective space? The following answer is given: If for any subset M of a linear space (P, $\mathfrak{L}$ ) the restriction (M, $\mathfrak{L}$ )(M)) is locally complete, and if for every plane E of (M, $\mathfrak{L}$ (M)) the plane $\bar E$ generated by E is a projective plane, then (P, $\mathfrak{L}$ ) is a projective space (cf. 5.6). Or more generally: If for any subset M of P the restriction (M, $\mathfrak{L}$ (M)) is locally complete, and if for any two distinct coplanar lines G1, G2 ∈ $\mathfrak{L}$ (M) the lines $\bar G_1 ,\bar G_2 \varepsilon \mathfrak{L}$ generated by G1, G2 have a nonempty intersection and $\overline {G_1 \cup {\text{ }}G_2 }$ satisfies the exchange condition, then (P, $\mathfrak{L}$ ) is a generalized projective space.     

An efficient algorithm for the minimum capacity cut problem

Given a finite undirected graph with nonnegative edge capacities the minimum capacity cut problem consists of partitioning the graph into two nonempty sets such that the sum of the capacities of edges connecting the two parts is minimum among all possible partitionings. The standard algorithm to calculate a minimum capacity cut, due to Gomory and Hu (1961), runs in O(n ⁴) time and is difficult to implement. We present an alternative algorithm with the same worst-case bound which is easier to implement and which was found empirically to be far superior to the standard algorithm. We report computational results for graphs with up to 2000 nodes.Partial financial support by NSF grant DMS8508955 and ONR grant R&T4116663.Work done while visiting New York University. Partial financial support by a New York University Research Challenge Fund grant and ONR grant R&T4116663.     

The Pohozaev-Schoen identity on asymptotically Euclidean manifolds: Conservation laws and their applications

The aim of this paper is to present a version of the generalized Pohozaev-Schoen identity in the context of asymptotically Euclidean manifolds. Since these kind of geometric identities have proven to be a very powerful tool when analysing different geometric problems for compact manifolds, we will present a variety of applications within this new context. Among these applications, we will show some rigidity results for asymptotically Euclidean Ricci-solitons and Codazzi-solitons. Also, we will present an almost-Schur type inequality valid in this non-compact setting which does not need restrictions on the Ricci curvature. Finally, we will show how some rigidity results related with static potentials also follow from these type of conservation principles.     

Polynomial Time Algorithms to Approximate Permanents and Mixed Discriminants Within a Simply Exponential Factor

We present real, complex, and quaternionic versions of a simple randomized polynomial time algorithm to approximate the permanent of a nonnegative matrix and, more generally, the mixed discriminant of positive semidefinite matrices. The algorithm provides an unbiased estimator, which, with high probability, approximates the true value within a factor of O(cⁿ), where n is the size of the matrix (matrices) and where c ≈ 0.28 for the real version, c ≈ 0.56 for the complex version, and c ≈ 0.76 for the quaternionic version. We discuss possible extensions of our method as well as applications of mixed discriminants to problems of combinatorial counting. ©1999 John Wiley & Sons, Inc. Random Struct. Alg., 14, 29–61, 1999