Approximation Algorithms for MAX 4-SAT and Rounding Procedures for Semidefinite Programs

Karloff and Zwick obtained recently an optimal 7/8-approximation algorithm for MAX 3-SAT. In an attempt to see whether similar methods can be used to obtain a 7/8-approximation algorithm for MAX SAT, we consider the most natural generalization of MAX 3-SAT, namely MAX 4-SAT. We present a semidefinite programming relaxation of MAX 4-SAT and a new family of rounding procedures that try to cope well with clauses of various sizes. We study the potential, and the limitations, of the relaxation and of the proposed family of rounding procedures using a combination of theoretical and experimental means. We select two rounding procedures from the proposed family of rounding procedures. Using the first rounding procedure we seem to obtain an almost optimal 0.8721-approximation algorithm for MAX 4-SAT. Using the second rounding procedure we seem to obtain an optimal 7/8-approximation algorithm for satisfiable instances of MAX 4-SAT. On the other hand, we show that no rounding procedure from the family considered can be shown, using the current techniques, to yield an approximation algorithm for MAX 4-SAT whose performance guarantee for all instances of the problem is greater than 0.8724. We also show that the integrality ratio of the proposed relaxation, as a relaxation of MAX {1, 4}-SAT, is at most 0.8754.The 0.8721-approximation for MAX 4-SAT that we seem to obtain substantially improves the performance guarantees of all previous algorithms suggested for the problem. It is extremely close to being optimal as a (7/8 + ε)-approximation algorithm for MAX 4-SAT, for any fixed ε > 0, would imply that P = NP. Our investigation also indicates, however, that additional ideas are required in order to obtain optimal 7/8-approximation algorithms for MAX 4-SAT and MAX SAT.Although most of this paper deals specifically with the MAX 4-SAT problem, we believe that the new family of rounding procedures introduced and the methodology used in the design and in the analysis of the various rounding procedures considered have a much wider range of applicability.     

MAX k‐CUT and approximating the chromatic number of random graphs

We consider the MAX k‐CUT problem on random graphs G_n,p. First, we bound the probable weight of a MAX k‐CUT using probabilistic counting arguments and by analyzing a simple greedy heuristic. Then, we give an algorithm that approximates MAX k‐CUT in expected polynomial time, with approximation ratio 1 + O((np)^‐1/2). Our main technical tool is a new bound on the probable value of Frieze and Jerrum's semidefinite programming (SDP)‐relaxation of MAX k‐CUT on random graphs. To obtain this bound, we show that the value of the SDP is tightly concentrated. As a further application of our bound on the probable value of the SDP, we obtain an algorithm for approximating the chromatic number of G_n,p, 1/n ≤ p ≤ 0.99, within a factor of O((np)^1/2) in polynomial expected time, thereby answering a question of Krivelevich and Vu. We give similar algorithms for random regular graphs. The techniques for studying the SDP apply to a variety of SDP relaxations of further NP‐hard problems on random structures and may therefore be of independent interest. For instance, to bound the SDP we estimate the eigenvalues of random graphs with given degree sequences. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006     

An improved upper bound for the TSP in cubic 3-edge-connected graphs

We consider the travelling salesman problem (TSP) problem on (the metric completion of) 3-edge-connected cubic graphs. These graphs are interesting because of the connection between their optimal solutions and the subtour elimination LP relaxation. Our main result is an approximation algorithm better than the 3/2-approximation algorithm for TSP in general.     

The traveling salesman problem on cubic and subcubic graphs

We study the traveling salesman problem (TSP) on the metric completion of cubic and subcubic graphs, which is known to be NP-hard. The problem is of interest because of its relation to the famous 4/3-conjecture for metric TSP, which says that the integrality gap, i.e., the worst case ratio between the optimal value of a TSP instance and that of its linear programming relaxation (the subtour elimination relaxation), is 4/3. We present the first algorithm for cubic graphs with approximation ratio 4/3. The proof uses polyhedral techniques in a surprising way, which is of independent interest. In fact we prove constructively that for any cubic graph on $n$ vertices a tour of length $4n/3-2$ exists, which also implies the 4/3-conjecture, as an upper bound, for this class of graph-TSP. Recently, Mömke and Svensson presented an algorithm that gives a 1.461-approximation for graph-TSP on general graphs and as a side result a 4/3-approximation algorithm for this problem on subcubic graphs, also settling the 4/3-conjecture for this class of graph-TSP. The algorithm by Mömke and Svensson is initially randomized but the authors remark that derandomization is trivial. We will present a different way to derandomize their algorithm which leads to a faster running time. All of the latter also works for multigraphs.     

Approximation algorithms for the single allocation problem in hub-and-spoke networks and related metric labeling problems

This paper deals with a single allocation problem in hub-and-spoke networks. We present a simple deterministic 3-approximation algorithm and randomized 2-approximation algorithm based on a linear relaxation problem and a randomized rounding procedure. We handle the case where the number of hubs is three, which is known to be NP-hard, and present a (5/4)-approximation algorithm.The single allocation problem includes a special class of the metric labeling problem, defined by introducing an assumption that both objects and labels are embedded in a common metric space. Under this assumption, we can apply our algorithms to the metric labeling problem without losing theoretical approximation ratios. As a byproduct, we also obtain a (4/3)-approximation algorithm for an ordinary metric labeling problem with three labels.     

Complexity and approximation of the connected set-cover problem

In this paper, we study the computational complexity and approximation complexity of the connected set-cover problem. We derive necessary and sufficient conditions for the connected set-cover problem to have a polynomial-time algorithm. We also present a sufficient condition for the existence of a (1 +? ln ??)-approximation. In addition, one such (1 +? ln ??)-approximation algorithm for this problem is proposed. Furthermore, it is proved that there is no polynomial-time ${O(\log^{2-\varepsilon} n)}$ -approximation for any ${\varepsilon\,{>}\,0}$ for the connected set-cover problem on general graphs, unless NP has an quasi-polynomial Las-Vegas algorithm.     

Minimum Color Sum of Bipartite Graphs

The problem ofminimum color sumof a graph is to color the vertices of the graph such that the sum (average) of all assigned colors is minimum. Recently it was shown that in general graphs this problem cannot be approximated withinn^{1 − ε}, for any ε > 0, unlessNP = ZPP(Bar-Noyet al., Information and Computation140(1998), 183–202). In the same paper, a 9/8-approximation algorithm was presented for bipartite graphs. The hardness question for this problem on bipartite graphs was left open. In this paper we show that the minimum color sum problem for bipartite graphs admits no polynomial approximation scheme, unlessP = NP. The proof is byL-reducing the problem of finding the maximum independent set in a graph whose maximum degree is four to this problem. This result indicates clearly that the minimum color sum problem is much harder than the traditional coloring problem, which is trivially solvable in bipartite graphs. As for the approximation ratio, we make a further step toward finding the precise threshold. We present a polynomial 10/9-approximation algorithm. Our algorithm uses a flow procedure in addition to the maximum independent set procedure used in previous solutions.     

A (2 + )-Approximation Scheme for Minimum Domination on Circle Graphs

The main result of this paper is a (2 + )-approximation scheme for the minimum dominating set problem on circle graphs. We first present an O(n²) time 8-approximation algorithm for this problem and then extend it to an time (2 + )-approximation scheme for this problem. Here n and m are the number of vertices and the number of edges of the circle graph. We then present simple modifications to this algorithm that yield (3 + )-approximation schemes for the minimum connected and the minimum total dominating set problems on circle graphs. Keil (1993, Discrete Appl. Math.42, 51–63) shows that these problems are NP-complete for circle graphs and leaves open the problem of devising approximation algorithms for them. These are the first O(1)-approximation algorithms for domination problems on circle graphs.     

An approximation algorithm for sorting by reversals and transpositions

Genome rearrangement algorithms are powerful tools to analyze gene orders in molecular evolution. Analysis of genomes evolving by reversals and transpositions leads to a combinatorial problem of sorting by reversals and transpositions, the problem of finding a shortest sequence of reversals and transpositions that sorts one genome into the other. In this paper we present a 2k-approximation algorithm for sorting by reversals and transpositions for unsigned permutations where k is the approximation ratio of the algorithm used for cycle decomposition. For the best known value of k our approximation ratio becomes 2.8386+δ for any δ>0. We also derive a lower bound on reversal and transposition distance of an unsigned permutation.     

Admission control with advance reservations in simple networks

In the admission control problem we are given a network and a set of connection requests, each of which is associated with a path, a time interval, a bandwidth requirement, and a weight. A feasible schedule is a set of connection requests such that at any given time, the total bandwidth requirement on every link in the network is at most 1. Our goal is to find a feasible schedule with maximum total weight.We consider the admission control problem in two simple topologies: the line and the tree. We present a 12c-approximation algorithm for the line topology, where c is the maximum number of requests on a link at some time instance. This result implies a 12c-approximation algorithm for the rectangle packing problem, where c is the maximum number of rectangles that cover simultaneously a point in the plane. We also present an O(logt)-approximation algorithm for the tree topology, where t is the size of the tree. We consider the loss minimization version of the admission control problem in which the goal is to minimize the weight of unscheduled requests. We present a c-approximation algorithm for loss minimization problem in the tree topology. This result is based on an approximation algorithm for a generalization of set cover, in which each element has a covering requirement, and each set has a covering potential. The approximation ratio of this algorithm is Δ, where Δ is the maximum number of sets that contain the same element.     

Approximations for node-weighted Steiner tree in unit disk graphs

Given a node-weighted connected graph and a subset of terminals, the problem node-weighted Steiner tree (NWST) seeks a lightest tree connecting a given set of terminals in a node-weighted graph. While NWST in general graphs are as hard as Set Cover, NWST restricted to unit-disk graphs (UDGs) admits constant-approximations. Recently, Zou et al. (Lecture notes in computer science, vol 5165, COCOA, 2008, pp 278–285) showed that any μ-approximation algorithm for the classical edge-weighted Steiner tree problem can be used to produce 2.5 μ-approximation algorithm for NWST restricted to UDGs. With the best known approximation bound 1.55 for the classical Steiner tree problem, they obtained an approximation bound 3.875 for NWST restricted to UDGs. In this paper, we present three approximation algorithms for NWST restricted to UDGs, the k-Restricted Relative Greedy Algorithm whose approximation bound converges to 1 + ln 5 ≈ 2.61 as k → ∞, the 3-Restricted Greedy Algorithm with approximation bound 4\frac13{4\frac{1}{3}} , and the k-Restricted Variable Metric Algorithm whose approximation bound converges to 3.9334 as k → ∞.     

Combinatorial 5/6-approximation of Max Cut in graphs of maximum degree 3

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 Θ(n^3.5logn); but the best combinatorial algorithms have approximation ratio 4/5 only, achieved in O(n²) 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²) time, perhaps improvable even to O(n). Our main tool is a new type of vertex decomposition for graphs of maximum degree 3.     

On connected domination in unit ball graphs

Given a simple undirected graph, the minimum connected dominating set problem is to find a minimum cardinality subset of vertices D inducing a connected subgraph such that each vertex outside D has at least one neighbor in D. Approximations of minimum connected dominating sets are often used to represent a virtual routing backbone in wireless networks. This paper first proposes a constant-ratio approximation algorithm for the minimum connected dominating set problem in unit ball graphs and then introduces and studies the edge-weighted bottleneck connected dominating set problem, which seeks a minimum edge weight in the graph such that the corresponding bottleneck subgraph has a connected dominating set of size k. In wireless network applications this problem can be used to determine an optimal transmission range for a network with a predefined size of the virtual backbone. We show that the problem is hard to approximate within a factor better than 2 in graphs whose edge weights satisfy the triangle inequality and provide a 3-approximation algorithm for such graphs. We also show that for fixed k the problem is polynomially solvable in unit disk and unit ball graphs.     

Combinatorial approximation algorithms for the robust facility location problem with penalties

In this paper, we consider the robust facility location problem with penalties, aiming to serve only a specified fraction of the clients. We formulate this problem as an integer linear program to identify which clients must be served. Based on the corresponding LP relaxation and dual program, we propose a primal–dual (combinatorial) 3-approximation algorithm. Combining the greedy augmentation procedure, we further improve the above approximation ratio to 2.     

A 3-approximation algorithm for the subtree distance between phylogenies

In this paper, we give a (polynomial-time) 3-approximation algorithm for the rooted subtree prune and regraft distance between two phylogenetic trees. This problem is known to be NP-complete and the best previously known approximation algorithm is a 5-approximation. We also give a faster fixed-parameter algorithm for the rooted subtree prune and regraft distance than was previously known.     

Improved approximation algorithm for the feedback set problem in a bipartite tournament

We present a simple 3-approximation algorithm for the feedback vertex set problem in a bipartite tournament, improving on the approximation ratio of 3.5 achieved by the best previous algorithms.     

Worst case complexity of multivariate Feynman–Kac path integration

We study the multivariate Feynman–Kac path integration problem. This problem was studied in Plaskota et al. (J. Comp. Phys. 164 (2000) 335) for the univariate case. We describe an algorithm based on uniform approximation, instead of the L₂-approximation used in Plaskota et al. (2000). Similarly to Plaskota et al. (2000), our algorithm requires extensive precomputing. We also present bounds on the complexity of our problem. The lower bound is provided by the complexity of a certain integration problem, and the upper bound by the complexity of the uniform approximation problem. The algorithm presented in this paper is almost optimal for the classes of functions for which uniform approximation and integration have roughly the same complexities.     

On approximating complex quadratic optimization problems via semidefinite programming relaxations

In this paper we study semidefinite programming (SDP) models for a class of discrete and continuous quadratic optimization problems in the complex Hermitian form. These problems capture a class of well-known combinatorial optimization problems, as well as problems in control theory. For instance, they include the MAX-3-CUT problem where the Laplacian matrix is positive semidefinite (in particular, some of the edge weights can be negative). We present a generic algorithm and a unified analysis of the SDP relaxations which allow us to obtain good approximation guarantees for our models. Specifically, we give an -approximation algorithm for the discrete problem where the decision variables are k-ary and the objective matrix is positive semidefinite. To the best of our knowledge, this is the first known approximation result for this family of problems. For the continuous problem where the objective matrix is positive semidefinite, we obtain the well-known π /4 result due to Ben-Tal et al. [Math Oper Res 28(3):497–523, 2003], and independently, Zhang and Huang [SIAM J Optim 16(3):871–890, 2006]. However, our techniques simplify their analyses and provide a unified framework for treating those problems. In addition, we show for the first time that the gap between the optimal value of the original problem and that of the SDP relaxation can be arbitrarily close to π /4. We also show that the unified analysis can be used to obtain an Ω(1/ log n)-approximation algorithm for the continuous problem in which the objective matrix is not positive semidefinite. This research was supported in part by NSF grant DMS-0306611.     

关联聚类问题的半定规划舍入算法

主要研究带有两类权重的一般图下的关联聚类问题. 问题的定义是, 给定图G=(V,E), 每条边有两类权重, 我们需要将点集V进行聚类, 目标是最大相同性, 即最大化属于某个类的边的第一类权重之和加上在两个不同类之间的边的第二类权重之和. 该问题是NP-难的, 我们利用外部旋转技术将现有的半定规划舍入0.75-近似算法改进. 算法的分析指出, 改进的算法虽然不能将近似比0.75提高, 但是对于大多数实例, 可以获得更好的运行效果.