We give the first combinatorial approximation algorithm for Maxcut that beats the trivial 0.5 factor by a constant. The main partitioning procedure is very intuitive, natural, and easily described. It essentially performs a number of random walks and aggregates the information to provide the partition. We can control the running time to get an approximation factor-running time tradeoff. We show that for any constant b > 1.5, there is an O(n^ b ) algorithm that outputs a (0.5+delta)-approximation for Maxcut, where delta = delta(b) is some positive constant. One of the components of our algorithm is a weak local graph partitioning procedure that may be of independent interest. Given a starting vertex @math and a conductance parameter phi, unless a random walk of length ell = O(log n) starting from i mixes rapidly (in terms of phi and ell), we can find a cut of conductance at most phi close to the vertex. The work done per vertex found in the cut is sublinear in n.
We present an improved semidefinite programming based approximation algorithm for the MAX CUT problem in graphs of maximum degree at most 3. The approximation ratio of the new algorithm is at least 0.9326. This improves, and also somewhat simplifies, a result of Feige, Karpinski and Langberg. We also observe that results of Hopkins and Staton and of Bondy and Locke yield a simple combinatorial 4 5-approximation algorithm for the problem. Finally, we present a combinatorial 22 27-approximation algorithm for the MAX CUT problem for regular cubic graphs. The best approximation algorithm for Max Cut in graphs of maximum degree 3 uses semidefinite programming, has approximation ratio 0.9326, and its running time is @Q(n^3^.^5logn); but the best combinatorial algorithms have approximation ratio 4 5 only, achieved in O(n^2) time [J.A. Bondy, S.C. Locke, J. Graph Theory 10 (1986) 477-504; E. Halperin, et al, J. Algorithms 53 (2004) 169-185]. Here we present an improved combinatorial approximation, which is a 5 6-approximation algorithm that runs in O(n^2) time, perhaps improvable even to O(n). Our main tool is a new type of vertex decomposition for graphs of maximum degree 3. We consider the problem MAX CSP over multi-valued domains with variables ranging over sets of size si ≤ s and constraints involving kj ≤ k variables. We study two algorithms with approximation ratios A and B. respectively, so we obtain a solution with approximation ratio max (A, B).The first algorithm is based on the linear programming algorithm of Serna, Trevisan, and Xhafa [Proc. 15th Annual Symp. on Theoret. Aspects of Comput. Sci., 1998, pp. 488-498] and gives ratio A which is bounded below by s1-k. For k = 2, our bound in terms of the individual set sizes is the minimum over all constraints involving two variables of (1 2√s1+ 1 2√s2)2, where s1 and s2 are the set sizes for the two variables.We then give a simple combinatorial algorithm which has approximation ratio B, with B > A e. The bound is greater than s1-k e in general, and greater than s1-k(1 - (s - 1) 2(k - 1)) for s ≤ k - 1, thus close to the s1-k linear programming bound for large k. For k = 2, the bound is 4 9 if s = 2, 1 2(s - 1) if s ≥ 3, and in general greater than the minimum of 1 4S1 + 1 4s2 over constraints with set sizes s1 and s2, thus within a factor of two of the linear programming bound.For the case of k = 2 and s = 2 we prove an integrality gap of 4 9 (1 + O(n-1 2)). This shows that our analysis is tight for any method that uses the linear programming upper bound. On presente un algorithme polynomial permettant de determiner un sous-graphe biparti d'un graphe G sans triangle ni boucle de degre maximum 3, contenant au moins 4 5 des aretes de G. On caracterise le dodecaedre et le graphe de Petersen comme les seuls graphes connexes 3-reguliers sans triangle ni boucle pour lesquels il n'existe pas de sous graphe biparti ayant un nombre d'aretes superieur a cette proportion   A portable device for removing and collecting dust, particularly from vehicle friction brake and clutch assemblies, comprises a base having a high efficiency filter and vacuum assembly, a transparent evacuation hood designed to surround the brake or clutch, a vacuum hose for removing contaminated air from the hood to the base, and adjustable means for disposing the hood at variable heights above the base. The filter and vacuum assembly, which may serve as a stand alone unit having application outside the automotive field, is oriented such that a disposable filter is located in a compartment upstream of the vacuum motors and may be removed from the base while the vacuum motors are running, thereby preventing dispersal of hazardous materials during the filter changing operation. Apertures provided in the hood include two gloved portals for allowing a worker's hands and arms to have unimpeded access to the brake and clutch assemblies. A highly portable embodiment includes an inflatable hood.