Almost Instantaneous Fixed to Variable (AIFV) coding is a relatively new method of loss less coding that, unlike Huffman coding, uses more than one coding tree. The problem of constructing optimal AIFV codes is a special case of that of constructing minimum cost Markov Chains. This paper provides the first complete proof of correctness for the previously known iterative algorithm for constructing such Markov chains. A recent work describes how to efficiently solve the Markov Chain problem by first constructing a Markov Chain Polytope and then running the Ellipsoid algorithm for linear programming on it. This paper's second result is that, in the AIFV case, a special property of the polytope instead permits solving the corresponding linear program using simple binary search.

It is possible to improve upon Tunstall coding using a collection of multiple parse trees. The best such results so far are Iwata and Yamamoto's maximum cost AIVF codes. The most efficient algorithm for designing such codes is an iterative one that could run in exponential time. In this paper, we show that this problem fits into the framework of a newly developed technique that uses linear programming with the Ellipsoid method to solve the minimum cost Markov chain problem. This permits constructing maximum cost AIVF codes in (weakly) polynomial time.

Huffman Codes are optimal Instantaneous Fixed-to-Variable (FV) codes in which every source symbol can only be encoded by one codeword. Relaxing these constraints permits constructing better FV codes. More specifically, recent work has shown that AIFV-$m$codes can beat Huffman coding. AIFV-$m$codes construct an$m$-tuple of different coding trees between which the code alternates and are only almost instantaneous (AI). This means that decoding a word might require a delay of a finite number of bits. Current algorithms for constructing optimal AIFV-$m$codes are iterative processes that construct progressively “better sets” of code trees. The processes have been proven to finitely converge to the optimal code but with no known bounds on the convergence rate. This paper derives a geometric interpretation of the space of binary AIFV-2 codes, permitting the development of the first polynomially time-bounded procedure for constructing optimal AIFV codes. This binary-search like procedure will run in$O(n^{3} b)$time, where$n$is the number of symbols in the source alphabet and$b$is the maximum number of bits used to encode any one input probability.

AIFV-m coding is a method for constructing lossless codes for memoryless sources that provide better worst-case redundancy than Huffman codes. It achieves this by using m code trees instead of one and also by allowing some bounded delay in the decoding process. The process for constructing optimal AIFV-m on n source symbols is based on multiple calls to a local optimization subroutine. Local optimization was originally performed using Integer Linear Programming, which was later replaced by an O(mn2m+1)-time Dynamic Program. The running time for m = 2 was further improved to O(n3), but the speedup technique was not applicable to m > 2. This paper introduces a new dynamic programming approach that yields a general O(mnm+2)-time algorithm.

Abstract Huang and Wong (Acta Inform 21(1):113–123, 1984) proposed a polynomial-time dynamic-programming algorithm for computing optimal generalized binary split trees. We show that their algorithm is incorrect. Thus, it remains open whether such trees can be computed in polynomial time. Spuler (Optimal search trees using two-way key comparisons, PhD thesis, 1994) proposed modifying Huang and Wong’s algorithm to obtain an algorithm for a different problem: computing optimal two-way comparison search trees. We show that the dynamic program underlying Spuler’s algorithm is not valid, in that it does not satisfy the necessary optimal-substructure property and its proposed recurrence relation is incorrect. It remains unknown whether the algorithm is guaranteed to compute a correct overall solution.

We present a simple O(n 4 ) -time algorithm for computing optimal search trees with two-way comparisons. The only previous solution to this problem, by Anderson et al., has the same running time but is significantly more complicated and is restricted to the variant where only successful queries are allowed. Our algorithm extends directly to solve the standard full variant of the problem, which also allows unsuccessful queries and for which no polynomial-time algorithm was previously known. The correctness proof of our algorithm relies on a new structural theorem for two-way-comparison search trees.

The {\em Maximal} points in a set S are those that aren't {\em dominated} by any other point in S. Such points arise in multiple application settings in which they are called by a variety of different names, e.g., maxima, Pareto optimums, skylines. Because of their ubiquity, there is a large literature on the {\em expected} number of maxima in a set S of n points chosen IID from some distribution. Most such results assume that the underlying distribution is uniform over some spatial region and strongly use this uniformity in their analysis. This work was initially motivated by the question of how this expected number changes if the input distribution is perturbed by random noise. More specifically, let Ballp denote the uniform distribution from the 2-d unit Lp ball, delta Ballq denote the 2-d Lq-ball, of radius delta and Ballpq be the convolution of the two distributions, i.e., a point v in Ballp is reported with an error chosen from delta Ballq. The question is how the expected number of maxima change as a function of delta. Although the original motivation is for small delta the problem is well defined for any delta and our analysis treats the general case. More specifically, we study, as a function of n,δ, the expected number of maximal points when the n points in S are chosen IID from distributions of the type Ballpq where p,q in {1,2,infty} for delta > 0 and also of the type Ballp infty-q, where q in [1,infty) for delta > 0.

Huffman Codes are "optimal" Fixed-to-Variable (FV) codes if every source symbol can only be encoded by one codeword. Relaxing this constraint permits constructing better FV codes. More specifically, recent work has shown that AIFV codes can beat Huffman coding. AIFV codes construct a set of different coding trees between which the code alternates and are only "almost instantaneous" (AI). This means that decoding a word might require a delay of a finite number of bits. Current algorithms for constructing optimal AIFV codes are iterative processes that construct progressively "better sets" of code trees. The processes have been proven to finitely converge to the optimal code but with no known bounds on the convergence time. This paper derives a geometric interpretation of the space of AIFV codes. This permits the development of new polynomially time-bounded iterative procedures for constructing optimal AIFV codes. For the simplest case we show that a binary search procedure can replace the current iterative process. For the more complicated cases we describe how to frame the problem as a linear programming problem with an exponential number of constraints but a polynomial time separability oracle. This permits using the Grotschel, Lovasz and Schrijver ellipsoid method to solve the problem in a polynomial number of steps.

An optimal binary search tree for an access sequence on elements is a static tree that minimizes the total search cost. Constructing perfectly optimal binary search trees is expensive so the most efficient algorithms construct almost optimal search trees. There exists a long literature of constructing almost optimal search trees dynamically, i.e., when the access pattern is not known in advance. All of these trees, e.g., splay trees and treaps, provide a multiplicative approximation to the optimal search cost. In this paper we show how to maintain an almost optimal weighted binary search tree under access operations and insertions of new elements where the approximation is an additive constant. More technically, we maintain a tree in which the depth of the leaf holding an element $e_i$ does not exceed $\min(\log(W/w_i),\log n)+O(1)$ where $w_i$ is the number of times $e_i$ was accessed and $W$ is the total length of the access sequence. Our techniques can also be used to encode a sequence of $m$ symbols with a dynamic alphabetic code in $O(m)$ time so that the encoding length is bounded by $m(H+O(1))$, where $H$ is the entropy of the sequence. This is the first efficient algorithm for adaptive alphabetic coding that runs in constant time per symbol.

Dynamic Flows were introduced by Ford and Fulkerson in 1958 to model flows over time. They define edge capacities to be the total amount of flow that can enter an edge in one time unit. Each edge also has a length, representing the time needed to traverse it. Dynamic Flows have been used to model many problems including traffic congestion, hop-routing of packets and evacuation protocols in buildings. While the basic problem of moving the maximal amount of supplies from sources to sinks is polynomial time solvable, natural minor modifications can make it NP-hard. One such modification is that flows be confluent, i.e., all flows leaving a vertex must leave along the same edge. This corresponds to natural conditions in, e.g., evacuation planning and hop routing. We investigate the single-sink Confluent Quickest Flow problem. The input is a graph with edge capacities and lengths, sources with supplies and a sink. The problem is to find a confluent flow minimizing the time required to send supplies to the sink. Our main results include: a) Logarithmic Non-Approximability: Directed Confluent Quickest Flows cannot be approximated in polynomial time with an O(\log n) approximation factor, unless P=NP. b) Polylogarithmic Bicriteria Approximations: Polynomial time (O(\log^8 n), O(\log^2 \kappa)) bicritera approximation algorithms for the Confluent Quickest Flow problem where \kappa is the number of sinks, in both directed and undirected graphs. Corresponding results are also developed for the Confluent Maximum Flow over time problem. The techniques developed also improve recent approximation algorithms for static confluent flows.

Let G = (V, E) be a graph modelling a building or road network in which edges have-both travel times (lengths) and capacities associated with them. An edge’s capacity is the number of people that can enter that edge in a unit of time. In emergencies, people evacuate towards the exits. If too many people try to evacuate through the same edge, congestion builds up and slows down the evacuation. Graphs with both lengths and capacities are known as Dynamic Flow networks. An evacuation plan for G consists of a choice of exit locations and a partition of the people at the vertices into groups, with each group evacuating to the same exit. The evacuation time of a plan is the time it takes until the last person evacuates. The k-sink evacuation problem is to provide an evacuation plan with k exit locations that minimizes the evacuation time. It is known that this problem is NP-Hard for general graphs but no polynomial time algorithm was previously known even for the case of G a tree. This paper presents an O(nk^2 log^5 n) algorithm for the k-sink evacuation problem on trees, which can also be applied to a more general class of problems.

We give a polynomial-time approximation scheme for the generalization of Huffman coding in which codeword letters have nonuniform costs (as in Morse code, where the dash is twice as long as the dot). The algorithm computes a $(1+\epsilon)$-approximate solution in time $O(n+f(\epsilon)\log^3n)$, where $n$ is the input size.

The “state-of-the-art” in length-limited Huffman coding (LLHC) algorithms is theΘ(nD)-time,Θ(n)-space one of Hirschberg and Larmore, wherenis the size of the code andD≤nis the length restriction on the codewords. This is a very clever, very problem specific, technique. This paper presents a simple dynamic-programming (DP) method that solves the problem with the same time and space bounds. The fact that there was anΘ(nD) time DP algorithm was previously known; it is a straightforward DP with theMongeproperty (which permits an order of magnitude speedup). It was not interesting, though, because it also requiredΘ(nD) space. The main result of this paper is thetechniquedeveloped for reducing the space. It is quite simple and applicable to many other problems modeled by DPs with the Monge property. This is illustrated with examples from web-proxy design and wireless mobile paging.

Given a probability distribution over a set of n words to be transmitted, the Huffman Coding problem is to find a minimal-cost prefix free code for transmitting those words. The basic Huffman coding problem can be solved in O(n log n) time but variations are more difficult. One of the standard techniques for solving these variations utilizes a top-down dynamic programming approach. In this paper we show that this approach is amenable to dynamic programming speedup techniques, permitting a speedup of an order of magnitude for many algorithms in the literature for such variations as mixed radix, reserved length and one-ended coding. These speedups are immediate implications of a general structural property that permits batching together the calculation of many DP entries.

There exist several general techniques in the literature for speeding up naive implementations of dynamic programming. Two of the best known are the Knuth-Yao quadrangle inequality speedup and the SMAWK algorithm for finding the row-minima of totally monotone matrices. Although both of these techniques use a quadrangle inequality and seem similar, they are actually quite different and have been used differently in the literature. In this article we show that the Knuth-Yao technique is actually a direct consequence of total monotonicity. As well as providing new derivations of the Knuth-Yao result, this also permits to solve the Knuth-Yao problem directly using the SMAWK algorithm. Another consequence of this approach is a method for solving online versions of problems with the Knuth-Yao property. The online algorithms given here are asymptotically as fast as the best previously known static ones. For example, the Knuth-Yao technique speeds up the standard dynamic program for finding the optimal binary search tree of n elements from Θ( n 3 ) down to O ( n 2 ), and the results in this article allow construction of an optimal binary search tree in an online fashion (adding a node to the left or the right of the current nodes at each step) in O ( n ) time per step.

Abstract In this article, we develop a method to count the number of spanning trees in certain classes of double fixed‐step loop networks with nonconstant steps. More specifically our technique finds the number of spanning trees in$ \overrightarrow{C} _{n}^{p,q} $ , the double fixed‐step loop network withnvertices and jumps of sizepandq, whenn=d1m, andq=d2m+pwhered1,d2, andpare arbitrary parameters andmis a variable. © 2008 Wiley Periodicals, Inc. NETWORKS, 2008

There is a large literature devoted to the problem of finding an optimal (min-cost) prefix-free code with an unequal letter-cost encoding alphabet of size. While there is no known polynomial time algorithm for solving it optimally, there are many good heuristics that all provide additive errors to optimal. The additive error in these algorithms usually depends linearly upon the largest encoding letter size.

A mobile user is roaming in a zone composed of N cells in a cellular network system. When a call to the mobile user arrives, the system pages the mobile user in these cells since it never reports its location unless it leaves the zone. The N cells are associated with a probability vector (p1, ...,pN) where piis the probability that the mobile user resides in the ith cell and all the probabilities are independent. A delay constraint paging strategy must find the mobile user within D (1 les D les N) paging rounds; in each round a subset of the N cells is paged. The goal is to minimize the expected number of paged cells until the mobile user is found. Solutions based on dynamic programming that yield optimal strategies are known. The running time of the known implementations is Theta(N2D). Our first contribution is to improve the running time to Theta(ND) by proving that the dynamic programming recursive formulation satisfies the Monge property, permitting us to use various dynamic programming speedup techniques. A Theta(N) heuristic solution is also known. Our second contribution is a heuristic whose running time is Theta(N log D). Our heuristic outperforms the known heuristic while running faster for D << N. We compare the non-optimal heuristics with the optimal solution demonstrating the tradeoff between optimality and running time efficiency of various solutions.

Abstract We investigate the two‐median problem on a mesh withMcolumns andNrows (M≥N), under the Manhattan (L1) metric. We derive exact algorithms with respect tom,n, andr, the number of columns, rows, and vertices, respectively, that contain requests. Specifically, we give anO(mn2logm) time,O(r) space algorithm for general (nonuniform) meshes (assumingm≥n). For uniform meshes, we give two algorithms both usingO(MN) space. One is anO(MN2) time algorithm, while the other is an algorithm running inO(MNlogN) time with high probability and inO(MN2) time in the worst case assuming the weights are independent and identically distributed random variables satisfying certain natural conditions. These improve upon the previously best‐known algorithm that runs inO(mn2r) time. © 2007 Wiley Periodicals, Inc. NETWORKS, Vol. 49(3), 226–233 2007

Let /spl lscr/ /sub 1/,/spl lscr/ /sub 2/,...,/spl lscr/ /sub n/ be a (possibly infinite) sequence of nonnegative integers and /spl Sigma/ some D-ary alphabet. The Kraft-inequality states that /spl lscr/ /sub 1/,/spl lscr/ /sub 2/,...,/spl lscr/ /sub n/ are the lengths of the words in some prefix (free) code over /spl Sigma/ if and only if /spl Sigma//sub i=1//sup n/D/sup -/spl lscr/ i//spl les/1. Furthermore, the code is exhaustive if and only if equality holds. The McMillan inequality states that if /spl lscr/ /sub n/ are the lengths of the words in some uniquely decipherable code, then the same condition holds. In this paper we examine how the Kraft-McMillan inequality conditions for the existence of a prefix or uniquely decipherable code change when the code is not only required to be prefix but all of the codewords are restricted to belong to a given specific language L. For example, L might be all words that end in a particular pattern or, if /spl Sigma/ is binary, might be all words in which the number of zeros equals the number of ones.

We present an algorithm to reconstruct a collection of disjoint smooth closed curves from n noisy samples. Our noise model assumes that the samples are obtained by first drawing points on the curves according to a locally uniform distribution followed by a uniform perturbation of each point in the normal direction with a magnitude smaller than the minimum local feature size. The reconstruction is faithful with a probability that approaches 1 as n increases.We expect that our approach can lead to provable algorithms under less restrictive noise models and for handling non-smooth features.

Summary form only given. Two classes of constrained systems are discussed: the generation of read/write isolated memory and two-dimensional run length limited constrained systems. The procedure on how to use the recurrence relations on the A/sub n/ and '1'-counting to derive recurrence inequalities on the /spl lambda//sub n/ is shown. This procedure has been found to yield good upper and lower bounds on the capacities of the constraints. Contrary to the situation in most other known constraints. It is observed that this technique provides much better bounds than the simple brute force method.

The maximum residual energy path (MREP) routing has been shown an effective routing scheme for energy conservation in a battery wireless network. Past studies on MREP are based on the assumption that the transmitting node consumes power, but the receiving node does not. This assumption is false if acknowledgement is required, or if the ad hoc network has deployed the energy-conservation mode (sleeping mode). When backward energy consumption is present in transmission (i.e. the receiving end consumes energy), finding an MRE path that has enough energy for finishing the transmission has become NP-hard. We show in this paper a Dijkstra-like heuristic algorithm for finding the optimal MRE path. The new algorithm guarantees that once a path is found, it will have enough energy to finish the transmission task, while the original MREP algorithm, ignoring the backward energy costs, cannot guarantee that. We also show another routing technique that can extend the system life. The technique works for both MREP-based routing schemes.

(MATH) It is well known that the complexity, i.e., the number of vertices, edges and faces, of the 3-dimensional Voronoi diagram of n points can be as bad as Θ( n 2 ). Interest has recently arisen as to what happens, both in deterministic and probabilistic situations, when the 3-dimensional points are restricted to lie on the surface of a 2-dimensional object. In this paper we consider the situation when the points are drawn from a 2-dimensional Poisson distribution with rate n over a fixed union of triangles in $\myRe^3.$ We show that with high probability the complexity of their Voronoi diagram is $\Ot n .(MATH) This implies, for example, that the complexity of the Voronoi diagram of points chosen from the surface of a general fixed polyhedron in $\myRe 3 will also be $\Ot n with high probability.

Summary form only given. A serial binary (0,1) memory is read isolated if no two consecutive positions in the memory may both store 1's; it is write isolated if no two consecutive positions in the memory can be changed during rewriting. Such restrictions have arisen in the contexts of asymmetric error-correcting ternary codes and of rewritable optical discs etc. A read/write isolated memory is a binary, linearly ordered, rewritable storage medium that obeys both the read and write constraints. We introduce new compressed matrix techniques. The new contribution of this paper is to show that it is possible to take advantage of the recursive structures of the transfer matrices to (i) build other matrices of the same size whose eigenvalues yield provably better bounds or (ii) build smaller matrices whose largest eigenvalues are the same as those of the transfer matrices. Thus, it is possible to get the same bounds with less computation. We call these approaches compressed matrix techniques. While technique (ii) was specific to this problem technique (i) is applicable to many other two-dimensional constraint problems.

(MATH) In the standard Huffman coding problem, one is given a set of words and for each word a positive frequency. The goal is to encode each word w as a codeword c(w) over a given alphabet. The encoding must be prefix free (no codeword is a prefix of any other) and should minimize the weighted average codeword size Σw freq w, |c(w)|. The problem has a well-known polynomial-time algorithm due to Huffman [15].Here we consider the generalization in which the letters of the encoding alphabet may have non-uniform lengths. The goal is to minimize the weighted average codeword length Σw freq (w) cost(c(w)), where cost s is the sum of the (possibly non-uniform) lengths of the letters in s. Despite much previous work, the problem is not known to be NP-hard, nor was it previously known to have a polynomial-time approximation algorithm. Here we describe a polynomial-time approximation scheme (PTAS) for the problem.

In this paper we discuss the problem of constructing minimum-cost, prefix-free codes for equiprobable words under the assumption that all codewords are restricted to belonging to an arbitrary language L. We examine how, given certain types of L, the structure of the minimum-cost code changes as n, the number of codewords, grows.

Anderson and Kuhn (1997) described an attack against tamper-resistant devices wherein a secret key stored in EEPROM is compromised using a simple and low-cost attack. The attack consists of setting bits in the EEPROM using low-cost probes and observing the effect on the output of the device. These attacks are extremely general, as they apply to virtually any cryptosystem. The objective of the present work is to explore cryptographic techniques with the goal of raising the cost (in terms of time and money) of carrying out the EEPROM modification attack by Class I attackers, at least to a point where it is as prohibitive as the cost of purchasing more expensive equipment. We propose the m-permutation protection scheme in which the key will be encoded in a special way and burned into the EEPROM of the device. To attack the scheme, the attacker needs to be able to solve for K in the equation K=/spl oplus//sub i=1//sup m/P/sub i/ in which P/sub i/'s are unknown. It is observed that the m-permutation protection scheme does not distribute the key K uniformly. Analysis shows that m=3 or m=5 are already good enough practically to provide strong security if the encoding is done properly and that m>5 may not give significant improvement to the security of the scheme.

We discuss the problem of efficiently constructing minimum-cost binary prefix-free codes having the property that each codeword ends with a "1".

Web caching or web proxy has been considered as the prime vehicle of coping with the ever-increasing demand for information retrieval over the Internet, the WWW being a typical example. Existing work on web proxy has primarily focused on content based caching; relatively less attention has been given to the development of proper placement strategies for the potential web proxies in the Internet. In this paper, we argue that the placement of web proxies is critical to the performance and further investigates the optimal placement policy of web proxies for a target web server in the Internet. The objective is to optimize a given performance measure for the target web server subject to system resources and traffic pattern. Specifically, we are interested in finding the optimal placement of multiple web proxies (M) among potential sites (N) under a given traffic pattern. We show this can be modeled a dynamic programming problem. We further obtain the optimal solution for the tree topology using O(N/sup 3/M/sup 2/) time.

We describe a new randomized data structure, the sparse partition, for solving the dynamic closest-pair problem. Using this data structure the closest pair of a set of n points in D-dimensional space, for any fixed D, can be found in constant time. If a frame containing all the points is known in advance, and if the floor function is available at unit cost, then the data structure supports insertions into and deletions from the set in expected O(log n) time and requires expected O(n) space. This method is more efficient than any deterministic algorithm for solving the problem in dimension D > 1. The data structure can be modified to run in O(log 2 n) expected time per update in the algebraic computation tree model. Even this version is more efficient than the best currently known deterministic algorithm for D > 2. Both results assume that the sequence of updates is not determined in any way by the random choices made by the algorithm.

We consider the problem of constructing prefix-free codes of minimum cost when the encoding alphabet contains letters of unequal length. The complexity of this problem has been unclear for thirty years with the only algorithm known for its solution involving a transformation to integer linear programming. We introduce a new dynamic programming solution to the problem. It optimally encodes n words in O(n/sup C+2/) time, if the costs of the letters are integers between 1 and C. While still leaving open the question of whether the general problem is solvable in polynomial time, our algorithm seems to be the first one that runs in polynomial time for fixed letter costs.

We consider the following variant of Huffman coding in which the costs of the letters, rather than the probabilities of the words, are nonuniform “Given an alphabet of r letters of nonuniform length, find a minimum-average-length prefix free set of n codewords over the alphabet”; equivalently, “Find an optimal r-ary search tree with n leaves, where each leaf is accessed with equal probability but the cost to descend from a parent to its ith child depends on i.” We show new structural properties of such codes, leading to an $O(n\log ^2 r)$ time algorithm for finding them, This new algorithm is simpler and faster than the best previously known $O(nr\min \{ \log n,r\} )$ time algorithm, due to Perl Garey, and Even [J. Assoc. Comput. Mach., 22 (1975), pp. 202–214].

This paper is concerned with a simple, rather intuitive preprocessing step that is likely to improve the average-case performance of any convex hull algorithm. For n points randomly distributed in the unit square, we show that a simple linear pass through the points can eliminate all but Ο(√n) of the points by showing that a simple superset of the remaining points has size c√n + ο(√n). We give a full implementation of the method, which should be useful in any practical application for finding convex hulls. Most of the paper is concerned with an analysis of the number of points eliminated by the procedure, including derivation of an exact expression for c. Extensions to higher dimensions are also considered.