Online time-constrained scheduling in linear and ring networks

We consider the problem of scheduling a sequence of packets over a linear network, where every packet has a source and a target, as well as a release time and a deadline by which it must arrive at its target. The model we consider is bufferless, where packets are not allowed to be buffered in nodes along their paths other than at their source. This model applies to optical networks where opto-electronic conversion is costly, and packets mostly travel through bufferless hops. The offline version of this problem was previously studied in M. Adler et al. (2002) [3]. In this paper we study the online version of the problem, where we are required to schedule the packets without knowledge of future packet arrivals. We use competitive analysis to evaluate the performance of our algorithms. We present the first online algorithms for several versions of the problem. For the problem of throughput maximization, where all packets have uniform weights, we give an algorithm with a logarithmic competitive ratio, and present some lower bounds. For other weight functions, we show algorithms that achieve optimal competitive ratios.     

On the Turán number for the hexagon

A long-standing conjecture of Erd?s and Simonovits is that ex(n,C_2k), the maximum number of edges in an n-vertex graph without a 2k-gon is asymptotically as n tends to infinity. This was known almost 40 years ago in the case of quadrilaterals. In this paper, we construct a counterexample to the conjecture in the case of hexagons. For infinitely many n, we prove that

     

Quadratic forms on graphs

We introduce a new graph parameter, called the Grothendieck constant of a graph G=(V,E), which is defined as the least constant K such that for every A:E→ℝ,

Nonembeddability theorems via Fourier analysis

Various new nonembeddability results (mainly into L₁) are proved via Fourier analysis. In particular, it is shown that the Edit Distance on {0,1}^d has L₁ distortion We also give new lower bounds on the L₁ distortion of flat tori, quotients of the discrete hypercube under group actions, and the transportation cost (Earthmover) metric.     

Girth and Euclidean distortion

Let G be a k-regular graph, , with girth g. We prove that every embedding has distortion . Two proofs are given, one based on Markov type [B] and the other on quadratic programming. In the core of both proofs are some Poincaré-type inequalities on graph metrics. Submitted: July 2001, Revised: September 2001.     

Triple-hybrid sub-micron particles: Ag@polymer@silica

Journal of Sol-Gel Science and Technology - Methods for the synthesis of triple-hybrid (metal, organic polymer, ceramic component) submicron particles of silver@(polymer@silica) spheres were...     

The Johnson–Lindenstrauss Lemma Almost Characterizes Hilbert Space, But Not Quite

Let X be a normed space that satisfies the Johnson–Lindenstrauss lemma (J–L lemma, in short) in the sense that for any integer n and any x ₁,…,x _n ∈X, there exists a linear mapping L:X→F, where F⊆X is a linear subspace of dimension O(log n), such that ‖x _i −x _j ‖≤‖L(x _i )−L(x _j )‖≤O(1)⋅‖x _i −x _j ‖ for all i,j∈{1,…,n}. We show that this implies that X is almost Euclidean in the following sense: Every n-dimensional subspace of X embeds into Hilbert space with distortion 2^2O(log*n)2^{2^{O(\log^{*}n)}} . On the other hand, we show that there exists a normed space Y which satisfies the J–L lemma, but for every n, there exists an n-dimensional subspace E _n ⊆Y whose Euclidean distortion is at least 2^Ω(α(n)), where α is the inverse Ackermann function.     

The Euclidean Distortion of the Lamplighter Group

We show that the cyclic lamplighter group C ₂ ? C _n embeds into Hilbert space with distortion $\mathrm{O}(\sqrt{\log n})We show that the cyclic lamplighter group C ₂ ≀ C _n embeds into Hilbert space with distortion O(?{logn})\mathrm{O}(\sqrt{\log n}) . This matches the lower bound proved by Lee et al. (Geom. Funct. Anal., 2009), answering a question posed in that paper. Thus, the Euclidean distortion of C ₂ ≀ C _n is \varTheta(?{logn})\varTheta(\sqrt{\log n}) . Our embedding is constructed explicitly in terms of the irreducible representations of the group. Since the optimal Euclidean embedding of a finite group can always be chosen to be equivariant, as shown by Aharoni et al. (Isr. J. Math. 52(3):251–265, 1985) and by Gromov (see de Cornulier et. al. in Geom. Funct. Anal., 2009), such representation-theoretic considerations suggest a general tool for obtaining upper and lower bounds on Euclidean embeddings of finite groups.     

Maximum gradient embeddings and monotone clustering

Let (X,d _X ) be an n-point metric space. We show that there exists a distribution over non-contractive embeddings into trees f: X → T such that for every x ∈ X, where C is a universal constant. Conversely we show that the above quadratic dependence on log n cannot be improved in general. Such embeddings, which we call maximum gradient embeddings, yield a framework for the design of approximation algorithms for a wide range of clustering problems with monotone costs, including fault-tolerant versions of k-median and facility location.