Hermitian Laplacians and a Cheeger inequality for the Max2Lin problem We study spectral approaches for the MAX2LIN(k) problem, in which we are given a system of m linear equations of the form x_i  x_j equiv c_ijmod k, and required to find an assignment to the n variables x_i that maximises the total number of satisfied equations.  :47,consider Hermitian Laplacians related to this problem, and prove a Cheeger inequality that relates the smallest eigenvalue of a Hermitian Laplacian to the maximum number of satisfied equations of a MAX2LIN(k) instance mathcalI. We develop an widetildeO(kn2) time algorithm that, for any (1varepsilon)satisfiable instance, produces an assignment satisfying a left(1  O(k)sqrtvarepsilonright)fraction of equations. We also present a subquadratictime algorithm that, when the graph associated with mathcalI is an expander, produces an assignment satisfying a left(1 O(k2)varepsilon right)fraction of the equations. Our Cheeger inequality and first algorithm can be seen as generalisations of the Cheeger inequality and algorithm for MAXCUT developed by Trevisan.

A quadratically convergent local algorithm on minimizing sums of the largest eigenvalues of a symmetric matrix In this paper, we consider the problem on minimizing sums of the largest eigenvalues of a symmetric matrix which depends on the decision variable affinely. An important application of this problem is the graph partitioning problem, which arises in layout of circuit boards, computer logic partitioning, and paging of computer programs. Given xe2x88x88xe2x89xa50, we first derive an optimality condition which ensures that the objective function is within xe2x88x88 error bound of the solution. This condition may be used as a practical stopping criterion for any algorithm solving the underlying problem. We also show that, in a neighborhood of the minimizer, the optimization problem can be equivalently formulated as a smooth constrained problem. An existing algorithm on minimizing the largest eigenvalue of a symmetric matrix is shown to be applicable here. This algoritm enjoys the property that if started close enough to the minimizer, then it will converge quadratically. To implement a practical algorithm, one needs to incorporate some technique to generate a good starting point. Since the problem is convex, this can be done by using an algorithm for general convex optimization problems (e.g., Kelleyu0027s cutting plane method or ellipsoid methods), or an algorithm specific for the optimization problem under consideration (e.g., the algorithm developed by Cullum, Donath, and Wolfe). Such union ensures that the overall algorithm has global convergence with quadratic rate. Finally, the results presented in this paper are readily extended on minimizing sums of the largest eigenvalues of a Hermitian matrix.