Improved Approximation Results for the Minimum Energy Broadcasting Problem

In this paper we present new results on the performance of the Minimum Spanning Tree heuristic for the Minimum Energy Broadcast Routing (MEBR) problem. We first prove that, for any number of dimensions d≥2, the approximation ratio of the heuristic does not increase when the power attenuation coefficient α, that is the exponent to which the coverage distance must be raised to give the emission power, grows. Moreover, we show that, for any fixed instance, as a limit for α going to infinity, the ratio tends to the lower bound of Clementi et al. (Proceedings of the 18th annual symposium on theoretical aspects of computer science (STACS), pp. 121–131, 2001), Wan et al. (Wirel. Netw. 8(6):607–617, 2002) given by the d-dimensional kissing number, thus closing the existing gap between the upper and the lower bound. We then introduce a new analysis allowing to establish a 7.45-approximation ratio for the 2-dimensional case, thus significantly decreasing the previously known 12 upper bound (Wan et al. in Wirel. Netw. 8(6):607–617, 2002) (actually corrected to 12.15 in Klasing et al. (Proceedings of the 3rd IFIP-TC6 international networking conference, pp. 866–877, 2004)). Finally, we extend our analysis to any number of dimensions d≥2 and any α≥d, obtaining a general approximation ratio of 3 ^d −1, again independent of α. The improvements of the approximation ratios are specifically significant in comparison with the lower bounds given by the kissing numbers, as these grow at least exponentially with respect to d. The research was partially funded by the European project COST Action 293, “Graphs and Algorithms in Communication Networks” (GRAAL). Preliminary version of this paper appeared in Flammini et al. (Proceedings of ACM joint workshop on foundations of mobile computing (DIALM-POMC), pp. 85–91, 2004).     

The Fully Polynomial Approximation Algorithm for the 0-1 Knapsack Problem

A modified fast approximation algorithm for the 0-1 knapsack problem with improved complexity is presented, based on the schemes of Ibarra, Kim and Babat. By using a new partition of items, the algorithm solves the n -item 0-1 knapsack problem to any relative error tolerance ε > 0 in the scaled profit space P ^* /K = O ( 1/ ε ^1+δ ) with time O(n log(1/ ε )+1/ ε^{2+2δ}) and space O(n +1/ ɛ^{2+δ}), where P^{*} and b are the maximal profit and the weight capacity of the knapsack problem, respectively, K is a problem-dependent scaling factor, δ={α}/(1+α) and α=O( log b ). This algorithm reduces the exponent of the complexity bound in [5].     

Efficient Reorganization of Binary Search Trees

We consider the problem of maintaining a binary search tree ({bst}) that minimizes the average access cost needed to satisfy randomly generated requests. We analyze scenarios in which the accesses are generated according to a vector of fixed probabilities which is unknown . Our approach is statistical. We devise policies for modifying the tree structure dynamically, using rotations of accessed records. The aim is to produce good approximations of the optimal structure of the tree, while keeping the number of rotations as small as possible. The heuristics that we propose achieve a close approximation to the optimal BST, with lower organization costs than any previously studied. We introduce the MOVE_ONCE rule. The average access cost to the tree under this rule is shown to equal the value achieved by the common rule Move to the Root (MTR). The advantage of MOVE_ONCE over MTR and similar rules is that it relocates each of the items in the tree at most once. We show that the total expected cost of modifying the tree by the MOVE_ONCE rule is bounded from above by 2(n+1)H _n -4n rotations (in a tree with n records), where H _n is the n th harmonic number. Extensive experiments show that this value is an overestimate, and in fact the number of rotations is linear for all the access probability vectors we tested. An approximate analysis is shown to match the experimental results, producing the expected number n((π ² /3)-2) - 2\ln n+0.1354 . Next we combine the MOVE_ONCE rule with reference counters, one per record, that provide estimates of the reference probabilities. We call the resulting reorganization rule MOUCS. We show that, for any δ , α >0 and sufficiently large n , it achieves a cost that approaches the optimum up to an absolute difference of δ with probability higher than 1- α , within a number of accesses that is proportional to n (\lg n) ² /(αδ ² ) . Received March 10, 2001; revised March 26, 2001.     

Polynomial algorithms for finding the asymptotically optimum plan of the multiindex axial assignment problem

To construct the asymptotically optimum plan of the p-index axial assignment problem of order n, p algorithms α₀, α₁, ..., α _p−1 with complexities equal to O(n^p+1), O(n^p), ..., O(n²) operations, respectively, are proposed and substantiated under some additional conditions imposed on the coefficients of the objective function. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 6, pp. 176–181, November–December 2005.     

Bounded-Diameter Minimum-Cost Graph Problems

We present approximation algorithms for two closely related bicriteria problems. Given a graph with two weight functions on the edges, length and cost, we consider the Bounded-Diameter Minimum-Cost Steiner Tree (BDMST) problem and the Bounded-Diameter Minimum-Cardinality Edge Addition (BDMC) problem. We present a parameterized approximation algorithm for the BDMST problem with a bicriteria approximation ratio of (O(p log s/log p),O(log s/log p)) where the first factor gives the relaxation on the diameter bound, the second factor is the cost-approximation factor, s is the number of required nodes and p, 1 ≤ p < s, is an input parameter. The parameter p allows a trade-off between the two approximation factors. This is the first improvement of the cost-approximation factor since the scheme proposed by Marathe et al. [9]. For example, p can be set to s^α to obtain an (O(s^α),O(1)) approximation for a constant α. The algorithm is very simple and is suitable for distributed implementations. We also present the first algorithm for Bounded-Hops Minimum-Cost Steiner Tree for complete graphs with triangle inequality. This model includes graphs defined by points in a Euclidean space of any dimension. The algorithm guarantees an approximation ratio of (O(log_ds),O(log_ds)) where d is the bound on the diameter. This is an improvement over the general-case approximation when d is comparable with s. For example, the ratio is (O(1),O(1)) for any d = s^α where α is a constant between 0 and 1. For the case where the number of terminals is a constant and all edge lengths are unit, we have a polynomial-time algorithm. This can be extended to any length function providing a (1 + ε) in the approximation with ε showing up in the time complexity of the algorithm. For another special case, where the cost of any edge is either 1 or 0 and the length of each edge is positive, an algorithm with approximation ratio of (O(log(c log s)), O(log(c log s))) is presented, where c is the cost of the optimal solution. This approximation is a significant improvement over (O(log s),O(log s)) when the cost of the solution c is much smaller than the number of terminals s. This is useful when an existing multicast network is to be modified to accommodate new terminals with the addition of as few new edges as possible. We also propose an approximation algorithm for the Bounded-Diameter Minimum-Cardinality Edge Addition problem, which achieves an O(log n) approximation while relaxing the diameter bound by 2. While this ratio is the same as the one claimed in [3], this algorithm is simple and combinatorial rather than based on the Linear Program solution and can be readily modified for a distributed implementation.     

Multivariate numerical approximation using constructive L^{2} (\mathbb{R}) RBF neural network

For the multivariate continuous function, using constructive feedforward L² (\mathbbR) L^{2} (\mathbb{R}) radial basis function (RBF) neural network, we prove that a L² (\mathbbR) L^{2} (\mathbb{R}) RBF neural network with n + 1 hidden neurons can interpolate n + 1 multivariate samples with zero error. Then, we prove that the L² (\mathbbR) L^{2} (\mathbb{R}) RBF neural network can uniformly approximate any continuous multivariate function with arbitrary precision. The correctness and effectiveness are verified through eight numeric experiments.     

The essential order of approximation for neural networks

There have been various studies on approximation ability of feedforward neural networks (FNNs). Most of the existing studies are, however, only concerned with density or upper bound estimation on how a multivariate function can be approximated by an FNN, and consequently, the essential approximation ability of an FNN cannot be revealed. In this paper, by establishing both upper and lower bound estimations on approximation order, the essential approximation ability (namely, the essential approximation order) of a class of FNNs is clarified in terms of the modulus of smoothness of functions to be approximated. The involved FNNs can not only approximate any continuous or integrable functions defined on a compact set arbitrarily well, but also provide an explicit lower bound on the number of hidden units required. By making use of multivariate approximation tools, it is shown that when the functions to be approximated are Lipschitzian with order up to 2, the approximation speed of the FNNs is uniquely deter     

Universal routing schemes

Summary.  In this paper, we deal with the compact routing problem, that is implementing routing schemes that use a minimum memory size on each router. A universal routing scheme is a scheme that applies to all n-node networks. In [31], Peleg and Upfal showed that one cannot implement a universal routing scheme with less than a total of Ω(n ^1+1/(2s+4)) memory bits for any given stretch factor s≧1. We improve this bound for stretch factors s, 1≦s<2, by proving that any near-shortest path universal routing scheme uses a total of Ω(n ²) memory bits in the worst-case. This result is obtained by counting the minimum number of routing functions necessary to route on all n-node networks. Moreover, and more fundamentally, we give a tight bound of Θ(n log n) bits for the local minimum memory requirement of universal routing scheme of stretch factors s, 1≦s<2. More precisely, for any fixed constant ɛ, 0<ɛ<1, there exists a n-node network G on which at least Ω(n ^ɛ) routers require Θ(n log n) bits each to code any routing function on G of stretch factor <2. This means that, whatever you choose the routing scheme, there exists a network on which one cannot compress locally the routing information better than routing tables do. Received: August 1995 / Accepted: August 1996     

Combining Markov-Chain Analysis and Drift Analysis

In their seminal article Droste, Jansen, and Wegener (Theor. Comput. Sci. 276:51–82, 2002) consider a basic direct-search heuristic with a global search operator, namely the so-called (1+1) Evolutionary Algorithm ((1+1) EA). They present the first theoretical analysis of the (1+1) EA’s expected runtime for the class of linear functions over the search space {0,1} ⁿ . In a rather long and involved proof they show that, for any linear function, the expected runtime is O(nlog n), i.e., that there are two constants c and n′ such that, for n≥n′, the expected number of iterations until a global optimum is generated is bounded above by c⋅nlog ₂ n. However, neither c nor n′ are specified—they would be pretty large. Here we reconsider this optimization scenario to demonstrate the potential of an analytical method that makes use of the distribution of the evolving candidate solution over the search space {0,1} ⁿ . Actually, an invariance property of this distribution is proved, which is then used to obtain a significantly improved bound on the drift, namely the expected change of a potential function, here the number of bits set correctly. Finally, this better estimate of the drift enables an upper bound on the expected number of iterations of 3.8nlog ₂ n+7.6log ₂ n for n≥2.     

Entropy of Operators or why Matrix Multiplication is Hard for Depth-Two Circuits

We consider unbounded fanin depth-2 circuits with arbitrary boolean functions as gates. We define the entropy of an operator f:{0,1} ⁿ →{0,1} ^m as the logarithm of the maximum number of vectors distinguishable by at least one special subfunction of f. Our main result is that every depth-2 circuit for f requires at least entropy(f) wires. This is reminiscent of a classical lower bound of Nechiporuk on the formula size, and gives an information-theoretic explanation of why some operators require many wires. We use this to prove a tight estimate Θ(n ³) of the smallest number of wires in any depth-2 circuit computing the product of two n by n matrices over any finite field. Previously known lower bound for this operator was Ω(n ²log n).     

Hardness and approximation results for packing steiner trees

We study approximation algorithms and hardness of approximation for several versions of the problem of packing Steiner trees. For packing edge-disjoint Steiner trees of undirected graphs, we show APX-hardness for four terminals. For packing Steiner-node-disjoint Steiner trees of undirected graphs, we show a logarithmic hardness result, and give an approximation guarantee ofO (√n logn), wheren denotes the number of nodes. For the directed setting (packing edge-disjoint Steiner trees of directed graphs), we show a hardness result of Θ(m ^1/3/−ɛ) and give an approximation guarantee ofO(m ^1/2/+ɛ), wherem denotes the number of edges. We have similar results for packing Steiner-node-disjoint priority Steiner trees of undirected graphs. Supported by NSERC Grant No. OGP0138432. Supported by an NSERC postdoctoral fellowship, Department of Combinatorics and Optimization at University of Waterloo, and a University start-up fund at University of Alberta.     

Approximation of functions by perceptrons: a new approach

We provide a constructive proof of the theorem of function approximation by perceptrons (cf Leshno et al. [1], Hornik [2]) when the activation function ψ isC∞ with all its derivatives non 0 at 0. We deal with uniform approximation on compact sets of continuous functions on ℜ ^d ,d≥1. This approach is elementary and provides some approximation results for the derivatives along with some bounds for the hidden layer.     

The Asymptotic Number of Leftist Trees

It is shown that the number of leftist trees of size n in a simply generated family of trees is asymptotically given by \sim α c ⁿ n ^-3/2 with certain constants α>0 and c >1 . Furthermore, it is proved that the number of leaves in leftist trees with n nodes satisfies a central limit theorem. Received June 6, 2000; revised July 14, 2000.     

On Constrained Facility Location Problems

Given m facilities each with an opening cost, n demands, and distance between every demand and facility, the Facility Location problem finds a solution which opens some facilities to connect every demand to an opened facility such that the total cost of the solution is minimized. The k-Facility Location problem further requires that the number of opened facilities is at most k, where k is a parameter given in the instance of the problem. We consider the Facility Location problems satisfying that for every demand the ratio of the longest distance to facilities and the shortest distance to facilities is at most ω, where ω is a predefined constant. Using the local search approach with scaling technique and error control technique, for any arbitrarily small constant > 0, we give a polynomial-time approximation algorithm for the ω-constrained Facility Location problem with approximation ratio 1 + ω + 1 + ε, which significantly improves the previous best known ratio (ω + 1)/α for some 1≤α≤2, and a polynomial-time approximation algorithm for the ω-constrained k- Facility Location problem with approximation ratio ω+1+ε. On the aspect of approximation hardness, we prove that unless NP■DTIME(nO(loglogn)), the ω-constrained Facility Location problem cannot be approximated within 1 + lnω - 1, which slightly improves the previous best known hardness result 1.243 + 0.316ln(ω - 1). The experimental results on the standard test instances of Facility Location problem show that our algorithm also has good performance in practice.     

Speed Scaling of Processes with Arbitrary Speedup Curves on a Multiprocessor

We consider the setting of a multiprocessor where the speeds of the m processors can be individually scaled. Jobs arrive over time and have varying degrees of parallelizability. A nonclairvoyant scheduler must assign the processes to processors, and scale the speeds of the processors. We consider the objective of energy plus flow time. We assume that a processor running at speed s uses power s ^α for some constant α>1. For processes that may have side effects or that are not checkpointable, we show an W(m^(a-1)/a2)\Omega(m^{(\alpha -1)/\alpha^{2}}) bound on the competitive ratio of any randomized algorithm. For checkpointable processes without side effects, we give an O(log m)-competitive algorithm. Thus for processes that may have side effects or that are not checkpointable, the achievable competitive ratio grows quickly with the number of processors, but for checkpointable processes without side effects, the achievable competitive ratio grows slowly with the number of processors. We then show a lower bound of Ω(log ^1/α m) on the competitive ratio of any randomized algorithm for checkpointable processes without side effects.     

Exact and Approximate Truthful Mechanisms for the Shortest Paths Tree Problem

Let a communication network be modeled by an undirected graph G=(V,E) of n nodes and m edges, and assume that edges are controlled by selfish agents. In this paper we analyze the problem of designing a truthful mechanism for computing one of the most popular structures in communication networks, i.e., the single-source shortest paths tree. More precisely, we will study several realistic scenarios, in which each agent can own either a single or multiple edges of G. In particular, for the single-edge case, we will show that: (i) in the classic utilitarian case, the problem can be solved efficiently in O(mnlog α(m,n)) time, where α(m,n) is the inverse of the Ackermann’s function; (ii) in a meaningful non-utilitarian case, namely that in which agents’ valuation functions only depend on the edge lengths, the problem can be solved in O(m+nlog n) time. Conversely, for the multiple-edges case, we will show in the utilitarian case an O(mP+nPlog n) time truthful mechanism, where P=O(n) denotes the number of agents participating in the solution, while in the same non-utilitarian case we will prove a general lower bound to the approximation ratio that can be achieved by any truthful mechanism, by showing that no c-approximate mechanism can exist, for any fixed . Work partially supported by the Research Project GRID.IT, funded by the Italian Ministry of Education, University and Research. Part of the results herein contained was presented at the 11th International Euro-Par Conference (Euro-Par’05), Lisbon, Portugal, 2005.     

Piercing Translates and Homothets of a Convex Body

According to a classical result of Grünbaum, the transversal number τ(ℱ) of any family ℱ of pairwise-intersecting translates or homothets of a convex body C in ℝ ^d is bounded by a function of d. Denote by α(C) (resp. β(C)) the supremum of the ratio of the transversal number τ(ℱ) to the packing number ν(ℱ) over all finite families ℱ of translates (resp. homothets) of a convex body C in ℝ ^d . Kim et al. recently showed that α(C) is bounded by a function of d for any convex body C in ℝ ^d , and gave the first bounds on α(C) for convex bodies C in ℝ ^d and on β(C) for convex bodies C in the plane.     

Efficient algorithms for constructing (1+∊,β)-spanners in the distributed and streaming models

For an unweighted undirected graph G = (V,E), and a pair of positive integers α ≥ 1, β ≥ 0, a subgraph G′ = (V,H), H ⊂eqE, is called an (α,β)-spanner of G if for every pair of vertices u,v ∊ V, dist_G′(u,v) ≤ α ⋅ dist_G(u,v) + β. It was shown in [21] that for any ∊ > 0, κ = 1,2,…, there exists an integer β = β(∊,κ) such that for every n-vertex graph G there exists a (1+∊,β)-spanner G′ with O(n^1+1/κ) edges. An efficient distributed protocol for constructing (1+∊,β)-spanners was devised in [19]. The running time and the communication complexity of that protocol are O(n^1+ρ) and O(|E|n^ρ), respectively, where ρ is an additional control parameter of the protocol that affects only the additive term β. In this paper we devise a protocol with a drastically improved running time (O(n^ρ) as opposed to O(n^1+ρ)) for constructing (1+∊,β)-spanners. Our protocol has the same communication complexity as the protocol of [19], and it constructs spanners with essentially the same properties as the spanners that are constructed by the protocol of [19]. The protocol can be easily extended to a parallel implementation which runs in O(log n + (|E|⋅ n^ρlog n)/p) time using p processors in the EREW PRAM model. In particular, when the number of processors, p, is at least |E|⋅ n^ρ, the running time of the algorithm is O(log n). We also show that our protocol for constructing (1+∊,β)-spanners can be adapted to the streaming model, and devise a streaming algorithm that uses a constant number of passes and O(n^1+1/κ⋅ {log} n) bits of space for computing all-pairs-almost-shortest-paths of length at most by a multiplicative factor (1+∊) and an additive term of β greater than the shortest paths. Our algorithm processes each edge in time O(n^ρ), for an arbitrarily small ρ > 0. The only previously known algorithm for the problem [23] constructs paths of length κ times greater than the shortest paths, has the same space requirements as our algorithm, but requires O(n^1+1/κ) time for processing each edge of the input graph. However, the algorithm of [23] uses just one pass over the input, as opposed to the constant number of passes in our algorithm. We also show that any streaming algorithm for o(n)-approximate distance computation requires Ω(n) bits of space. This work was Supported by the DoD University Research Initiative (URI) administered by the Office of Naval Research under Grant N00014-01-1-0795. Michael Elkin was supported by ONR grant N00014-01-1-0795. Jian Zhang was supported by ONR grant N00014-01-1-0795 and NSF grants CCR-0105337 and ITR-0331548. Preliminary version of this paper was published in PODC’04, see [22]. After the preliminary version of our paper [22] appeared on PODC’04, Feigenbaum et al. [24] came up with a new streaming algorithm for the problem that is far more efficient than [23] in terms of time-per-edge processing. However, our algorithm is still the only existing streaming algorithm that provides an almost additive approximation of distances.