854648
Approximation algorithms for low-distortion embeddings into low-dimensional spaces
We present several approximation algorithms for the problem of embedding metric spaces into a line, and into the two-dimensional plane. Among other results, we give an O(√n)-approximation algorithm for the problem of finding a line embedding of a metric induced by a given unweighted graph, that minimizes the (standard) multiplicative distortion. We give an improved Õ(n1/3) approximation for the case of metrics generated by unweighted trees. This is the first result of this type.
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.
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.
18838099
Infrastructure Leasing Problems
Consider the following Steiner Tree leasing problem. Given a graph G= (V,E) with root r, and a sequence of terminal sets D t i¾? Vfor each day ti¾? [T]. A feasible solution to the problem is a set of edges E t for each tconnecting D t to r. Instead of obtaining edges for a single day at a time, or for infinitely long (both of which give Steiner tree problems), we leaseedges for say, { a day, a week, a month, a year}. Naturally, leasing an edge for a longer period costs less per unit of time. What is a good leasing strategy? In this paper, we give a general approach to solving a wide class of such problems by showing a close connection between deterministic leasing problems and problems in multistage stochastic optimization. All our results are in the offline setting.
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.
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.
1782369
Designing and executing scientific workflows with a programmable integrator
MOTIVATION
As in many other fields of science, computational methods in molecular biology need to intersperse information access and algorithm execution in a computational workflow. Users often find difficulties when transferring data between data sources and applications. In most cases there is no standard solution for workflow design and execution and tailored scripting mechanisms are implemented in a case by case basis.


RESULTS
In this paper, we present a general purpose 'programmable integrator' that can access information from a variety of sources in a coordinated manner. Its usefulness in complex bioinformatics applications is claimed and supported by some application examples.


AVAILABILITY
Tools are freely available to non-profit educations and research institutions. Usage by commercial organizations requires a license agreement. Software requirements: Java v1.3 (http://java.sun.com), Xerces XML Parser (http://xml.apache.org/xerces-j) and Kweelt implementation of XQuery (http://kweelt.sourceforge.net/).
26737462
The Parallel Complexity of Tree Embedding Problems
Abstract The question of the sequential complexity of various tree embedding problems arises in the recent work of Robertson and Seymour on graph miners; here we consider the parallel complexity of such problems. In particular, we present two CREW PRAM algorithms: an O (log 3 n ) time randomized algorithm for determining whether there is a topological embedding of one rooted tree in another and an O (log 2 n log log n ) time deterministic algorithm for determining whether or not a rooted tree with a degree constraint is a minor of a general rooted tree. These algorithms are two examples of a general technique that can be used for solving other problems on trees.
14070074
Stream processing of XPath queries with predicates
We consider the problem of evaluating large numbers of XPath filters, each with many predicates, on a stream of XML documents. The solution we propose is to lazily construct a single deterministic pushdown automata, called the XPush Machine from the given XPath fllters. We describe a number of optimization techniques to make the lazy XPush machine more efficient, both in terms of space and time. The combination of these optimizations results in high, sustained throughput. For example, if the total number of atomic predicates in the filters is up to 200000, then the throughput is at least 0.5 MB/sec: it increases to 4.5 MB/sec when each fllter contains a single predicate.
3086074
An Exercise in Fault-Containment: Self-Stabilizing Leader Election
Self-stabilizing algorithms are designed to guarantee convergence to some desired stable state from arbitrary initial states arising out of an arbitrarily large number of faults. However, in a well-designed system, the simultaneous occurrence of a large number of faults is rare. It is therefore desirable to design algorithms that are not only self-stabilizing, but also have the ability to recover very fast from a bounded number of faults. As an illustration, we present a simple self-stabilizing leader election protocol that recovers in O(1) time from a state with a single transient fault on oriented rings. Only the faulty node and its two neighbors change their state during convergence to a stable state. Thus, the effect of a single fault is tightly contained around the fault. The technique for transforming a self-stabilizing algorithm into its fault-contained version is simple and general, and can be applied to other problems as well that satisfy certain properties.
42435460
Embeddings of k-connected graphs of pathwidth k
We present O(n^3) embedding algorithms (subgraph isomorphism and its generalizations) for classes of graphs of bounded pathwidth, where n is the number of vertices in the graph. These include the first polynomial-time algorithm for minor containment and the first O(n^c) algorithm (c a constant independent of k) for topological embedding of graphs from subclasses of partial k-trees, as well as an O(n^2) algorithm for subgraph isomorphism. Of independent interest are structural properties of k-connected graphs of bounded pathwidth on which our algorithms are based. We also describe special cases which reduce to various generalizations of string matching, permitting more efficient solutions. Finally, we describe n^k^+^O^(^1^) algorithms for solving these problems on arbitrary graphs of pathwidth at most k.