13293366
Improved bandwidth approximation for trees
A linear arrangement of an n-vertex graph G = (V, E) is a one-one mapping f of the vertex set V onto the set In] = {0, 1 , . . . , n 1}. The bandwidth of this linear arrangement is the maximum distance between the images of the endpoints of any edge in E(G). When the input graph G is a tree, the best known approximation algorithm for the minimum bandwidth linear arrangement (which is based on the principle of volume respecting embeddings) outputs a linear arrangement which has bandwidth within O(log 3 n) of the optimal bandwidth. In this paper, we present a simple randomized O(log 2 n lov~-n)-approximation algorithm for bandwidth minimization on trees.
100323
Tree based MPLS routing
MPLS (MultiProtocol Label Switching) is a new technology proposed by the IETF [4,10] for network routing, and is being increasingly deployed by the largest Internet service providers. The MPLS technology differs from conventional network protocols in a crucial way: instead of reading the entire packet header at all switching points, the analysis of the packet header is done just once, when the packet header is assigned a stack of labels, and thenceforth, each switching point or router just gets to look at the label at the top of the stack (and the ingress edge), and based only on this information, it has to make a decision about the next-hop node [17,16]. In another departure from conventional routing and in particular from IP source routing, where the entire packet route is explicitly put in the header and popped off along the route, the router can not only pop the top label, it can push other labels on top of the stack.The two parameters of interest in designing MPLS routing protocols are the number of labels used, and the depth of the stack used for routing. Clearly, both cannot be simultaneously minimized, and there is often an interesting trade-off between label size and stack depth: it is obvious that if k labels are used, one must have a stack depth of logk n.In fact, it was not known whether this bound could be achieved even for trees; the best stack depth previously achieved with a constant number of labels was O(log2 n). In this paper, we show that one can indeed get asymptotically optimal upper bounds and route on trees using k labels and a maximum stack depth of O(logk n), and that this trade-off can be achieved using a simpler and more intuitive protocol than the one given in [9]. These tree-routing ideas are then shown to give better routing protocols for planar graphs as well. In particular, we show how to route along near-shortest paths (of length at most (1 + ε) times the shortest-path) with O(log2 n/ε) labels and logarithmic stack depth. We also apply them to graphs with smaller separators, including most large ISP networks.
37922436
Improved Bandwidth Approximation for Trees and Chordal Graphs
A linear arrangement of an n-vertex graph G=(V,E) is a one?one mapping f of the vertex set V onto the set n]={0,1,?,n?1}. The bandwidth of this linear arrangement is the maximum difference between the images of the endpoints of any edge in E(G). When the input graph G is a tree, the best known approximation algorithms for the minimum bandwidth linear arrangement (which are based on the principle of volume respecting embeddings) output a linear arrangement which has bandwidth within O(log3n) of the optimal bandwidth. In this paper, we present a simple randomized O(log2.5n)-approximation algorithm for bandwidth minimization on trees. We also show that a close variant of this algorithm gives a similar performance guarantee for chordal graphs.
11033759
Oblivious network design
Consider the following network design problem: given a network <i>G = (V, E)</i>, source-sink pairs {<i>s</i><inf><i>i</i></inf>, <i>t</i><inf><i>i</i></inf>} arrive and desire to send a unit of flow between themselves. The cost of the routing is this: if edge <i>e</i> carries a total of <i>f</i><inf><i>e</i></inf> flow (from all the terminal pairs), the cost is given by Σ <inf><i>e</i></inf><i>l</i>(<i>f</i><inf><i>e</i></inf>), where <i>l</i> is some concave cost function; the goal is to minimize the total cost incurred. However, we want the routing to be <i>oblivious</i>: when terminal pair {<i>s</i><inf><i>i</i></inf>, <i>t</i><inf><i>i</i></inf>} makes its routing decisions, it does not know the current flow on the edges of the network, nor the identity of the other pairs in the system. Moreover, it does not even know the identity of the function <i>l</i>, merely knowing that <i>l</i> is a concave function of the total flow on the edge. How should it (obliviously) route its one unit of flow? Can we get competitive algorithms for this problem?In this paper, we develop a framework to model <i>oblivious network design</i> problems (of which the above problem is a special case), and give algorithms with poly-logarithmic competitive ratio for problems in this framework (and hence for this problem). Abstractly, given a problem like the one above, the solution is a multicommodity flow producing a "load" on each edge of <i>L</i><inf><i>e</i></inf> = <i>l</i>(<i>f</i><inf>1</inf>(<i>e</i>),<i>f</i><inf>2</inf>(<i>e</i>), ..., <i>f</i><inf><i>k</i></inf>(<i>e</i>)), and the total cost is given by an "aggregation function" agg (<i>L</i><inf><i>e</i>1</inf>,...,<i>L</i><inf><i>em</i></inf>) of the loads of all edges. Our goal is to develop oblivious algorithms that approximately minimize the total cost of the routing, knowing the aggregation function agg, but merely knowing that <i>l</i> lies in some class C, and having no other information about the current state of the network. Hence we want algorithms that are simultaneously "function-oblivious" as well as "traffic-oblivious".The aggregation functions we consider are the max and σ objective functions, which correspond to the well-known measures of <i>congestion</i> and <i>total cost</i> of a network; in this paper, we prove the following:• If the aggregation function is Σ, we give an oblivious algorithm with <i>O</i>(log<sup>2</sup> <i>n</i>) competitive ratio whenever the load function <i>l</i> is in the class of <i>monotone sub-additive functions</i>. (Recall that our algorithm is also "function-oblivious"; it works whenever each edge has a load function <i>l</i> in the class.)• For the case when the aggregation function is max, we give an oblivious algorithm with <i>O</i>(log<sup>2</sup> <i>n</i> log log <i>n</i>) competitive ratio, when the load function <i>l</i> is a <i>norm;</i> we also show that such a competitive ratio is not possible for general sub-additive functions.These are the first such general results about oblivious algorithms for network design problems, and we hope the ideas and techniques will lead to more and improved results in this area.
411060
Approximating unique games
The UNIQUE GAMES problem is the following: we are given a graph <i>G</i> = (<i>V, E</i>), with each edge <i>e</i> = (<i>u, v</i>) having a weight <i>w</i><inf><i>e</i></inf> and a permutation π<inf><i>uv</i></inf> on [<i>k</i>]. The objective is to find a labeling of each vertex <i>u</i> with a label <i>f</i><inf><i>u</i></inf> ∈ [<i>k</i>] to minimize the weight of unsatisfied edges---where an edge (<i>u, v</i>) is <i>satisfied</i> if <i>f</i><inf><i>v</i></inf> = π<inf><i>uv</i></inf>(<i>f</i><inf><i>u</i></inf>).The <i>Unique Games Conjecture</i> of Khot [8] essentially says that for each ε > 0, there is a <i>k</i> such that it is NP-hard to distinguish instances of Unique games with (1-ε) satisfiable edges from those with only ε satisfiable edges. Several hardness results have recently been proved based on this assumption, including optimal ones for Max-Cut, Vertex-Cover and other problems, making it an important challenge to prove or refute the conjecture.In this paper, we give an <i>O</i>(log <i>n</i>)-approximation algorithm for the problem of minimizing the number of unsatisfied edges in any Unique game. Previous results of Khot [8] and Trevisan [12] imply that if the optimal solution has OPT = ε<i>m</i> unsatisfied edges, semidefinite relaxations of the problem could give labelings with min {<i>k</i><sup>2</sup>ε<sup>1/5</sup>, (ε log <i>n</i>)<sup>1/2</sup>}<i>m</i> unsatisfied edges. In this paper we show how to round a LP relaxation to get an <i>O</i>(log <i>n</i>)-approximation to the problem; i.e., to find a labeling with only <i>O</i>(ε<i>m</i> log <i>n</i>) = <i>O</i>(OPT log <i>n</i>) unsatisfied edges.
47205636
Approximation Algorithms for the Unsplittable Flow Problem
We present approximation algorithms for the unsplittable flow problem (UFP) on undirected graphs. As is standard in this line of research, we assume that the maximum demand is at most the minimum capacity. We focus on the non-uniform capacity case in which the edge capacities can vary arbitrarily over the graph. Our results are: - For undirected graphs we obtain a O(??-1 log2 n) approximation ratio, where n is the number of vertices, ? the maximum degree, and ? the expansion of the graph. Our ratio is capacity independent and improves upon the earlier O(??-1(cmax/cmin) log n) bound [15] for large values of cmax/cmin. Furthermore, if we specialize to the case where all edges have the same capacity, our algorithm gives an O(??-1 log n) approximation, which matches the performance of the best-known algorithm [15] for this special case. - For certain strong constant-degree expanders considered by Frieze [10] we obtain an O(? log n) approximation for the uniform capacity case, improving upon the current O(log n) approximation. - For UFP on the line and the ring, we give the first constant-factor approximation algorithms. Previous results addressed only the uniform capacity case. - All of the above results improve if the maximum demand is bounded away from the minimum capacity.Our results are based on randomized rounding followed by greedy alteration and are inspired by the use of this idea in recent work [21, 9].
6254649
Disjunctive Image Computation for Embedded Software Verification
Finite state models generated from software programs have unique characteristics that are not exploited by existing model checking algorithms. In this paper, we propose a novel disjunctive image computation algorithm and other simplifications based on these characteristics. Our algorithm divides an image computation into a disjunctive set of easier ones that can be performed in isolation. Hypergraph partitioning is used to minimize the number of live variables in each disjunctive component. We use the live variables to simplify transition relations and reachable state subsets. Our experiments on a set of real-world C programs show that the new algorithm achieves orders-of-magnitude performance improvement over the best known conjunctive image computation algorithm
5331854
On the Scalable Computation of Large Sets of Integrals
We consider efficient strategies for the parallel and distributed computation of large sets of multivariate integrals. These arise in many applications such as computational chemistry, high energy physics and finite element problems. We use a hierarchical architecture which is highly scalable and allows parallelization not only at the domain level but also at the integral level. We present experimental results on a family of parametrized integrals and show that our approach leads to an efficient scalable load balanced algorithm. The methods are easily applicable to other areas where a large number of problems need to be solved efficiently on a parallel and distributed system.
17006088
An Efficient MAP Classifier for Sensornets
The classification phase is computationally intensive and frequently recurs in tracking applications in sensor networks. Most related work uses traditional signal processing classifiers, such as Maximum A Posterior (MAP) classifier. Naive formulations of MAP are not feasible for resource constraint sensornet nodes. In this paper, we study computationally efficient methods for classification. We propose to use one-sided Jacobi iterations for eigen value decomposition of the covariance matrices, the inverse of which are needed in MAP classifier. We show that this technique greatly simplifies the execution of MAP classifier and makes it a feasible and efficient choice for sensornet applications.
14357490
A Distributed Self-Stabilizing Algorithm for Finding a Connected Dominating Set in a Graph
A connected dominating set of a graph G is a set of nodes of G such that every node in G is either in the set or is adjacent to some node in the set, and the graph induced by the elements of the set is connected. Connected dominating sets have major applications in routing in wireless ad-hoc networks. In this paper, we present a distributed self-stabilizing algorithm for finding a connected dominating set of a graph. Starting from an arbitrary initial state, the algorithm finds a connected dominating set in O(N^2) time, where N is the number of nodes. We also show detailed simulation results to indicate that in practice, the algorithm finds small-sized connected dominating sets in a short time.
16442037
Handwritten Bank Check Recognition Of Courtesy Amounts
In spite of rapid evolution of electronic techniques, a number of large-scale applications continue to rely on the use of paper as the dominant medium. This is especially true for processing of bank checks. This paper examines the issue of reading the numerical amount field. In the case of checks, the segmentation of unconstrained strings into individual digits is a challenging task because of connected and overlapping digits, broken digits, and digits that are physically connected to pieces of strokes from neighboring digits. The proposed architecture involves four stages: segmentation of the string into individual digits, normalization, recognition of each character using a neural network classifier, and syntactic verification. Overall, this paper highlights the importance of employing a hybrid architecture that incorporates multiple approaches to provide high recognition rates.