2125509
Improved results for directed multicut
We give a simple algorithm for the Minimum Directed Multicut problem, and show that it gives an <i>O</i>(√<i>n</i>)-approximation. This improves on the previous approximation guarantee of <i>O</i>(√<i>n</i> log <i>k</i>) of Cheriyan, Karloff and Rabani [1], which was obtained by a more sophisticated algorithm.
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.
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.
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.
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.
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].
2250792
Revising TimeGraph-II
TimeGraph-II is a system for efficient point-based temporal reasoning, developed by Schubert, Gerevini, and collaborators. For our purposes, temporal relations are represented in a directed acyclic graph, where vertices represent time points and directed edges are labelled ≤ or <, with no redundant edges. The graph is partitioned into a set of chains, supported by a metagraph data structure. Temporal reasoning can be carried out efficiently: reasoning within a chain takes constant time; reasoning between chains is less efficient, but is determined by a graph (the metagraph) significantly smaller than the original. We suggest two enhancements to TimeGraph-II, both of which lead to improvements in the original approach. First, the original approach does not consider updates to the structure. We show that additions to chains can be accomplished very efficiently, with manageable degradation in reasoning (O(log n) in both cases). Second, we argue that basing the representation on trees rather than chains leads to a strictly more powerful reasoner. More queries can be answered in constant time, and at the same time, for general queries, the size of the metagraph is decreased.
34084077
A Spot Pricing Framework For Pricing Intra-Domain Assured Bandwidth Services
The Internet today offers primarily a best-effort service. Research and technology development efforts are currently underway to allow the provisioning of better than best-effort quality of service assurances. In this article, we develop a spot pricing framework for expected bandwidth guaranteed Internet service contracts on a single domain. A nonlinear pricing model that maximizes the total surplus with cost constraints forms the basis for the framework. The spot price process is obtained for different demand profiles of the customer-base and demand arrival characteristics. Simulation modeling and analysis is employed to implement the pricing framework and analyze the price process under different market conditions and changes due to network failures. The framework when implemented at access or exchange points of different service provider domains will provide assured bandwidth for inter-domain traffic.
209133
Computing planar intertwines
The proof of Wagner's conjecture by N. Robertson and P. Seymour gives a finite description of any family of graphs which is closed under the minor ordering, called the obstructions of the family. Since the intersection and the union of two minor closed graph families are again a minor closed graph family, an interesting question is that of computing the obstructions of the new family given the obstructions for the original two families. It is easy to compute the obstructions of the intersection, but, until very recently, it was an open problem to compute the obstructions of the union. It is shown that if the original families are planar, then the obstructions of the union are no larger than n to the O(n/sup 2/) power, where n is the size of the largest obstruction of the original family.<<ETX>>
492959
On the Complements of Partial k-Trees
We introduce new techniques for studying the structure of partial k-trees. In particular, we show that the complements of partial k-trees provide an intuitively-appealing characterization of partial k-tree obstructions. We use this characterization to obtain a lower bound of 2Ω(k log k) on the number of obstructions, significantly improving the previously best-known bound of 2Ω(√k). Our techniques have the added advantage of being considerably simpler than those of previous authors.
8665183
Dynamic detection and removal of inactive clauses in SAT with application in image computation
In this paper, we present a new technique for the efficient dynamic detection and removal of inactive clauses, i.e. clauses that do not affect the solutions of interest of a Boolean satisfiability (SAT) problem. The algorithm is based on the extraction of gate connectivity information during generation of the Boolean formula from the circuit, and its use in the inner loop of a branch-and-bound SAT algorithm. The motivation for this optimization is to exploit the circuit structure information, which can be used to find unobservable gates at circuit outputs under dynamic conditions. It has the potential to speed up all applications of SAT in which the SAT formula is derived from a logic circuit. In particular, we find that it has considerable impact on an image computation algorithm based on SAT. We present practical results for benchmark circuits which show that the use of this optimization consistently improves the performance for reachability analysis, in some cases enabling the prototype tool to reach more states than otherwise possible.