A New Approximation Algorithm for Finding Heavy Planar Subgraphs

We provide the first nontrivial approximation algorithm for MAXIMUM WEIGHT PLANAR SUBGRAPH, the NP-hard problem of finding a heaviest planar subgraph in an edge-weighted graph G . This problem has applications in circuit layout, facility layout, and graph drawing. No previous algorithm for MAXIMUM WEIGHT PLANAR SUBGRAPH had a performance ratio exceeding 1/3 , which is obtained by any algorithm that produces a maximum weight spanning tree in G . Based on the Berman—Ramaiyer Steiner tree algorithm, the new algorithm has performance ratio at least 1/3+1/72 and at most 5/12 . We also show that if G is complete and its edge weights satisfy the triangle inequality, then the performance ratio is at least 3/8 . Furthermore, we derive the first nontrivial performance ratio (7/12 instead of 1/2 ) for the NP-hard SC MAXIMUM WEIGHT OUTERPLANAR SUBGRAPH problem.     

Connectivity vs. reachability

We consider the problem of the relative complexity of the connectivity and reachability (s-t-connectivity) problems, in a model resembling the one used for graph properties. In our model an oracle answers queries about edge-induced subgraphs, and we count the number of queries made. The main result is that in order to determine whether t is reachable from s one has to ask Ω(n²) questions about the connectivity of edge-induced subgraphs. For non-adaptive strategies we show that questions are necessary for n≥6. Several other results are included.     

ℓ 2 2 Spreading Metrics for Vertex Ordering Problems

We design approximation algorithms for the vertex ordering problems Minimum Linear Arrangement, Minimum Containing Interval Graph, and Minimum Storage-Time Product, achieving approximation factors of $O(\sqrt{\log n}\log\log n)We design approximation algorithms for the vertex ordering problems Minimum Linear Arrangement, Minimum Containing Interval Graph, and Minimum Storage-Time Product, achieving approximation factors of O(?{logn}loglogn)O(\sqrt{\log n}\log\log n) , O(?{logn}loglogn)O(\sqrt{\log n}\log\log n) , and O(?{logT}loglogT)O(\sqrt{\log T}\log\log T) , respectively, the last running in time polynomial in T (T being the sum of execution times). The technical contribution of our paper is to introduce “ℓ ₂² spreading metrics” (that can be computed by semidefinite programming) as relaxations for both undirected and directed “permutation metrics,” which are induced by permutations of {1,2,…,n}. The techniques introduced in the recent work of Arora, Rao and Vazirani (Proc. of 36th STOC, pp. 222–231, 2004) can be adapted to exploit the geometry of such ℓ ₂² spreading metrics, giving a powerful tool for the design of divide-and-conquer algorithms. In addition to their applications to approximation algorithms, the study of such ℓ ₂² spreading metrics as relaxations of permutation metrics is interesting in its own right. We show how our results imply that, in a certain sense we make precise, ℓ ₂² spreading metrics approximate permutation metrics on n points to a factor of O(?{logn}loglogn)O(\sqrt{\log n}\log\log n) .     

A New Approximation Algorithm for Finding Heavy Planar Subgraphs

Abstract. We provide the first nontrivial approximation algorithm for MAXIMUM WEIGHT PLANAR SUBGRAPH, the NP-hard problem of finding a heaviest planar subgraph in an edge-weighted graph G . This problem has applications in circuit layout, facility layout, and graph drawing. No previous algorithm for MAXIMUM WEIGHT PLANAR SUBGRAPH had a performance ratio exceeding 1/3 , which is obtained by any algorithm that produces a maximum weight spanning tree in G . Based on the Berman—Ramaiyer Steiner tree algorithm, the new algorithm has performance ratio at least 1/3+1/72 and at most 5/12 . We also show that if G is complete and its edge weights satisfy the triangle inequality, then the performance ratio is at least 3/8 . Furthermore, we derive the first nontrivial performance ratio (7/12 instead of 1/2 ) for the NP-hard SC MAXIMUM WEIGHT OUTERPLANAR SUBGRAPH problem.     

Improved Approximation Algorithms for Label Cover Problems

In this paper we consider both the maximization variant Max Rep and the minimization variant Min Rep of the famous Label Cover problem. So far the best approximation ratios known for these two problems were \(O(\sqrt{n})\) and indeed some authors suggested the possibility that this ratio is the best approximation factor for these two problems. We show, in fact, that there are a O(n ^1/3)-approximation algorithm for Max Rep and a O(n ^1/3log?^2/3 n)-approximation algorithm for Min Rep. In addition, we also exhibit a randomized reduction from Densest k-Subgraph to Max Rep, showing that any approximation factor for Max Rep implies the same factor (up to a constant) for Densest k-Subgraph.     

Scheduling to Minimize Staleness and Stretch in Real-Time Data Warehouses

We study scheduling algorithms for loading data feeds into real time data warehouses, which are used in applications such as IP network monitoring, online financial trading, and credit card fraud detection. In these applications, the warehouse collects a large number of streaming data feeds that are generated by external sources and arrive asynchronously. Data for each table in the warehouse are generated at a constant rate, different tables possibly at different rates. For each data feed, the arrival of new data triggers an update that seeks to append the new data to the corresponding table; if multiple updates are pending for the same table, they are batched together before being loaded. At time τ, if a table has been updated with information up to time r≤τ, its staleness is defined as τ−r.