When Does Eddy Viscosity Damp Subfilter Scales Sufficiently?

Large eddy simulation (LES) seeks to predict the dynamics of spatially filtered turbulent flows. The very essence is that the LES-solution contains only scales of size ≥Δ, where Δ denotes some user-chosen length scale. This property enables us to perform a LES when it is not feasible to compute the full, turbulent solution of the Navier-Stokes equations. Therefore, in case the large eddy simulation is based on an eddy viscosity model we determine the eddy viscosity such that any scales of size <Δ are dynamically insignificant. In this paper, we address the following two questions: how much eddy diffusion is needed to (a) balance the production of scales of size smaller than Δ; and (b) damp any disturbances having a scale of size smaller than Δ initially. From this we deduce that the eddy viscosity ν _e has to depend on the invariants q = \frac12tr(S²)q = \frac{1}{2}\mathrm{tr}(S^{2}) and r = -\frac13tr(S³)r= -\frac{1}{3}\mathrm{tr}(S^{3}) of the (filtered) strain rate tensor S. The simplest model is then given by n_e = \frac32(D/p)² |r|/q\nu_{e} = \frac{3}{2}(\Delta/\pi)^{2} |r|/q. This model is successfully tested for a turbulent channel flow (Re  _τ =590).     

Approximation Algorithms for <Emphasis Type="Italic">k</Emphasis>-hurdle Problems

The polynomial-time solvable k-hurdle problem is a natural generalization of the classical s-t minimum cut problem where we must select a minimum-cost subset S of the edges of a graph such that |p∩S|≥k for every s-t path p. In this paper, we describe a set of approximation algorithms for “k-hurdle” variants of the NP-hard multiway cut and multicut problems. For the k-hurdle multiway cut problem with r terminals, we give two results, the first being a pseudo-approximation algorithm that outputs a (k−1)-hurdle solution whose cost is at most that of an optimal solution for k hurdles. Secondly, we provide a 2(1-\frac1r)2(1-\frac{1}{r})-approximation algorithm based on rounding the solution of a linear program, for which we give a simple randomized half-integrality proof that works for both edge and vertex k-hurdle multiway cuts that generalizes the half-integrality results of Garg et al. for the vertex multiway cut problem. We also describe an approximation-preserving reduction from vertex cover as evidence that it may be difficult to achieve a better approximation ratio than 2(1-\frac1r)2(1-\frac{1}{r}). For the k-hurdle multicut problem in an n-vertex graph, we provide an algorithm that, for any constant ε>0, outputs a ⌈(1−ε)k⌉-hurdle solution of cost at most O(log n) times that of an optimal k-hurdle solution, and we obtain a 2-approximation algorithm for trees.     

Complexity of Hard-Core Set Proofs

We study a fundamental result of Impagliazzo (FOCS’95) known as the hard-core set lemma. Consider any function f:{0,1}ⁿ?{0,1}{f:\{0,1\}^n\to\{0,1\}} which is “mildly hard”, in the sense that any circuit of size s must disagree with f on at least a δ fraction of inputs. Then, the hard-core set lemma says that f must have a hard-core set H of density δ on which it is “extremely hard”, in the sense that any circuit of size s￠=O(s/(\frac1e²log(\frac1ed))){s'=O(s/(\frac{1}{\epsilon^2}\log(\frac{1}{\epsilon\delta})))} must disagree with f on at least (1-e)/2{(1-\epsilon)/2} fraction of inputs from H.     

Small Space Representations for Metric Min-sum k-Clustering and Their Applications

The min-sum k -clustering problem is to partition a metric space (P,d) into k clusters C ₁,…,C _k ?P such that $\sum_{i=1}^{k}\sum_{p,q\in C_{i}}d(p,q)The min-sum k -clustering problem is to partition a metric space (P,d) into k clusters C ₁,…,C _k ⊆P such that ?_i=1^k?_{p,q ? Ci}d(p,q)\sum_{i=1}^{k}\sum_{p,q\in C_{i}}d(p,q) is minimized. We show the first efficient construction of a coreset for this problem. Our coreset construction is based on a new adaptive sampling algorithm. With our construction of coresets we obtain two main algorithmic results.     

Approximate Pattern Matching with the <Emphasis Type="Italic">L</Emphasis><Subscript>1</Subscript>, <Emphasis Type="Italic">L</Emphasis><Subscript>2</Subscript> and <Emphasis Type="Italic">L</Emphasis><Subscript>∞</Subscript> Metrics

Given an alphabet Σ={1,2,…,|Σ|} text string T∈Σ ⁿ and a pattern string P∈Σ ^m , for each i=1,2,…,n−m+1 define L _p (i) as the p-norm distance when the pattern is aligned below the text and starts at position i of the text. The problem of pattern matching with L _p distance is to compute L _p (i) for every i=1,2,…,n−m+1. We discuss the problem for d=1,2,∞. First, in the case of L ₁ matching (pattern matching with an L ₁ distance) we show a reduction of the string matching with mismatches problem to the L ₁ matching problem and we present an algorithm that approximates the L ₁ matching up to a factor of 1+ε, which has an O(\frac1e²nlogmlog|S|)O(\frac{1}{\varepsilon^{2}}n\log m\log|\Sigma|) run time. Then, the L ₂ matching problem (pattern matching with an L ₂ distance) is solved with a simple O(nlog m) time algorithm. Finally, we provide an algorithm that approximates the L _∞ matching up to a factor of 1+ε with a run time of O(\frac1enlogmlog|S|)O(\frac{1}{\varepsilon}n\log m\log|\Sigma|) . We also generalize the problem of String Matching with mismatches to have weighted mismatches and present an O(nlog ⁴ m) algorithm that approximates the results of this problem up to a factor of O(log m) in the case that the weight function is a metric.     

Near-Entropy Hotlink Assignments

Consider a rooted tree T of arbitrary maximum degree d representing a collection of n web pages connected via a set of links, all reachable from a source home page represented by the root of T. Each web page i carries a probability p _i representative of the frequency with which it is visited. By adding hotlinks—shortcuts from a node to one of its descendents—we wish to minimize the expected number of steps l needed to visit pages from the home page, expressed as a function of the entropy H(p) of the access probabilities p. This paper introduces several new strategies for effectively assigning hotlinks in a tree. For assigning exactly one hotlink per node, our method guarantees an upper bound on l of 1.141H(p)+1 if d>2 and 1.08H(p)+2/3 if d=2. We also present the first efficient general methods for assigning at most k hotlinks per node in trees of arbitrary maximum degree, achieving bounds on l of at most \frac2H(p)log(k+1)+1\frac{2H(p)}{\log(k+1)}+1 and \fracH(p)log(k+d)-logd+1\frac{H(p)}{\log(k+d)-\log d}+1 , respectively. All our methods are strong, i.e., they provide the same guarantees on all subtrees after the assignment. We also present an algorithm implementing these methods in O(nlog n) time, an improvement over the previous O(n ²) time algorithms. Finally we prove a Ω(nlog n) lower bound on the running time of any strong method that guarantee an average access time strictly better than 2H(p).     

Approximating Minimum-Power Degree and Connectivity Problems

Power optimization is a central issue in wireless network design. Given a graph with costs on the edges, the power of a node is the maximum cost of an edge incident to it, and the power of a graph is the sum of the powers of its nodes. Motivated by applications in wireless networks, we consider several fundamental undirected network design problems under the power minimization criteria. Given a graph G=(V,E)\mathcal{G}=(V,\mathcal{E}) with edge costs {c(e):e∈ℰ} and degree requirements {r(v):v∈V}, the Minimum-Power Edge-Multi-Cover\textsf{Minimum-Power Edge-Multi-Cover} (MPEMC\textsf{MPEMC} ) problem is to find a minimum-power subgraph G of G\mathcal{G} so that the degree of every node v in G is at least r(v). We give an O(log n)-approximation algorithms for MPEMC\textsf{MPEMC} , improving the previous ratio O(log ⁴ n). This is used to derive an O(log n+α)-approximation algorithm for the undirected $\textsf{Minimum-Power $\textsf{Minimum-Power ($\textsf{MP$\textsf{MP ) problem, where α is the best known ratio for the min-cost variant of the problem. Currently, _boxclosen-k)\alpha=O(\log k\cdot \log\frac{n}{n-k}) which is O(log k) unless k=n−o(n), and is O(log ² k)=O(log ² n) for k=n−o(n). Our result shows that the min-power and the min-cost versions of the $\textsf{$\textsf{ problem are equivalent with respect to approximation, unless the min-cost variant admits an o(log n)-approximation, which seems to be out of reach at the moment.     

Large deviations for distributions of sums of random variables: Markov chain method

Let {ξ _k } _k=0^∞ be a sequence of i.i.d. real-valued random variables, and let g(x) be a continuous positive function. Under rather general conditions, we prove results on sharp asymptotics of the probabilities $ P\left\{ {\frac{1} {n}\sum\limits_{k = 0}^{n - 1} {g\left( {\xi _k } \right) < d} } \right\} $ P\left\{ {\frac{1} {n}\sum\limits_{k = 0}^{n - 1} {g\left( {\xi _k } \right) < d} } \right\} , n → ∞, and also of their conditional versions. The results are obtained using a new method developed in the paper, namely, the Laplace method for sojourn times of discrete-time Markov chains. We consider two examples: standard Gaussian random variables with g(x) = |x| ^p , p > 0, and exponential random variables with g(x) = x for x ≥ 0.     

Error Analysis for hp-FEM Semi-Lagrangian Second Order BDF Method for Convection-Dominated Diffusion Problems

We present in this paper an analysis of a semi-Lagrangian second order Backward Difference Formula combined with hp-finite element method to calculate the numerical solution of convection diffusion equations in ℝ². Using mesh dependent norms, we prove that the a priori error estimate has two components: one corresponds to the approximation of the exact solution along the characteristic curves, which is O(Dt²+h^m+1(1+\frac\mathopen|logh|Dt))O(\Delta t^{2}+h^{m+1}(1+\frac{\mathopen{|}\log h|}{\Delta t})); and the second, which is O(Dt^p+|| [(u)\vec]-[(u)\vec]_h||_L^￥)O(\Delta t^{p}+\| \vec{u}-\vec{u}_{h}\|_{L^{\infty}}), represents the error committed in the calculation of the characteristic curves. Here, m is the degree of the polynomials in the finite element space, [(u)\vec]\vec{u} is the velocity vector, [(u)\vec]_h\vec{u}_{h} is the finite element approximation of [(u)\vec]\vec{u} and p denotes the order of the method employed to calculate the characteristics curves. Numerical examples support the validity of our estimates.     

Geometric Representation of Graphs in Low Dimension Using Axis Parallel Boxes

An axis-parallel k-dimensional box is a Cartesian product R ₁×R ₂×???×R _k where R _i (for 1≤i≤k) is a closed interval of the form [a _i ,b _i ] on the real line. For a graph G, its boxicity box?(G) is the minimum dimension k, such that G is representable as the intersection graph of (axis-parallel) boxes in k-dimensional space. The concept of boxicity finds applications in various areas such as ecology, operations research etc. A number of NP-hard problems are either polynomial time solvable or have much better approximation ratio on low boxicity graphs. For example, the max-clique problem is polynomial time solvable on bounded boxicity graphs and the maximum independent set problem for boxicity d graphs, given a box representation, has a $\lfloor 1+\frac{1}{c}\log n\rfloor^{d-1}An axis-parallel k-dimensional box is a Cartesian product R ₁×R ₂×⋅⋅⋅×R _k where R _i (for 1≤i≤k) is a closed interval of the form [a _i ,b _i ] on the real line. For a graph G, its boxicity box (G) is the minimum dimension k, such that G is representable as the intersection graph of (axis-parallel) boxes in k-dimensional space. The concept of boxicity finds applications in various areas such as ecology, operations research etc. A number of NP-hard problems are either polynomial time solvable or have much better approximation ratio on low boxicity graphs. For example, the max-clique problem is polynomial time solvable on bounded boxicity graphs and the maximum independent set problem for boxicity d graphs, given a box representation, has a ?1+\frac1clogn?^d-1\lfloor 1+\frac{1}{c}\log n\rfloor^{d-1} approximation ratio for any constant c≥1 when d≥2. In most cases, the first step usually is computing a low dimensional box representation of the given graph. Deciding whether the boxicity of a graph is at most 2 itself is NP-hard.     

Spreading of Messages in Random Graphs

Consider the following model on the spreading of messages. A message initially convinces a set of vertices, called the seeds, of the Erdős-Rényi random graph G(n,p). Whenever more than a ρ∈(0,1) fraction of a vertex v’s neighbors are convinced of the message, v will be convinced. The spreading proceeds asynchronously until no more vertices can be convinced. This paper derives lower bounds on the minimum number of initial seeds, min-seed(n,p,d,r)\mathrm{min\hbox{-}seed}(n,p,\delta,\rho), needed to convince a δ∈{1/n,…,n/n} fraction of vertices at the end. In particular, we show that (1) there is a constant β>0 such that min-seed(n,p,d,r)=W(min{d,r}n)\mathrm{min\hbox{-}seed}(n,p,\delta,\rho)=\Omega(\min\{\delta,\rho\}n) with probability 1−n ^−Ω(1) for p≥β (ln (e/min {δ,ρ}))/(ρ n) and (2) min-seed(n,p,d,1/2)=W(dn/ln(e/d))\mathrm{min\hbox{-}seed}(n,p,\delta,1/2)=\Omega(\delta n/\ln(e/\delta)) with probability 1−exp (−Ω(δ n))−n ^−Ω(1) for all p∈[ 0,1 ]. The hidden constants in the Ω notations are independent of p.     

Improved Approximation Algorithms for Maximum Resource Bin Packing and Lazy Bin Covering Problems

In this paper, we study two variants of the bin packing and covering problems called Maximum Resource Bin Packing (MRBP) and Lazy Bin Covering (LBC) problems, and present new approximation algorithms for them. For the offline MRBP problem, the previous best known approximation ratio is \frac65\frac{6}{5} (=1.2) achieved by the classical First-Fit-Increasing (FFI) algorithm (Boyar et al. in Theor. Comput. Sci. 362(1–3):127–139, 2006). In this paper, we give a new FFI-type algorithm with an approximation ratio of \frac8071\frac{80}{71} (≈1.12676). For the offline LBC problem, it has been shown in Lin et al. (COCOON, pp. 340–349, 2006) that the classical First-Fit-Decreasing (FFD) algorithm achieves an approximation ratio of \frac7160\frac{71}{60} (≈1.18333). In this paper, we present a new FFD-type algorithm with an approximation ratio of \frac1715\frac{17}{15} (≈1.13333). Our algorithms are based on a pattern-based technique and a number of other observations. They run in near linear time (i.e., O(nlog n)), and therefore are practical.     

Interpolation of Shifted-Lacunary Polynomials

Given a “black box” function to evaluate an unknown rational polynomial f ? \mathbbQ[x]f \in {\mathbb{Q}}[x] at points modulo a prime p, we exhibit algorithms to compute the representation of the polynomial in the sparsest shifted power basis. That is, we determine the sparsity $t \in {\mathbb{Z}}_{>0}$t \in {\mathbb{Z}}_{>0}, the shift a ? \mathbbQ\alpha \in {\mathbb{Q}}, the exponents 0 ￡ e₁ < e₂ < ? < e_t{0 \leq e_{1} < e_{2} < \cdots < e_{t}}, and the coefficients c₁, ?, c_t ? \mathbbQ \{0}c_{1}, \ldots , c_{t} \in {\mathbb{Q}} \setminus \{0\} such that

Ramsey numbers and an approximation algorithm for the vertex cover problem

Summary We show two results. First we derive an upper bound for the special Ramsey numbers r _k(q) where r _k(q) is the largest number of nodes a graph without odd cycles of length bounded by 2k+1 and without an independent set of size q+1 can have. We prove The proof is constructive and yields an algorithm for computing an independent set of that size. Using this algorithm we secondly describe an O(¦V¦·¦E¦) time bounded approximation algorithm for the vertex cover problem, whose worst case ratio is , for all graphs with at most (2k+3) ^k (2k+2) nodes (e.g. 1.8, if ¦V¦146000).     

The Gaussian Surface Area and Noise Sensitivity of Degree-d Polynomial Threshold Functions

We prove asymptotically optimal bounds on the Gaussian noise sensitivity and Gaussian surface area of degree-d polynomial threshold functions. In particular, we show that for f a degree-d polynomial threshold function that the Gaussian noise sensitivity of f with parameter e{\epsilon} is at most \fracdarcsin(?{2e-e²})p{\frac{d\arcsin\left(\sqrt{2\epsilon-\epsilon^2}\right)}{\pi}} . This bound translates into an optimal bound on the Gaussian surface area of such functions, namely that the Gaussian surface area is at most \fracd?{2p}{\frac{d}{\sqrt{2\pi}}} . Finally, we note that the later result implies bounds on the runtime of agnostic learning algorithms for polynomial threshold functions.     

The Directed Orienteering Problem

This paper studies vehicle routing problems on asymmetric metrics. Our starting point is the directed k-TSP problem: given an asymmetric metric (V,d), a root r∈V and a target k≤|V|, compute the minimum length tour that contains r and at least k other vertices. We present a polynomial time O(\fraclog² nloglogn·logk)O(\frac{\log^{2} n}{\log\log n}\cdot\log k)-approximation algorithm for this problem. We use this algorithm for directed k-TSP to obtain an O(\fraclog² nloglogn)O(\frac{\log^{2} n}{\log\log n})-approximation algorithm for the directed orienteering problem. This answers positively, the question of poly-logarithmic approximability of directed orienteering, an open problem from Blum et al. (SIAM J. Comput. 37(2):653–670, 2007). The previously best known results were quasi-polynomial time algorithms with approximation guarantees of O(log ² k) for directed k-TSP, and O(log n) for directed orienteering (Chekuri and Pal in IEEE Symposium on Foundations in Computer Science, pp. 245–253, 2005). Using the algorithm for directed orienteering within the framework of Blum et al. (SIAM J. Comput. 37(2):653–670, 2007) and Bansal et al. (ACM Symposium on Theory of Computing, pp. 166–174, 2004), we also obtain poly-logarithmic approximation algorithms for the directed versions of discounted-reward TSP and vehicle routing problem with time-windows.     

Parallel merging with restriction

In this paper, we study the merging of two sorted arrays and on EREW PRAM with two restrictions: (1) The elements of two arrays are taken from the integer range [1,n], where n=Max(n ₁,n ₂). (2) The elements are taken from either uniform distribution or non-uniform distribution such that , for 1≤i≤p (number of processors). We give a new optimal deterministic algorithm runs in time using p processors on EREW PRAM. For ; the running time of the algorithm is O(log ^(g) n) which is faster than the previous results, where log ^(g) n=log log ^(g−1) n for g>1 and log ⁽¹⁾ n=log n. We also extend the domain of input data to [1,n ^k ], where k is a constant.

On the performance of Dijkstra’s third self-stabilizing algorithm for mutual exclusion and related algorithms

In Dijkstra (Commun ACM 17(11):643–644, 1974) introduced the notion of self-stabilizing algorithms and presented three such algorithms for the problem of mutual exclusion on a ring of n processors. The third algorithm is the most interesting of these three but is rather non intuitive. In Dijkstra (Distrib Comput 1:5–6, 1986) a proof of its correctness was presented, but the question of determining its worst case complexity—that is, providing an upper bound on the number of moves of this algorithm until it stabilizes—remained open. In this paper we solve this question and prove an upper bound of 3\frac1318 n² + O(n){3\frac{13}{18} n^2 + O(n)} for the complexity of this algorithm. We also show a lower bound of 1\frac56 n² - O(n){1\frac{5}{6} n^2 - O(n)} for the worst case complexity. For computing the upper bound, we use two techniques: potential functions and amortized analysis. We also present a new-three state self-stabilizing algorithm for mutual exclusion and show a tight bound of \frac56 n² + O(n){\frac{5}{6} n^2 + O(n)} for the worst case complexity of this algorithm. In Beauquier and Debas (Proceedings of the second workshop on self-stabilizing systems, pp 17.1–17.13, 1995) presented a similar three-state algorithm, with an upper bound of 5\frac34n²+O(n){5\frac{3}{4}n^2+O(n)} and a lower bound of \frac18n²-O(n){\frac{1}{8}n^2-O(n)} for its stabilization time. For this algorithm we prove an upper bound of 1\frac12n² + O(n){1\frac{1}{2}n^2 + O(n)} and show a lower bound of n ²−O(n). As far as the worst case performance is considered, the algorithm in Beauquier and Debas (Proceedings of the second workshop on self-stabilizing systems, pp 17.1–17.13, 1995) is better than the one in Dijkstra (Commun ACM 17(11):643–644, 1974) and our algorithm is better than both.     

Minimum Augmentation of Edge-Connectivity between Vertices and Sets of Vertices in Undirected Graphs

Given an undirected multigraph G=(V,E), a family $\mathcal{W}Given an undirected multigraph G=(V,E), a family W\mathcal{W} of areas W⊆V, and a target connectivity k≥1, we consider the problem of augmenting G by the smallest number of new edges so that the resulting graph has at least k edge-disjoint paths between v and W for every pair of a vertex v∈V and an area W ? WW\in \mathcal{W} . So far this problem was shown to be NP-complete in the case of k=1 and polynomially solvable in the case of k=2. In this paper, we show that the problem for k≥3 can be solved in O(m+n(k ³+n ²)(p+kn+nlog n)log k+pkn ³log (n/k)) time, where n=|V|, m=|{{u,v}|(u,v)∈E}|, and p=|W|p=|\mathcal{W}| .     

A Fast Output-Sensitive Algorithm for Boolean Matrix Multiplication

We use randomness to exploit the potential sparsity of the Boolean matrix product in order to speed up the computation of the product. Our new fast output-sensitive algorithm for Boolean matrix product and its witnesses is randomized and provides the Boolean product and its witnesses almost certainly. Its worst-case time performance is expressed in terms of the input size and the number of non-zero entries of the product matrix. It runs in time [(O)\tilde](n²s^w/2-1)\widetilde{O}(n^{2}s^{\omega/2-1}), where the input matrices have size n×n, the number of non-zero entries in the product matrix is at most s, ω is the exponent of the fast matrix multiplication and [(O)\tilde](f(n))\widetilde{O}(f(n)) denotes O(f(n)log  ^d n) for some constant d. By the currently best bound on ω, its running time can be also expressed as [(O)\tilde](n²s^0.188)\widetilde{O}(n^{2}s^{0.188}). Our algorithm is substantially faster than the output-sensitive column-row method for Boolean matrix product for s larger than n ^1.232 and it is never slower than the fast [(O)\tilde](n^w)\widetilde{O}(n^{\omega})-time algorithm for this problem. By applying the fast rectangular matrix multiplication, we can refine our upper bound further to the form [(O)\tilde](n^{w(\frac12log_ns,1,1)})\widetilde{O}(n^{\omega(\frac{1}{2}\log_{n}s,1,1)}), where ω(p,q,t) is the exponent of the fast multiplication of an n ^p ×n ^q matrix by an n ^q ×n ^t matrix.