Robust discrete optimization and network flows

We propose an approach to address data uncertainty for discrete optimization and network flow problems that allows controlling the degree of conservatism of the solution, and is computationally tractable both practically and theoretically. In particular, when both the cost coefficients and the data in the constraints of an integer programming problem are subject to uncertainty, we propose a robust integer programming problem of moderately larger size that allows controlling the degree of conservatism of the solution in terms of probabilistic bounds on constraint violation. When only the cost coefficients are subject to uncertainty and the problem is a 0–1 discrete optimization problem on n variables, then we solve the robust counterpart by solving at most n+1 instances of the original problem. Thus, the robust counterpart of a polynomially solvable 0–1 discrete optimization problem remains polynomially solvable. In particular, robust matching, spanning tree, shortest path, matroid intersection, etc. are polynomially solvable. We also show that the robust counterpart of an NP-hard -approximable 0–1 discrete optimization problem, remains -approximable. Finally, we propose an algorithm for robust network flows that solves the robust counterpart by solving a polynomial number of nominal minimum cost flow problems in a modified network. The research of the author was partially supported by the Singapore-MIT alliance.The research of the author is supported by a graduate scholarship from the National University of Singapore.Mathematics Subject Classification (2000): 90C10, 90C15     

A C0 interior penalty method for a singularly‐perturbed fourth‐order elliptic problem on a layer‐adapted mesh

We analyze the convergence of a continuous interior penalty (CIP) method for a singularly perturbed fourth‐order elliptic problem on a layer‐adapted mesh. On this anisotropic mesh, we prove under reasonable assumptions uniform convergence of almost order k ? 1 for finite elements of degree k ≥ 2. This result is of better order than the known robust result on standard meshes. A by‐product of our analysis is an analytic lower bound for the penalty of the symmetric CIP method. Finally, our convergence result is verified numerically. © 2013 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 30: 838–861, 2014     

p -Sparse BEM for weakly singular integral equation with random data

We consider the weakly singular boundary integral equation 𝒱u = g on a randomly perturbed smooth closed surface Γ(ω) with deterministic g or on a deterministic closed surface Γ with stochastic g (ω). The aim is the computation of the centered moments ℳ︁^k u, k ⩾ 1, if the corresponding moments of the perturbation are known. The problem on the stochastic surface is reduced to a problem on the nominal deterministic surface Γ with the random perturbation parameter κ (ω). Resulting formulation for the k th moment is posed in the tensor product Sobolev spaces and involve the k -fold tensor product operators. The standard full tensor product Galerkin BEM requires 𝒪(N^k) unknowns for the k th moment problem, where N is the number of unknowns needed to discretize the nominal surface Γ. Based on [1], we develop the p -sparse grid Galerkin BEM to reduce the number of unknowns to 𝒪(N (log N)^{k –1}) (cf. [2], [3] for the wavelet approach). (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Torpid mixing of the Wang–Swendsen–Kotecký algorithm for sampling colorings

We study the problem of sampling uniformly at random from the set of k-colorings of a graph with maximum degree Δ. We focus attention on the Markov chain Monte Carlo method, particularly on a popular Markov chain for this problem, the Wang–Swendsen–Kotecký (WSK) algorithm. The second author recently proved that the WSK algorithm quickly converges to the desired distribution when k11Δ/6. We study how far these positive results can be extended in general. In this note we prove the first non-trivial results on when the WSK algorithm takes exponentially long to reach the stationary distribution and is thus called torpidly mixing. In particular, we show that the WSK algorithm is torpidly mixing on a family of bipartite graphs when 3k<Δ/(20logΔ), and on a family of planar graphs for any number of colors. We also give a family of graphs for which, despite their small chromatic number, the WSK algorithm is not ergodic when kΔ/2, provided k is larger than some absolute constant k₀.     

Codes from incidence matrices of graphs

We examine the p-ary codes, for any prime p, from the row span over ${\mathbb {F}_p}$ of |V| × |E| incidence matrices of connected graphs Γ = (V, E), showing that certain properties of the codes can be directly derived from the parameters and properties of the graphs. Using the edge-connectivity of Γ (defined as the minimum number of edges whose removal renders Γ disconnected) we show that, subject to various conditions, the codes from such matrices for a wide range of classes of connected graphs have the property of having dimension |V| or |V| ? 1, minimum weight the minimum degree δ(Γ), and the minimum words the scalar multiples of the rows of the incidence matrix of this weight. We also show that, in the k-regular case, there is a gap in the weight enumerator between k and 2k ? 2 of the binary code, and also for the p-ary code, for any prime p, if Γ is bipartite. We examine also the implications for the binary codes from adjacency matrices of line graphs. Finally we show that the codes of many of these classes of graphs can be used for permutation decoding for full error correction with any information set.     

Channel assignment on Cayley graphs

We address various channel assignment problems on the Cayley graphs of certain groups, computing the frequency spans by applying group theoretic techniques. In particular, we show that if G is the Cayley graph of an n‐generated group Γ with a certain kind of presentation, then λ(G;k, 1)≤2(k+n?1). For certain values of k this bound gives the obvious optimal value for any 2n‐regular graph. A large number of groups (for instance, even Artin groups and a number of Baumslag–Solitar groups) satisfy this condition. © 2010 Wiley Periodicals, Inc. J Graph Theory 67: 169‐177, 2011     

Mean distance in a graph

The average or mean of the distances between vertices in a connected graph Γ, μ(Γ), is a natural measure of the compactness of the graph. In this paper we compute bounds for μ(Γ) in terms of the number of vertices in Γ and the diameter of Γ. We prove a formula for computing μ(Γ) when Γ is a tree which is particularly useful when Γ has a high degree of symmetry. Finally, we present algorithms for μ(Γ) which are amenable to computer implementation.     

Very rapid mixing of the Glauber dynamics for proper colorings on bounded‐degree graphs

Recent results have shown that the Glauber dynamics for graph colorings has optimal mixing time when (i) the graph is triangle‐free and Δ‐regular and the number of colors k is a small constant fraction smaller than 2Δ, or (ii) the graph has maximum degree Δ and k=2Δ. We extend both these results to prove that the Glauber dynamics has optimal mixing time when the graph has maximum degree Δ and the number of colors is a small constant fraction smaller than 2Δ. © 2002 John Wiley & Sons, Inc. Random Struct. Alg., 20, 98–114, 2002     

Spanning k‐arc‐strong subdigraphs with few arcs in k‐arc‐strong tournaments

Given a k‐arc‐strong tournament T, we estimate the minimum number of arcs possible in a k‐arc‐strong spanning subdigraph of T. We give a construction which shows that for each k ≥ 2, there are tournaments T on n vertices such that every k‐arc‐strong spanning subdigraph of T contains at least arcs. In fact, the tournaments in our construction have the property that every spanning subdigraph with minimum in‐ and out‐degree at least k has arcs. This is best possible since it can be shown that every k‐arc‐strong tournament contains a spanning subdigraph with minimum in‐ and out‐degree at least k and no more than arcs. As our main result we prove that every k‐arc‐strong tournament contains a spanning k‐arc‐strong subdigraph with no more than arcs. We conjecture that for every k‐arc‐strong tournament T, the minimum number of arcs in a k‐arc‐strong spanning subdigraph of T is equal to the minimum number of arcs in a spanning subdigraph of T with the property that every vertex has in‐ and out‐degree at least k. We also discuss the implications of our results on related problems and conjectures. © 2004 Wiley Periodicals, Inc. J Graph Theory 46: 265–284, 2004     

An Efficient Algorithm for Bayesian Nearest Neighbours

K-Nearest Neighbours (k-NN) is a popular classification and regression algorithm, yet one of its main limitations is the difficulty in choosing the number of neighbours. We present a Bayesian algorithm to compute the posterior probability distribution for k given a target point within a data-set, efficiently and without the use of Markov Chain Monte Carlo (MCMC) methods or simulation—alongside an exact solution for distributions within the exponential family. The central idea is that data points around our target are generated by the same probability distribution, extending outwards over the appropriate, though unknown, number of neighbours. Once the data is projected onto a distance metric of choice, we can transform the choice of k into a change-point detection problem, for which there is an efficient solution: we recursively compute the probability of the last change-point as we move towards our target, and thus de facto compute the posterior probability distribution over k. Applying this approach to both a classification and a regression UCI data-sets, we compare favourably and, most importantly, by removing the need for simulation, we are able to compute the posterior probability of k exactly and rapidly. As an example, the computational time for the Ripley data-set is a few milliseconds compared to a few hours when using a MCMC approach.

     

A hybrid numerical-asymptotic boundary integral method for high-frequency acoustic scattering

We propose a new robust method for the computation of scattering of high-frequency acoustic plane waves by smooth convex objects in 2D. We formulate this problem by the direct boundary integral method, using the classical combined potential approach. By exploiting the known asymptotics of the solution, we devise particular expansions, valid in various zones of the boundary, which express the solution of the integral equation as a product of explicit oscillatory functions and more slowly varying unknown amplitudes. The amplitudes are approximated by polynomials (of minimum degree d) in each zone using a Galerkin scheme. We prove that the underlying bilinear form is continuous in L ₂, with a continuity constant that grows mildly in the wavenumber k. We also show that the bilinear form is uniformly L ₂-coercive, independent of k, for all k sufficiently large. (The latter result depends on rather delicate Fourier analysis and is restricted in 2D to circular domains, but it also applies to spheres in higher dimensions.) Using these results and the asymptotic expansion of the solution, we prove superalgebraic convergence of our numerical method as d → ∞ for fixed k. We also prove that, as k → ∞, d has to increase only very modestly to maintain a fixed error bound (d ∼ k ^1/9 is a typical behaviour). Numerical experiments show that the method suffers minimal loss of accuracy as k →∞, for a fixed number of degrees of freedom. Numerical solutions with a relative error of about 10⁻⁵ are obtained on domains of size for k up to 800 using about 60 degrees of freedom.     

A note on the girth‐doubling construction for polygonal graphs

A near‐polygonal graph is a graph Γ which has a set ?? of m‐cycles for some positive integer m such that each 2‐path of Γ is contained in exactly one cycle in ??. If m is the girth of Γ then the graph is called polygonal. Given a polygonal graph Γ of valency r and girth m, Archdeacon and Perkel proved the existence of a polygonal graph Γ₂ of valency r and girth 2m. We will show that this construction can be extended to one that yields a polygonal graph Γ₃ of valency r and girth 3m, but that making the cycles any longer with this construction does not yield a polygonal graph. We also show that if Aut(Γ) is 2‐arc transitive, so is Aut(Γ_k) for k = 2, 3. © 2010 Wiley Periodicals, Inc. J Graph Theory 68: 246‐254, 2011     

On the Size‐Ramsey Number of Hypergraphs

The size‐Ramsey number of a graph G is the minimum number of edges in a graph H such that every 2‐edge‐coloring of H yields a monochromatic copy of G. Size‐Ramsey numbers of graphs have been studied for almost 40 years with particular focus on the case of trees and bounded degree graphs. We initiate the study of size‐Ramsey numbers for k‐uniform hypergraphs. Analogous to the graph case, we consider the size‐Ramsey number of cliques, paths, trees, and bounded degree hypergraphs. Our results suggest that size‐Ramsey numbers for hypergraphs are extremely difficult to determine, and many open problems remain.     

Asymptotic Conditions for Degree Diminution Along Prescribed Lines

One of the problems in bivariate polynomial interpolation is the choice of a space of polynomials suitable for interpolating a given set of data. Depending on the number of data, a usual space is that of polynomials in 2 variables of total degree not greater than k. However, these spaces are not enough to cover many interpolation problems. Here, we are interested in spaces of polynomials of total degree not greater than k whose degree diminishes along some prescribed directions. These spaces arise naturally in some interpolation problems and we describe them in terms of polynomials satisfying some asymptotic interpolation conditions. This provides a general frame to the interpolation problems studied in some of our recent papers.     

Robust Stability Criteria for Uncertain Neutral Systems with Interval Time-Varying Delay

In this paper, we consider the problem of robust stability of a class of linear uncertain neutral systems with interval time-varying delay under (i) nonlinear perturbations in state, and (ii) time-varying parametric uncertainties using Lyapunov-Krasovskii approach. By constructing a candidate Lyapunov-Krasovskii (LK) functional, that takes into account the delay-range information appropriately, less conservative robust stability criteria are proposed in terms of linear matrix inequalities (LMI) to compute the maximum allowable bound for the delay-range within which the uncertain neutral system under consideration remains asymptotically stable. The reduction in conservatism of the proposed stability criterion over recently reported results is attributed to the fact that time-derivative of the LK functional is bounded tightly without neglecting any useful terms using a minimal number of slack matrix variables. The analysis, subsequently, yields a stability condition in convex LMI framework, that can be solved non-conservatively at boundary conditions using standard LMI solvers. The effectiveness of the proposed stability criterion is demonstrated through standard numerical examples.     

A decision-theoretic approach to robust optimization in multivalued graphs

This paper is devoted to the search of robust solutions in finite graphs when costs depend on scenarios. We first point out similarities between robust optimization and multiobjective optimization. Then, we present axiomatic requirements for preference compatibility with the intuitive idea of robustness in a multiple scenarios decision context. This leads us to propose the Lorenz dominance rule as a basis for robustness analysis. Then, after presenting complexity results about the determination of Lorenz optima, we show how the search can be embedded in algorithms designed to enumerate k best solutions. Then, we apply it in order to enumerate Lorenz optimal spanning trees and paths. We investigate possible refinements of Lorenz dominance and we propose an axiomatic justification of OWA operators in this context. Finally, the results of numerical experiments on randomly generated graphs are provided. They show the numerical efficiency of the suggested approach.     

A new frequency‐uniform coercive boundary integral equation for acoustic scattering

A new boundary integral operator is introduced for the solution of the soundsoft acoustic scattering problem, i.e., for the exterior problem for the Helmholtz equation with Dirichlet boundary conditions. We prove that this integral operator is coercive in L²(Γ) (where Γ is the surface of the scatterer) for all Lipschitz star‐shaped domains. Moreover, the coercivity is uniform in the wavenumber k = ω/c, where ω is the frequency and c is the speed of sound. The new boundary integral operator, which we call the “star‐combined” potential operator, is a slight modification of the standard combined potential operator, and is shown to be as easy to implement as the standard one. Additionally, to the authors' knowledge, it is the only second‐kind integral operator for which convergence of the Galerkin method in L²(Γ) is proved without smoothness assumptions on Γ except that it is Lipschitz. The coercivity of the star‐combined operator implies frequency‐explicit error bounds for the Galerkin method for any approximation space. In particular, these error estimates apply to several hybrid asymptoticnumerical methods developed recently that provide robust approximations in the high‐frequency case. The proof of coercivity of the star‐combined operator critically relies on an identity first introduced by Morawetz and Ludwig in 1968, supplemented further by more recent harmonic analysis techniques for Lipschitz domains. © 2011 Wiley Periodicals, Inc.