The maximum k-colorable subgraph (MkCS) problem is to find an induced k-colorable subgraph with maximum cardinality in a given graph. This paper is an in-depth analysis of the MkCS problem that considers various semidefinite programming relaxations, including their theoretical and numerical comparisons. To simplify these relaxations, we exploit the symmetry arising from permuting the colors, as well as the symmetry of the given graphs when applicable. We also show how to exploit invariance under permutations of the subsets for other partition problems and how to use the MkCS problem to derive bounds on the chromatic number of a graph. Our numerical results verify that the proposed relaxations provide strong bounds for the MkCS problem and that those outperform existing bounds for most of the test instances. Summary of Contribution: The maximum k-colorable subgraph (MkCS) problem is to find an induced k-colorable subgraph with maximum cardinality in a given graph. The MkCS problem has a number of applications, such as channel assignment in spectrum sharing networks (e.g., Wi-Fi or cellular), very-large-scale integration design, human genetic research, and so on. The MkCS problem is also related to several other optimization problems, including the graph partition problem and the max-k-cut problem. The two mentioned problems have applications in parallel computing, network partitioning, floor planning, and so on. This paper is an in-depth analysis of the MkCS problem that considers various semidefinite programming relaxations, including their theoretical and numerical comparisons. Further, our analysis relates the MkCS results with the stable set and the chromatic number problems. We provide extended numerical results that verify that the proposed bounding approaches provide strong bounds for the MkCS problem and that those outperform existing bounds for most of the test instances. Moreover, our lower bounds on the chromatic number of a graph are competitive with existing bounds in the literature.

We reformulate a (indefinite) quadratic program (QP) as a mixed-integer linear programming (MILP) problem by first reformulating a QP as a linear complementary problem, and then using binary variables and big-M constraints to model its complementary constraints. To obtain such reformulation, we use fundamental results on the solution of perturbed linear systems to impose bounds on the QP’s dual variables without eliminating any of its (globally) optimal primal solutions. Reformulating a nonconvex QP as a MILP problem allows the use of current state-of-the-art MILP solvers to find its global optimal solution. To illustrate this, we compare the performance of this MILP-based solution approach, labeled quadprogIP, with quadprogBB, BARON, and CPLEX. In practice, quadprogIP is shown to typically outperform by orders of magnitude quadprogBB, BARON, and CPLEX on standard QPs. Also, unlike quadprogBB, quadprogIP is able to solve QP instances in which the dual feasible set is unbounded. The MATLAB code quadprogIP and the instances used to perform the reported numerical experiments are publicly available at https://github.com/xiawei918/quadprogIP .

We consider the minimum makespan problem for n tasks and two unrelated parallel selfish machines. Let R n be the best approximation ratio of randomized monotone scale-free algorithms. This class contains the most efficient algorithms known for truthful scheduling on two machines. We propose a new M i n − M a x formulation for R n , as well as upper and lower bounds on R n based on this formulation. For the lower bound, we exploit pointwise approximations of cumulative distribution functions (CDFs). For the upper bound, we construct randomized algorithms using distributions with piecewise rational CDFs. Our method improves upon the existing bounds on R n for small n . In particular, we obtain almost tight bounds for n = 2 showing that | R 2 − 1.505996| < 10 − 6 .

For the hard-core lattice gas model defined on independent sets weighted by an activity $\lambda$, we study the critical activity $\lambda_c(\mathbb{Z}^2)$ for the uniqueness/nonuniqueness threshold on the 2-dimensional integer lattice $\mathbb{Z}^2$. The conjectured value of the critical activity is approximately 3.796. Until recently, the best lower bound followed from algorithmic results of Weitz [Proceedings of the $38$th Annual ACM Symposium on Theory of Computing, ACM, New York, 2006, pp. 140--149]. Weitz presented a fully polynomial-time approximation scheme for approximating the partition function for graphs of constant maximum degree $\Delta$ when $\lambda<\lambda_c(\mathbb{T}_\Delta)$, where $\mathbb{T}_\Delta$ is the infinite, regular tree of degree $\Delta$. His result established a certain decay of correlations property called strong spatial mixing (SSM) on $\mathbb{Z}^2$ by proving that SSM holds on its self-avoiding walk tree $T_{\mathrm{saw}}^\sigma(\mathbb{Z}^2)$, where $\sigma=(\sigma_v)_{v\in \mathbb{Z}^2}$ and $\sigma_v$ is an ordering on the neighbors of vertex $v$. As a consequence he obtained that $\lambda_c(\mathbb{Z}^2)\geq\lambda_c( \mathbb{T}_4) = 1.675$. Restrepo et al. [Probab. Theory Related Fields, 156 (2013), pp. 75--99] improved Weitz's approach for the particular case of $\mathbb{Z}^2$ and obtained that $\lambda_c(\mathbb{Z}^2)>2.388$. In this paper, we establish an upper bound for this approach, by showing that, for all $\sigma$, SSM does not hold on $T_{\mathrm{saw}}^\sigma(\mathbb{Z}^2)$ when $\lambda>3.4$. We also present a refinement of the approach of Restrepo et al. which improves the lower bound to $\lambda_c(\mathbb{Z}^2)>2.48$.

We study the effect of boundary conditions on the relaxation time (i.e., inverse spectral gap) of the Glauber dynamics for the hard-core model on the tree. The hard-core model is defined on the set of independent sets weighted by a parameter $\lambda$, called the activity or fugacity. The Glauber dynamics is the Markov chain that updates a randomly chosen vertex in each step. On the infinite tree with branching factor $b$, the hard-core model can be equivalently defined as a broadcasting process with a parameter $\omega$ which is the positive solution to $\lambda=\omega(1+\omega)^b$, and vertices are occupied with probability $\omega/(1+\omega)$ when their parent is unoccupied. This broadcasting process undergoes a phase transition between the so-called reconstruction and nonreconstruction regions at $\omega_r\approx \ln{b}/b$. Reconstruction has been of considerable interest recently since it appears to be intimately connected to the efficiency of local algorithms on locally tree-like graphs, such as sparse random graphs. In this paper we show that the relaxation time of the Glauber dynamics on regular trees $T_h$ of height $h$ with branching factor $b$ and $n$ vertices undergoes a phase transition around the reconstruction threshold. In particular, we construct a boundary condition for which the relaxation time slows down at the reconstruction threshold. More precisely, for any $\omega \le \ln{b}/b$, for $T_h$ with any boundary condition, the relaxation time is $\Omega(n)$ and $O(n^{1+o_b(1)})$. In contrast, above the reconstruction threshold we show that for every $\delta>0$, for $\omega=(1+\delta)\ln{b}/b$, the relaxation time on $T_h$ with any boundary condition is $O(n^{1+\delta + o_b(1)})$, and we construct a boundary condition where the relaxation time is $\Omega(n^{1+\delta/2 - o_b(1)})$. To prove this lower bound in the reconstruction region we introduce a general technique that transforms a reconstruction algorithm into a set with poor conductance.

We study the effect of boundary conditions on the relaxation time of the Glauber dynamics for the hardcore lattice gas model on the n-vertex regular b-ary tree of height h. The hard-core model is defined on independent sets weighted by an activity (or fugacity) Λ on trees. Reconstruction studies the effect of a ‘typical’ boundary condition, i.e., fixed assignment to the leaves, on the root. The threshold for when reconstruction occurs (and a typical boundary influences the root in the limit h → ∞) has been of considerable recent interest since it appears to be connected to the efficiency of certain local algorithms on locally tree-like graphs. The reconstruction threshold occurs at ω ≈ ln b/b where Λ = ω(1 + ω)b is a convenient re-parameterization of the model. We prove that for all boundary conditions, the relaxation time τ in the non-reconstruction region is fast, namely τ = O(n1+ob(1)) for any ω ≤ ln b/b. In the reconstruction region, for all boundary conditions, we prove τ = O(n1+δ+ob(1)) for ω = (1 + δ) ln b/b, for every δ > 0. In contrast, we construct a boundary condition, for which the Glauber dynamics slows down in the reconstruction region, namely τ = Ω(n1+δ/2−ob(1)) for ω = (1 + δ) ln b/b, for every δ > 0. The interesting part of our proof is this lower bound result, which uses a general technique that transforms an algorithm to prove reconstruction into a set in the state space of the Glauber dynamics with poor conductance.

Consider [Formula: see text]-colorings of the complete tree of depth [Formula: see text] and branching factor [Formula: see text]. If we fix the coloring of the leaves, for what range of [Formula: see text] is the root uniformly distributed over all [Formula: see text] colors (in the limit [Formula: see text])? This corresponds to the threshold for uniqueness of the infinite-volume Gibbs measure. It is straightforward to show the existence of colorings of the leaves which “freeze” the entire tree when [Formula: see text]. For [Formula: see text], Jonasson proved the root is “unbiased” for any fixed coloring of the leaves, and thus the Gibbs measure is unique. What happens for a typical coloring of the leaves? When the leaves have a nonvanishing influence on the root in expectation, over random colorings of the leaves, reconstruction is said to hold. Nonreconstruction is equivalent to extremality of the free-boundary Gibbs measure. When [Formula: see text], it is straightforward to show that reconstruction is possible (and hence the measure is not extremal). We prove that for [Formula: see text] and [Formula: see text], nonreconstruction holds; i.e., the Gibbs measure is extremal. We prove a strong form of extremality: With high probability over the colorings of the leaves the influence at the root decays exponentially fast with the depth of the tree. Closely related results were also proven recently by Sly. The above strong form of extremality implies that a local Markov chain that updates constant sized blocks has inverse linear entropy constant and hence [Formula: see text] mixing time where [Formula: see text] is the number of vertices of the tree. Extremality on trees and random graphs has received considerable attention recently since it may have connections to the efficiency of local algorithms.

We prove that the mixing time of the Glauber dynamics for random k-colorings of the complete tree with branching factor b undergoes a phase transition at k = b(1 + ob(1))/ln b. Our main result shows nearly sharp bounds on the mixing time of the dynamics on the complete tree with n vertices for k = Cb/ln b colors with constant C. For C ≥ 1 we prove the mixing time is . On the other side, for C < 1 the mixing time experiences a slowing down, in particular, we prove it is and . The critical point C = 1 is interesting since it coincides (at least up to first order) to the so-called reconstruction threshold which was recently established by Sly. The reconstruction threshold has been of considerable interest recently since it appears to have close connections to the efficiency of certain local algorithms, and this work was inspired by our attempt to understand these connections in this particular setting.

We propose the following model of a random graph on n vertices. Let F be a distribution in R+n(n-1)/2 with a coordinate for every pair ij with 1 ≤ i,j ≤ n. Then GF,p is the distribution on graphs with n vertices obtained by picking a random point X from F and defining a graph on n vertices whose edges are pairs ij for which Xij ≤ p. The standard Erdos-Renyi model is the special case when F is uniform on the 0-1 unit cube. We determine basic properties such as the connectivity threshold for quite general distributions. We also consider cases where the Xij are the edge weights in some random instance of a combinatorial optimization problem. By choosing suitable distributions, we can capture random graphs with interesting properties such as triangle-free random graphs and weighted random graphs with bounded total weight.

We study Markov chains for randomly sampling k-colorings of a graph with maximum degree δ. Our main result is a polynomial upper bound on the mixing time of the single-site update chain knownas the Glauber dynamics for planar graphs when k=Ω(δ/logδ). Our results can be partially extended to the more general case where the maximum eigenvalue of the adjacency matrix of the graphis at most δ1-e, for fixed e > 0.The main challenge when k ≤ δ + 1 is the possibility of frozen vertices, that is, vertices for which only one coloris possible, conditioned on the colors of its neighbors. Indeed, when δ = O(1), even a typical coloring canhave a constant fraction of the vertices frozen.Our proofs rely on recent advances in techniquesfor bounding mixing time using local uniformity properties.

In combinatorial optimization, a popular approach toNP-hard problems is the design of approximation algorithms. These algorithms typically run in polynomial time and are guaranteed to produce a solution which is within a known multiplicative factor of optimal. Unfortunately, the known factor is often known to be large in pathological instances. Conventional wisdom holds that, in practice, approximation algorithms will produce solutions closer to optimal than their proven guarantees. In this paper, we use the rigorous-analysis-of-heuristics framework to investigate this conventional wisdom.We analyze the performance of 3 related approximation algorithms for the uncapacitated facility location problem (from [Jain, Mahdian, Markakis, Saberi, Vazirani, 2003] and [Mahdian, Ye, Zhang, 2002]) when each is applied to an instances created by placing n points uniformly at random in the unit square. We find that, with high probability, these 3 algorithms do not find asymptotically optimal solutions, and, also with high probability, a simple plane partitioning heuristic does find an asymptotically optimal solution.