Computing an Eigenvector of a Monge Matrix in Max-Plus Algebra

The problem of finding one eigenvector of a given Monge matrix A in a max-plus algebra is considered. For a general matrix, the problem can be solved in O(n ³) time by computing one column of the corresponding metric matrix Δ(A _λ), where λ is the eigenvalue of A. An algorithm is presented, which computes an eigenvector of a Monge matrix in O(n ²) time.     

Sharp regularity results on second derivatives of solutions to the Monge‐Ampère equation with VMO type data

We establish interior estimates for L^p‐norms, Orlicz norms, and mean oscillation of second derivatives of solutions to the Monge‐Ampère equation det D²u = f(x) with zero boundary value, where f(x) is strictly positive, bounded, and satisfies a VMO‐type condition. These estimates develop the regularity theory of the Monge‐Ampère equation in VMO‐type spaces. Our Orlicz estimates also sharpen Caffarelli's celebrated W^{2, p}‐estimates. © 2008 Wiley Periodicals, Inc.     

A Global Optimization RLT-based Approach for Solving the Fuzzy Clustering Problem

The field of cluster analysis is primarily concerned with the partitioning of data points into different clusters so as to optimize a certain criterion. Rapid advances in technology have made it possible to address clustering problems via optimization theory. In this paper, we present a global optimization algorithm to solve the fuzzy clustering problem, where each data point is to be assigned to (possibly) several clusters, with a membership grade assigned to each data point that reflects the likelihood of the data point belonging to that cluster. The fuzzy clustering problem is formulated as a nonlinear program, for which a tight linear programming relaxation is constructed via the Reformulation-Linearization Technique (RLT) in concert with additional valid inequalities. This construct is embedded within a specialized branch-and-bound (B&B) algorithm to solve the problem to global optimality. Computational experience is reported using several standard data sets from the literature as well as using synthetically generated larger problem instances. The results validate the robustness of the proposed algorithmic procedure and exhibit its dominance over the popular fuzzy c-means algorithmic technique and the commercial global optimizer BARON.     

Approximation algorithms for supply chain planning and logistics problems with market choice

We propose generalizations of a broad class of traditional supply chain planning and logistics models that we call supply chain planning and logistics problems with market choice. Instead of the traditional setting, we are given a set of markets, each specified by a sequence of demands and associated with a revenue. Decisions are made in two stages. In the first stage, one chooses a subset of markets and rejects the others. Once that market choice is made, one needs to construct a minimum-cost production plan (set of facilities) to satisfy all of the demands of all the selected markets. The goal is to minimize the overall lost revenues of rejected markets and the production (facility opening and connection) costs. These models capture important aspects of demand shaping within supply chain planning and logistics models. We introduce a general algorithmic framework that leverages existing approximation results for the traditional models to obtain corresponding results for their counterpart models with market choice. More specifically, any LP-based α-approximation for the traditional model can be leveraged to a \frac11-e^-1/a{\frac{1}{1-e^{-1/\alpha}}} -approximation algorithm for the counterpart model with market choice. Our techniques are also potentially applicable to other covering problems.     

Partial Regularity for Singular Solutions to the Monge‐Ampère Equation

We prove that solutions to the Monge‐Ampère inequality in ?ⁿ are strictly convex away from a singular set of Hausdorff (n‐1)‐dimensional measure zero. Furthermore, we show this is optimal by constructing solutions to det D²u = 1 with singular set of Hausdorff dimension as close as we like to n‐1. As a consequence we obtain W^2,1 regularity for the Monge‐Ampère equation with bounded right‐hand side and unique continuation for the Monge‐Ampère equation with sufficiently regular right‐hand side. © 2015 Wiley Periodicals, Inc.     

A Global Optimization RLT-based Approach for Solving the Hard Clustering Problem

The field of cluster analysis is primarily concerned with the sorting of data points into different clusters so as to optimize a certain criterion. Rapid advances in technology have made it possible to address clustering problems via optimization theory. In this paper, we present a global optimization algorithm to solve the hard clustering problem, where each data point is to be assigned to exactly one cluster. The hard clustering problem is formulated as a nonlinear program, for which a tight linear programming relaxation is constructed via the Reformulation-Linearization Technique (RLT) in concert with additional valid inequalities that serve to defeat the inherent symmetry in the problem. This construct is embedded within a specialized branch-and-bound algorithm to solve the problem to global optimality. Pertinent implementation issues that can enhance the efficiency of the branch-and-bound algorithm are also discussed. Computational experience is reported using several standard data sets found in the literature as well as using synthetically generated larger problem instances. The results validate the robustness of the proposed algorithmic procedure and exhibit its dominance over the popular k-means clustering technique. Finally, a heuristic procedure to obtain a good quality solution at a relative ease of computational effort is also described.     

On the Intrinsic Complexity of Elimination Theory

We consider the intrinsic complexity of selected algorithmic problems of classical elimination theory in algebraic geometry. The inputs and outputs of these problems are given by finite sets of polynomials which we represent alternatively in dense form or by straight line programs. We begin with an overview on the known upper bounds for the sequential and parallel time complexity of these problems and show then that in the most important cases these bounds are tight. Our lower bound results include both the relative and the absolute viewpoint of complexity theory. On one side we give reductions of fundamental questions of elimination theory to NP- and P^#-complete problems and on the other side we show that some of these questions may have exponential size outputs. In this way we confirm the intrinsically exponential character of algorithmic problems in elimination theory whatever the type of data structure may be.     

Non-uniform exponential tension splines

We describe explicitly each stage of a numerically stable algorithm for calculating with exponential tension B-splines with non-uniform choice of tension parameters. These splines are piecewisely in the kernel of D ²(D ²–p ²), where D stands for ordinary derivative, defined on arbitrary meshes, with a different choice of the tension parameter p on each interval. The algorithm provides values of the associated B-splines and their generalized and ordinary derivatives by performing positive linear combinations of positive quantities, described as lower-order exponential tension splines. We show that nothing else but the knot insertion algorithm and good approximation of a few elementary functions is needed to achieve machine accuracy. The underlying theory is that of splines based on Chebyshev canonical systems which are not smooth enough to be ECC-systems. First, by de Boor algorithm we construct exponential tension spline of class C ¹, and then we use quasi-Oslo type algorithms to evaluate classical non-uniform C ² tension exponential splines.      

Improving the Data Augmentation Algorithm in the Two-Block Setup

The data augmentation (DA) approach to approximate sampling from an intractable probability density f_X is based on the construction of a joint density, f_{X, Y}, whose conditional densities, f_X|Y and f_Y|X, can be straightforwardly sampled. However, many applications of the DA algorithm do not fall in this “single-block” setup. In these applications, X is partitioned into two components, X = (U, V), in such a way that it is easy to sample from f_Y|X, f_{U|V, Y}, and f_{V|U, Y}. We refer to this alternative version of DA, which is effectively a three-variable Gibbs sampler, as “two-block” DA. We develop two methods to improve the performance of the DA algorithm in the two-block setup. These methods are motivated by the Haar PX-DA algorithm, which has been developed in previous literature to improve the performance of the single-block DA algorithm. The Haar PX-DA algorithm, which adds a computationally inexpensive extra step in each iteration of the DA algorithm while preserving the stationary density, has been shown to be optimal among similar techniques. However, as we illustrate, the Haar PX-DA algorithm does not lead to the required stationary density f_X in the two-block setup. Our methods incorporate suitable generalizations and modifications to this approach, and work in the two-block setup. A theoretical comparison of our methods to the two-block DA algorithm, a much harder task than the single-block setup due to nonreversibility and structural complexities, is provided. We successfully apply our methods to applications of the two-block DA algorithm in Bayesian robit regression and Bayesian quantile regression. Supplementary materials for this article are available online.     

Feedback Vertex Sets in Tournaments

We study combinatorial and algorithmic questions around minimal feedback vertex sets (FVS) in tournament graphs. On the combinatorial side, we derive upper and lower bounds on the maximum number of minimal FVSs in an n‐vertex tournament. We prove that every tournament on n vertices has at most 1.6740ⁿ minimal FVSs, and that there is an infinite family of tournaments, all having at least 1.5448ⁿ minimal FVSs. This improves and extends the bounds of Moon (1971). On the algorithmic side, we design the first polynomial space algorithm that enumerates the minimal FVSs of a tournament with polynomial delay. The combination of our results yields the fastest known algorithm for finding a minimum‐sized FVS in a tournament.     

Optimal Prefix-Free Codes for Unequal Letter Costs: Dynamic Programming with the Monge Property

In this paper we discuss the problem of finding optimal prefix-free codes for unequal letter costs, a variation of the classical Huffman coding problem. Our problem consists of finding a minimal cost prefix-free code in which the encoding alphabet consists of unequal cost (length) letters, with lengths α and β. The most efficient algorithm known previously requires O(n^{2 + max(α, β)}) time to construct such a minimal-cost set of n codewords, provided α and β are integers. In this paper we provide an O(n^max(α, β)) time algorithm. Our improvement comes from the use of a more sophisticated modeling of the problem, combined with the observation that the problem possesses a “Monge property” and that the SMAWK algorithm on monotone matrices can therefore be applied.     

Robust statistical modeling using the Birnbaum‐Saunders‐t distribution applied to insurance

In this paper, we carry out robust modeling and influence diagnostics in Birnbaum‐Saunders (BS) regression models. Specifically, we present some aspects related to BS and log‐BS distributions and their generalizations from the Student‐t distribution, and develop BS‐t regression models, including maximum likelihood estimation based on the EM algorithm and diagnostic tools. In addition, we apply the obtained results to real data from insurance, which shows the uses of the proposed model. Copyright © 2011 John Wiley & Sons, Ltd.     

Small Spectral Gap in the Combinatorial Laplacian Implies Hamiltonian

We consider the spectral and algorithmic aspects of the problem of finding a Hamiltonian cycle in a graph. We show that a sufficient condition for a graph being Hamiltonian is that the nontrivial eigenvalues of the combinatorial Laplacian are sufficiently close to the average degree of the graph. An algorithm is given for the problem of finding a Hamiltonian cycle in graphs with bounded spectral gaps which has complexity of order n ^{cln n} .     

On the theory of mappings with finite area distortion

It is shown that mappings in ℝⁿ with finite distortion of area in all dimensions 1 ≤ k ≤ n − 1 satisfy certain modulus inequalities in terms of inner and outer dilatations of the mappings; in particular, generalizations of the well-known Poletskii inequality for quasiregular mappings are proved. The theory developed is applicable, for example, to the class of finitely bi-Lipschitz mappings, which is a natural generalization of the bi-Lipschitz mappings, as well as isometries and quasi-isometries in ℝⁿ.     

Simplicial approximation of solutions to the nonlinear complementarity problem with lower and upper bounds

Ideas of a simplicial variable dimension restart algorithm to approximate zero points onR ⁿ developed by the authors and of a linear complementarity problem pivoting algorithm are combined to an algorithm for solving the nonlinear complementarity problem with lower and upper bounds. The algorithm can be considered as a modification of the2n-ray zero point finding algorithm onR ⁿ . It appears that for the new algorithm the number of linear programming pivot steps is typically less than for the2n-ray algorithm applied to an equivalent zero point problem. This is caused by the fact that the algorithm utilizes the complementarity conditions on the variables. This work is part of the VF-program “Equilibrium and Disequilibrium in Demand and Supply,” which has been approved by the Netherlands Ministry of Education and Sciences.     

Duality theorems on an infinite network *

We study conjugate duality for optimization problems on an infinite, but locally finite network with countable node set X and countable are set Y In contrast to earlier approaches we do not employ Hilbert or Banach space methods. Instead we work in the spaces R^X and R^Y which are siven their Droduct toDolosv, As an application we obtain generalizations of some basic inverse relations from discrete potential theory     

Programmed interactions in higher-order neural networks: The outer-product algorithm

Recent results on the memory storage capacity of the outer-product algorithm indicate that the algorithm stores of the order of n/log n memories in a network of n fully interconnected linear threshold elements when it is required that each memory be exactly recovered from a probe which is close enough to it. In this paper a rigourous analysis is presented of generalizations of the outer-product algorithm to higher-order networks of densely interconnected polynomial thresh-old units of degree d. Precise notions of memory storage capacity are formulated, and it is demonstrated that both static and dynamic storage capacities of all variants of the outer-product algorithm of degree d are of the order of n^d/log n.     

Convergence of a fourth-order singular perturbation of the n-dimensional radially symmetric Monge–Ampère equation

This paper concerns with the convergence analysis of a fourth-order singular perturbation of the Dirichlet Monge–Ampère problem in the n-dimensional radial symmetric case. A detailed study of the fourth- order problem is presented. In particular, various a priori estimates with explicit dependence on the perturbation parameter ε are derived, and a crucial convexity property is also proved for the solution of the fourth-order problem. Using these estimates and the convexity property, we prove that the solution of the perturbed problem converges uniformly and compactly to the unique convex viscosity solution of the Dirichlet Monge–Ampère problem. Rates of convergence in the H^k-norm for k = 0, 1, 2 are also established.