Is constraint satisfaction over two variables always easy?

By the breakthrough work of Håstad [J ACM 48(4) (2001), 798–859], several constraint satisfaction problems are now known to have the following approximation resistance property: Satisfying more clauses than what picking a random assignment would achieve is NP‐hard. This is the case for example for Max E3‐Sat, Max E3‐Lin, and Max E4‐Set Splitting. A notable exception to this extreme hardness is constraint satisfaction over two variables (2‐CSP); as a corollary of the celebrated Goemans‐Williamson algorithm [J ACM 42(6) (1995), 1115–1145], we know that every Boolean 2‐CSP has a nontrivial approximation algorithm whose performance ratio is better than that obtained by picking a random assignment to the variables. An intriguing question then is whether this is also the case for 2‐CSPs over larger, non‐Boolean domains. This question is still open, and is equivalent to whether the generalization of Max 2‐SAT to domains of size d, can be approximated to a factor better than (1 ? 1/d²). In an attempt to make progress towards this question, in this paper we prove, first, that a slight restriction of this problem, namely, a generalization of linear inequations with two variables per constraint, is not approximation resistant, and, second, that the Not‐All‐Equal Sat problem over domain size d with three variables per constraint, is approximation resistant, for every d ≥ 3. In the Boolean case, Not‐All‐Equal Sat with three variables per constraint is equivalent to Max 2‐SAT and thus has a nontrivial approximation algorithm; for larger domain sizes, Max 2‐SAT can be reduced to Not‐All‐Equal Sat with three variables per constraint. Our approximation algorithm implies that a wide class of 2‐CSPs called regular 2‐CSPs can all be approximated beyond their random assignment threshold. © 2004 Wiley Periodicals, Inc. Random Struct. Alg. 2004     

Sampling subproblems of heterogeneous Max‐Cut problems and approximation algorithms

Recent work in the analysis of randomized approximation algorithms for NP‐hard optimization problems has involved approximating the solution to a problem by the solution of a related subproblem of constant size, where the subproblem is constructed by sampling elements of the original problem uniformly at random. In light of interest in problems with a heterogeneous structure, for which uniform sampling might be expected to yield suboptimal results, we investigate the use of nonuniform sampling probabilities. We develop and analyze an algorithm which uses a novel sampling method to obtain improved bounds for approximating the Max‐Cut of a graph. In particular, we show that by judicious choice of sampling probabilities one can obtain error bounds that are superior to the ones obtained by uniform sampling, both for unweighted and weighted versions of Max‐Cut. Of at least as much interest as the results we derive are the techniques we use. The first technique is a method to compute a compressed approximate decomposition of a matrix as the product of three smaller matrices, each of which has several appealing properties. The second technique is a method to approximate the feasibility or infeasibility of a large linear program by checking the feasibility or infeasibility of a nonuniformly randomly chosen subprogram of the original linear program. We expect that these and related techniques will prove fruitful for the future development of randomized approximation algorithms for problems whose input instances contain heterogeneities. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

Polynomial time approximation schemes for dense instances of minimum constraint satisfaction

It is known that large fragments of the class of dense Minimum Constraint Satisfaction (MIN‐CSP) problems do not have polynomial time approximation schemes (PTASs) contrary to their Maximum Constraint Satisfaction analogs. In this paper we prove, somewhat surprisingly, that the minimum satisfaction of dense instances of kSAT ‐formulas, and linear equations mod 2, Ek‐LIN2, do have PTASs for any k. The MIN‐Ek‐LIN2 problems are equivalent to the k‐ary versions of the Nearest Codeword problem, the problem which is known to be exceedingly hard to approximate on general instances. The method of solution of the above problems depends on the development of a new density sampling technique for k‐uniform hypergraphs which could be of independent interest. © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 23: 73–91, 2003     

Complexity of approximating the oriented diameter of chordal graphs

The oriented diameter of a bridgeless connected undirected (bcu) graph G is the smallest diameter among all the diameters of strongly connected orientations of G. We study algorithmic aspects of determining the oriented diameter of a chordal graph. We (a) construct a linear‐time approximation algorithm that, for a given chordal bcu graph G, finds a strongly connected orientation of G with diameter at most one plus twice the oriented diameter of G; (b) prove that, for every k ≥ 2 and k # 3, to decide whether a chordal (split for k = 2) bcu graph G admits an orientation of diameter k is NP‐complete; (c) show that, unless P = NP, there is neither a polynomial‐time absolute approximation algorithm nor an α‐approximation algorithm that computes the oriented diameter of a bcu chordal graph for α < . © 2004 Wiley Periodicals, Inc. J Graph Theory 45: 255–269, 2004     

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     

Optimization on sparse random hypergraphs and spin glasses

We establish that in the large degree limit, the value of certain optimization problems on sparse random hypergraphs is determined by an appropriate Gaussian optimization problem. This approach was initiated in Dembo et al. (2016) for extremal cuts of graphs. The usefulness of this technique is further illustrated by deriving the optimal value for Max q‐cut on graphs, Max XORSAT on Erdős–Rényi hypergraphs, and the min‐bisection the min‐bisection for the Stochastic Block Model.     

Approximation with a fixed number of solutions of some multiobjective maximization problems

We investigate the problem of approximating the Pareto set of some multiobjective optimization problems with a given number of solutions. Our purpose is to exploit general properties that many well studied problems satisfy. We derive existence and constructive approximation results for the biobjective versions of Max Submodular Symmetric Function (and special cases), Max Bisection, and Max Matching and also for the k-objective versions of Max Coverage, Heaviest Subgraph, Max Coloring of interval graphs.     

A generic auction algorithm for the minimum cost network flow problem

In this paper we broadly generalize the assignment auction algorithm to solve linear minimum cost network flow problems. We introduce a generic algorithm, which contains as special cases a number of known algorithms, including the -relaxation method, and the auction algorithm for assignment and for transportation problems. The generic algorithm can serve as a broadly useful framework for the development and the complexity analysis of specialized auction algorithms that exploit the structure of particular network problems. Using this framework, we develop and analyze two new algorithms, an algorithm for general minimum cost flow problems, called network auction, and an algorithm for thek node-disjoint shortest path problem.     

Efficient algorithms for three‐dimensional axial and planar random assignment problems

Beautiful formulas are known for the expected cost of random two‐dimensional assignment problems, but in higher dimensions even the scaling is not known. In three dimensions and above, the problem has natural “Axial” and “Planar” versions, both of which are NP‐hard. For 3‐dimensional Axial random assignment instances of size n, the cost scales as Ω(1/ n), and a main result of the present paper is a linear‐time algorithm that, with high probability, finds a solution of cost O(n^–1+o(1)). For 3‐dimensional Planar assignment, the lower bound is Ω(n), and we give a new efficient matching‐based algorithm that with high probability returns a solution with cost O(n log n). © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 46, 160–196, 2015     

Local discontinuous galerkin approximation of convection‐dominated diffusion optimal control problems with control constraints

In this article, we investigate local discontinuous Galerkin approximation of stationary convection‐dominated diffusion optimal control problems with distributed control constraints. The state variable and adjoint state variable are approximated by piecewise linear polynomials without continuity requirement, whereas the control variable is discretized by variational discretization concept. The discrete first‐order optimality condition is derived. We show that optimization and discretization are commutative for the local discontinuous Galerkin approximation. Because the solutions to convection‐dominated diffusion equations often admit interior or boundary layers, residual type a posteriori error estimate in L² norm is proved, which can be used to guide mesh refinement. Finally, numerical examples are presented to illustrate the theoretical findings. © 2013 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 30: 339–360, 2014     

TV‐like regularization for backward parabolic problems

This paper investigates an inverse problem for parabolic equations backward in time, which is solved by total‐variation‐like (TV‐like, in abbreviation) regularization method with cost function ∥u_x∥². The existence, uniqueness and stability estimate for the regularization problem are deduced in the linear case. For numerical illustration, the variational adjoint method, which presents a simple method to derive the gradient of the optimization functional, is introduced to reconstruct the unknown initial condition for both linear and nonlinear parabolic equations. The conjugate gradient method is used to iteratively search for the optimal approximation. Numerical results validate the feasibility and effectiveness of the proposed algorithm. Copyright © 2016 John Wiley & Sons, Ltd.     

Galerkin method for optimal control of second‐order evolution equations

This paper presents the Galerkin approximation of the optimization problem of a system governed by non‐linear second‐order evolution equation where a non‐linear operator depends on derivative of the state of the system. The control is acting on a non‐linear equation. After giving some results on the existence of optimal control we shall prove the existence of the weak and strong condensation points of a set of solutions of the approximate optimization problems. Each of these points is a solution of the initial optimization problem. Finally we shall give a simple example using the obtained results. Copyright © 2004 John Wiley & Sons, Ltd.     

An algebraic approach to assignment problems

For assignment problems a class of objective functions is studied by algebraic methods and characterized in terms of an axiomatic system. It says essentially that the coefficients of the objective function can be chosen from a totally ordered commutative semigroup, which obeys a divisibility axiom. Special cases of the general model are the linear assignment problem, the linear bottleneck problem, lexicographic multicriteria problems,p-norm assignment problems and others. Further a polynomial bounded algorithm for solving this generalized assignment problem is stated. The algebraic approach can be extended to a broader class of combinatorial optimization problems.     

On the solution‐space geometry of random constraint satisfaction problems

For various random constraint satisfaction problems there is a significant gap between the largest constraint density for which solutions exist and the largest density for which any polynomial time algorithm is known to find solutions. Examples of this phenomenon include random k‐SAT, random graph coloring, and a number of other random constraint satisfaction problems. To understand this gap, we study the structure of the solution space of random k‐SAT (i.e., the set of all satisfying assignments viewed as a subgraph of the Hamming cube). We prove that for densities well below the satisfiability threshold, the solution space decomposes into an exponential number of connected components and give quantitative bounds for the diameter, volume, and number.© 2010 Wiley Periodicals, Inc. Random Struct. Alg., 38, 251–268, 2011     

On two-stage convex chance constrained problems

In this paper we develop approximation algorithms for two-stage convex chance constrained problems. Nemirovski and Shapiro (Probab Randomized Methods Des Uncertain 2004) formulated this class of problems and proposed an ellipsoid-like iterative algorithm for the special case where the impact function f (x, h) is bi-affine. We show that this algorithm extends to bi-convex f (x, h) in a fairly straightforward fashion. The complexity of the solution algorithm as well as the quality of its output are functions of the radius r of the largest Euclidean ball that can be inscribed in the polytope defined by a random set of linear inequalities generated by the algorithm (Nemirovski and Shapiro in Probab Randomized Methods Des Uncertain 2004). Since the polytope determining r is random, computing r is difficult. Yet, the solution algorithm requires r as an input. In this paper we provide some guidance for selecting r. We show that the largest value of r is determined by the degree of robust feasibility of the two-stage chance constrained problem—the more robust the problem, the higher one can set the parameter r. Next, we formulate ambiguous two-stage chance constrained problems. In this formulation, the random variables defining the chance constraint are known to have a fixed distribution; however, the decision maker is only able to estimate this distribution to within some error. We construct an algorithm that solves the ambiguous two-stage chance constrained problem when the impact function f (x, h) is bi-affine and the extreme points of a certain “dual” polytope are known explicitly. Research partially supported by NSF grants CCR-00-09972, DMS-01-04282 and ONR grant N000140310514.     

Fast Kalman Filtering and Forward–Backward Smoothing via a Low-Rank Perturbative Approach

Kalman filtering-smoothing is a fundamental tool in statistical time-series analysis. However, standard implementations of the Kalman filter-smoother require O(d³) time and O(d²) space per time step, where d is the dimension of the state variable, and are therefore impractical in high-dimensional problems. In this article we note that if a relatively small number of observations are available per time step, the Kalman equations may be approximated in terms of a low-rank perturbation of the prior state covariance matrix in the absence of any observations. In many cases this approximation may be computed and updated very efficiently (often in just O(k²d) or O(k²d + kdlog?d) time and space per time step, where k is the rank of the perturbation and in general k ? d), using fast methods from numerical linear algebra. We justify our approach and give bounds on the rank of the perturbation as a function of the desired accuracy. For the case of smoothing, we also quantify the error of our algorithm because of the low-rank approximation and show that it can be made arbitrarily low at the expense of a moderate computational cost. We describe applications involving smoothing of spatiotemporal neuroscience data. This article has online supplementary material.     

An SDP randomized approximation algorithm for max hypergraph cut with limited unbalance

We consider the design of semidefinite programming(SDP) based approximation algorithm for the problem Max Hypergraph Cut with Limited Unbalance(MHC-LU): Find a partition of the vertices of a weighted hypergraph H =(V, E) into two subsets V1, V2 with ‖V2|- |V1‖ u for some given u and maximizing the total weight of the edges meeting both V1 and V2. The problem MHC-LU generalizes several other combinatorial optimization problems including Max Cut, Max Cut with Limited Unbalance(MC-LU), Max Set Splitting,Max Ek-Set Splitting and Max Hypergraph Bisection. By generalizing several earlier ideas, we present an SDP randomized approximation algorithm for MHC-LU with guaranteed worst-case performance ratios for various unbalance parameters τ = u/|V|. We also give the worst-case performance ratio of the SDP-algorithm for approximating MHC-LU regardless of the value of τ. Our strengthened SDP relaxation and rounding method improve a result of Ageev and Sviridenko(2000) on Max Hypergraph Bisection(MHC-LU with u = 0), and results of Andersson and Engebretsen(1999), Gaur and Krishnamurti(2001) and Zhang et al.(2004) on Max Set Splitting(MHC-LU with u = |V|). Furthermore, our new formula for the performance ratio by a tighter analysis compared with that in Galbiati and Maffioli(2007) is responsible for the improvement of a result of Galbiati and Maffioli(2007) on MC-LU for some range of τ.     

A Categorical View to Structural Complexity

In the present work we are interested in to provide a universal language for supporting formalisms to specify the approximation hierarchy system for an abstract NP‐hard optimization problem. This work grew from the idea of providing a categorical view of structural complexity to optimization problems. The direction is aimed towards actually exploring the connections among the structural complexity aspects and categorical concepts, which may be viewed in a high‐level, in a structuralistic sense. After introducing the optimization problems categories OPTS and OPT, as well as related questions, a formal system modelling the approximation hierarchy of a given optimization problem is provided, based on categorical shape theory. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Convergence of euler-stokes splitting of the navier-stokes equations

We consider approximation by partial time steps of a smooth solution of the Navier-Stokes equations in a smooth domain in two or three space dimensions with no-slip boundary condition. For small k > 0, we alternate the solution for time k of the inviscid Euler equations, with tangential boundary condition, and the solution of the linear Stokes equations for time k, with the no-slip condition imposed. We show that this approximation remains bounded in H^2,p and is accurate to order k in L^p for p > ∞. The principal difficulty is that the initial state for each Stokes step has tangential velocity at the boundary generated during the Euler step, and thus does not satisfy the boundary condition for the Stokes step. The validity of such a fractional step method or splitting is an underlying principle for some computational methods. © 1994 John Wiley & Sons, Inc.     

Random k‐SAT and the power of two choices

We study an Achlioptas‐process version of the random k‐SAT process: a bounded number of k‐clauses are drawn uniformly at random at each step, and exactly one added to the growing formula according to a particular rule. We prove the existence of a rule that shifts the satisfiability threshold. This extends a well‐studied area of probabilistic combinatorics (Achlioptas processes) to random CSP's. In particular, while a rule to delay the 2‐SAT threshold was known previously, this is the first proof of a rule to shift the threshold of k‐SAT for . We then propose a gap decision problem based upon this semi‐random model. The aim of the problem is to investigate the hardness of the random k‐SAT decision problem, as opposed to the problem of finding an assignment or certificate of unsatisfiability. Finally, we discuss connections to the study of Achlioptas random graph processes. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 47, 163–173, 2015