Approximation algorithms for general packing problems and their application to the multicast congestion problem

In this paper we present approximation algorithms based on a Lagrangian decomposition via a logarithmic potential reduction to solve a general packing or min–max resource sharing problem with M non-negative convex constraints on a convex set B. We generalize a method by Grigoriadis et al. to the case with weak approximate block solvers (i.e., with only constant, logarithmic or even worse approximation ratios). Given an accuracy , we show that our algorithm needs calls to the block solver, a bound independent of the data and the approximation ratio of the block solver. For small approximation ratios the algorithm needs calls to the block solver. As an application we study the problem of minimizing the maximum edge congestion in a multicast communication network. Interestingly the block problem here is the classical Steiner tree problem that can be solved only approximately. We show how to use approximation algorithms for the Steiner tree problem to solve the multicast congestion problem approximately. This work was done in part when the second author was studying at the University of Kiel. This paper combines our extended abstracts of the 2nd IFIP International Conference on Theoretical Computer Science, TCS 2002, Montréal, Canada and the 3rd Workshop on Approximation and Randomization Algorithms in Communication Networks, ARACNE 2002, Roma, Italy. This research was supported in part by the DFG - Graduiertenkolleg, Effiziente Algorithmen und Mehrskalenmethoden; by the EU Thematic Network APPOL I + II, Approximation and Online Algorithms, IST-1999-14084 and IST-2001-32007; by the EU Research Training Network ARACNE, Approximation and Randomized Algorithms in Communication Networks, HPRN-CT-1999-00112; by the EU Project CRESCCO, Critical Resource Sharing for Cooperation in Complex Systems, IST-2001-33135. The second author was also supported by an MITACS grant of Canada; and by the NSERC Discovery Grant DG 5-48923.     

An Approximation Scheme For Cake Division With A Linear Number Of Cuts

In the cake cutting problem, n≥2 players want to cut a cake into n pieces so that every player gets a ‘fair’ share of the cake by his own measure. We prove the following result: For every ε>0, there exists a cake division scheme for n players that uses at most c_εn cuts, and in which each player can enforce to get a share of at least (1-ε)/n of the cake according to his own private measure. * Partially supported by Institute for Theoretical Computer Science, Prague (project LN00A056 of MŠMT ČR) and grant IAA1019401 of GA AV ČR.     

Network Design Via Iterative Rounding Of Setpair Relaxations

A typical problem in network design is to find a minimum-cost sub-network H of a given network G such that H satisfies some prespecified connectivity requirements. Our focus is on approximation algorithms for designing networks that satisfy vertex connectivity requirements. Our main tool is a linear programming relaxation of the following setpair formulation due to Frank and Jordan: a setpair consists of two subsets of vertices (of the given network G); each setpair has an integer requirement, and the goal is to find a minimum-cost subset of the edges of G sucht hat each setpair is covered by at least as many edges as its requirement. We introduce the notion of skew bisupermodular functions and use it to prove that the basic solutions of the linear program are characterized by “non-crossing families” of setpairs. This allows us to apply Jain’s iterative rounding method to find approximately optimal integer solutions. We give two applications. (1) In the k-vertex connectivity problem we are given a (directed or undirected) graph G=(V,E) with non-negative edge costs, and the task is to find a minimum-cost spanning subgraph H such that H is k-vertex connected. Let n=|V|, and let ε<1 be a positive number such that k≤(1−ε)n. We give an -approximation algorithm for both problems (directed or undirected), improving on the previous best approximation guarantees for k in the range . (2)We give a 2-approximation algorithm for the element connectivity problem, matching the previous best approximation guarantee due to Fleischer, Jain and Williamson. * Supported in part by NSERC researchgran t OGP0138432. † Supported in part by NSF Career Award CCR-9875024.     

NOTE ON INVERSE PROBLEM WITH l∞ OBJECTIVE FUNCTION

In this note, the author proves that the inverse problem of submodular function on digraphs with l∞ objective function can be solved by strongly polynomial algorithm. The result shows that most inverse network optimization problems with l∞ objective function can be solved in the polynomial time.     

An analysis of the greedy algorithm for the submodular set covering problem

We consider the problem: min \(\{ \mathop \Sigma \limits_{j \in s} f_j :z(S) = z(N),S \subseteqq N\} \) wherez is a nondecreasing submodular set function on a finite setN. Whenz is integer-valued andz(Ø)=0, it is shown that the value of a greedy heuristic solution never exceeds the optimal value by more than a factor \(H(\mathop {\max }\limits_j z(\{ j\} ))\) where \(H(d) = \sum\limits_{i = 1}^d {\frac{1}{i}} \) . This generalises earlier results of Dobson and others on the applications of the greedy algorithm to the integer covering problem: min {fy: Ay ≧b, y ε {0, 1}} wherea _ij ,b _i } ≧ 0 are integer, and also includes the problem of finding a minimum weight basis in a matroid.     

The colourful feasibility problem

We study a colourful generalization of the linear programming feasibility problem, comparing the algorithms introduced by Bárány and Onn with new methods. This is a challenging problem on the borderline of tractability, its complexity is an open question. We perform benchmarking on generic and ill-conditioned problems, as well as recently introduced highly structured problems. We show that some algorithms can lead to cycling or slow convergence and we provide extensive numerical experiments which show that others perform much better than predicted by complexity arguments. We conclude that the most efficient method is a proposed multi-update algorithm.     

A primal-dual approximation algorithm for generalized steiner network problems

We present the first polynomial-time approximation algorithm for finding a minimum-cost subgraph having at least a specified number of edges in each cut. This class of problems includes, among others, the generalized Steiner network problem, also called the survivable network design problem. Ifk is the maximum cut requirement of the problem, our solution comes within a factor of 2k of optimal. Our algorithm is primal-dual and shows the importance of this technique in designing approximation algorithms.Research supported by an NSF Graduate Fellowship, DARPA contracts N00014-91-J-1698 and N00014-92-J-1799, and AT&T Bell Laboratories.Research supported in part by Air Force contract F49620-92-J-0125 and DARPA contract N00014-92-J-1799.Part of this work was done while the author was visiting AT&T Bell Laboratories and Bellcore.     

Asymptotic behaviour of a family of gradient algorithms in ℝ d and Hilbert spaces

The asymptotic behaviour of a family of gradient algorithms (including the methods of steepest descent and minimum residues) for the optimisation of bounded quadratic operators in ℝ^d and Hilbert spaces is analyzed. The results obtained generalize those of Akaike (1959) in several directions. First, all algorithms in the family are shown to have the same asymptotic behaviour (convergence to a two-point attractor), which implies in particular that they have similar asymptotic convergence rates. Second, the analysis also covers the Hilbert space case. A detailed analysis of the stability property of the attractor is provided.     

Mutual exclusion scheduling with interval graphs or related classes. Part II

This paper is the second part of a study devoted to the mutual exclusion scheduling problem. Given a simple and undirected graph G and an integer k, the problem is to find a minimum coloring of G such that each color is used at most k times. The cardinality of such a coloring is denoted by χ(G,k). When restricted to interval graphs or related classes like circular-arc graphs and tolerance graphs, the problem has some applications in workforce planning. Unfortunately, the problem is shown to be NP-hard for interval graphs, even if k is a constant greater than or equal to four [H.L. Bodlaender, K. Jansen, Restrictions of graph partition problems. Part I. Theoret. Comput. Sci. 148 (1995) 93-109]. In this paper, the problem is approached from a different point of view by studying a non-trivial and practical sufficient condition for optimality. In particular, the following proposition is demonstrated: if an interval graph G admits a coloring such that each color appears at least k times, then χ(G,k)=⌈n/k⌉. This proposition is extended to several classes of graphs related to interval graphs. Moreover, all our proofs are constructive and provide efficient algorithms to solve the MES problem for these graphs, given a coloring satisfying the condition in input.     

Approximating Directed Multicuts

The seminal paper of Leighton and Rao (1988) and subsequent papers presented approximate min-max theorems relating multicommodity flow values and cut capacities in undirected networks, developed the divide-and-conquer method for designing approximation algorithms, and generated novel tools for utilizing linear programming relaxations. Yet, despite persistent research efforts, these achievements could not be extended to directed networks, excluding a few cases that are symmetric and therefore similar to undirected networks. This paper is an attempt to remedy the situation. We consider the problem of finding a minimum multicut in a directed multicommodity flow network, and give the first nontrivial upper bounds on the max flow-to-min multicut ratio. Our results are algorithmic, demonstrating nontrivial approximation guarantees.* Supported in part by NSERC research grant OGP0138432. Part of this work was done while visiting AT&T Labs–Research. Work at the Technion supported by Israel Science Foundation grant number 386/99, by BSF grants 96-00402 and 99-00217, by Ministry of Science contract number 9480198, by EU contract number 14084 (APPOL), by the CONSIST consortium (through the MAGNET program of the Ministry of Trade and Industry), and by the Fund for the Promotion of Research at the Technion.     

On 3-pushdown graphs with large separators

For an integers letl ^s (n), thes-iterated logarithm function, be defined inductively:l ⁰ (n)=n,l ^s+1 (n)=log₂ (l ² (n)) fors0. We show that for every fixeds and alln large enough, there is ann-vertex 3-pushdown graph whose smallest separator contains at least(n/l ^s (n)) vertices.The work of the first author was supported in part by NSF Grants MCS-83-03139, DCR-85-11713 and CCR-86-05353.The work of the second author was supported in part by NSF Grants MCS-84-16190.     

MAXIMUM CYCLE-MEANS OF WEIGHTED DIGRAPHS

Abstract. Computing the maximum cycle-mean of a weighted digraph is relevant to a number of applications, and combinatorial algorlthnls of complexity 0(n) are known.We present a new algorithm, with computational evidence to suggest an expected run-time growth rate below O(n^3）     

Bin packing can be solved within 1 + ε in linear time

For any listL ofn numbers in (0, 1) letL* denote the minimum number of unit capacity bins needed to pack the elements ofL. We prove that, for every positive ε, there exists anO(n)-time algorithmS such that, ifS(L) denotes the number of bins used byS forL, thenS(L)/L*≦1+ε for anyL providedL* is sufficiently large. The work of this author was supported by NSF Grant MCS 70-04997.     

A subexponential algorithm for the coloured tree partition problem

Given a tree of n vertices and a list of feasible colours for each vertex, the coloured tree partition problem (CTPP) consists in partitioning the tree into p vertex-disjoint subtrees of minimum total cost, and assigning to each subtree a different colour, which must be feasible for all of its vertices. The problem is strongly NP-hard on general graphs, as well as on grid and bipartite graphs. This paper deals with the previously open case of tree graphs, showing that it is strongly NP-complete to determine whether a feasible solution exists. It presents reduction, decomposition and bounding procedures to simplify the problem and an exact algorithm of complexity (with ) for the special case in which a vertex of each subtree is given.     

An approximate max-flow min-cut relation for undirected multicommodity flow,with applications

In this paper, we prove the first approximate max-flow min-cut theorem for undirected multicommodity flow. We show that for a feasible flow to exist in a multicommodity problem, it is sufficient that every cut's capacity exceeds its demand by a factor ofO(logClogD), whereC is the sum of all finite capacities andD is the sum of demands. Moreover, our theorem yields an algorithm for finding a cut that is approximately minimumrelative to the flow that must cross it. We use this result to obtain an approximation algorithm for T. C. Hu's generalization of the multiway-cut problem. This algorithm can in turn be applied to obtain approximation algorithms for minimum deletion of clauses of a 2-CNF formula, via minimization, and other problems. We also generalize the theorem to hypergraph networks; using this generalization, we can handle CNF clauses with an arbitrary number of literals per clause.Most of the results in this paper were presented in preliminary form in Approximation through multicommodity flow,Proceedings, 31th Annual Symposium on Foundations of Computer Science (1990), pp. 726–737.Research supported by the National Science Foundation under NSF grant CDA 8722809, by the Office of Naval and the Defense Advanced Research Projects Agency under contract N00014-83-K-0146, and ARPA Order No. 6320, Amendament 1.Research supported by NSF grant CCR-9012357 and by an NSF Presidential Young Investigator Award.     

The multifit algorithm for set partitioning containing kernels

This pager investigates the set partitioning containing kernels. This problem can alsobe considered as the identical machine scheduling prohlem with nonsimultaneous machine release times. That the algorithm MULTIFIT has a worst ease bound of 6/5 is proved. Throughcombining MULTIFIT and LPT. an algorithm MULTILPT with a worat case bound of 7/6 has been obtained.     

Fully-Dynamic Min-Cut*

We show that we can maintain up to polylogarithmic edge connectivity for a fully-dynamic graph in worst-case time per edge insertion or deletion. Within logarithmic factors, this matches the best time bound for 1-edge connectivity. Previously, no o(n) bound was known for edge connectivity above 3, and even for 3-edge connectivity, the best update time was O(n^2/3), dating back to FOCS'92. Our algorithm maintains a concrete min-cut in terms of a pointer to a tree spanning one side of the cut plus ability to list the cut edges in O(log n) time per edge. By dealing with polylogarithmic edge connectivity, we immediately get a sampling based expected factor (1+o(1)) approximation to general edge connectivity in time per edge insertion or deletion. This algorithm also maintains a pointer to one side of a near-minimal cut, but if we want to list the cut edges in O(log n) time per edge, the update time increases to . * A preliminary version of this work was presented at the The 33rd ACM Symposium on Theory of Computing( STOC) [22], Crete, Greece, July 2001.     

Recognizing graphic matroids

There is no polynomially bounded algorithm to test if a matroid (presented by an “independence oracle”) is binary. However, there is one to test graphicness. Finding this extends work of previous authors, who have given algorithms to test binary matroids for graphicness. Our main tool is a new result that ifM′ is the polygon matroid of a graphG, andM is a different matroid onE(G) with the same rank, then there is a vertex ofG whose star is not a cocircuit ofM.