The Isomorphism Problem for All Hyperbolic Groups

We give a solution to Dehn’s isomorphism problem for the class of all hyperbolic groups, possibly with torsion. We also prove a relative version for groups with peripheral structures. As a corollary, we give a uniform solution to Whitehead’s problem asking whether two tuples of elements of a hyperbolic group G are in the same orbit under the action of Aut(G). We also get an algorithm computing a generating set of the group of automorphisms of a hyperbolic group preserving a peripheral structure.     

Global Optimization of 0-1 Hyperbolic Programs

We develop eight different mixed-integer convex programming reformulations of 0-1 hyperbolic programs. We obtain analytical results on the relative tightness of these formulations and propose a branch and bound algorithm for 0-1 hyperbolic programs. The main feature of the algorithm is that it reformulates the problem at every node of the search tree. We demonstrate that this algorithm has a superior convergence behavior than directly solving the relaxation derived at the root node. The algorithm is used to solve a discrete p-choice facility location problem for locating ten restaurants in the city of Edmonton.The research was supported in part by NSF awards DMII 95-02722 and BES 98-73586 to NVS.     

A boundary-value problem in an unbounded strip

Using the generalized scheme of the method of separation of variables we propose a new approach to the study of a boundary-value problem in an unbounded strip for hyperbolic partial differential equations of even order with respect to time. In the space of entire functions of exponential type (with respect to the spatial variable) we single out a unique solution class for the problem and exhibit an algorithm for constructing a solution of it. Translated fromMatematicheskie Metody i Fiziko-Mekhanicheskie Polya, No. 37, 1994, pp. 16–21.     

The isomorphism problem for toral relatively hyperbolic groups

We provide a solution to the isomorphism problem for torsion-free relatively hyperbolic groups with abelian parabolics. As special cases we recover solutions to the isomorphism problem for: (i) torsion-free hyperbolic groups (Sela, [60] and unpublished); and (ii) finitely generated fully residually free groups (Bumagin, Kharlampovich and Miasnikov [14]). We also give a solution to the homeomorphism problem for finite volume hyperbolic n-manifolds, for n≥3. In the course of the proof of the main result, we prove that a particular JSJ decomposition of a freely indecomposable torsion-free relatively hyperbolic group with abelian parabolics is algorithmically constructible.     

Adaptive multiscale scheme based on numerical density of entropy production for conservation laws

We propose a 1D adaptive numerical scheme for hyperbolic conservation laws based on the numerical density of entropy production (the amount of violation of the theoretical entropy inequality). This density is used as an a posteriori error which provides information if the mesh should be refined in the regions where discontinuities occur or coarsened in the regions where the solution remains smooth. As due to the Courant-Friedrich-Levy stability condition the time step is restricted and leads to time consuming simulations, we propose a local time stepping algorithm. We also use high order time extensions applying the Adams-Bashforth time integration technique as well as the second order linear reconstruction in space. We numerically investigate the efficiency of the scheme through several test cases: Sod’s shock tube problem, Lax’s shock tube problem and the Shu-Osher test problem.     

Criteria of unique solvability of nonlocal boundary-value problem for systems of hyperbolic equations with mixed derivatives

We consider nonlocal boundary-value problem for a system of hyperbolic equations with two independent variables. We investigate questions of existence of unique classical solution to problem under consideration. In terms of initial data we propose criteria of unique solvability and suggest algorithms of finding of solutions to nonlocal boundary-value problem. As an application we give conditions of solvability of periodic boundary-value problem for a system of hyperbolic equations.     

An optimization-based heuristic for the robotic cell problem

This study investigates an optimization-based heuristic for the robotic cell problem. This problem arises in automated cells and is a complex flow shop problem with a single transportation robot and a blocking constraint. We propose an approximate decomposition algorithm. The proposed approach breaks the problem into two scheduling problems that are solved sequentially: a flow shop problem with additional constraints (blocking and transportation times) and a single machine problem with precedence constraints, time lags, and setup times. For each of these problems, we propose an exact branch-and-bound algorithm. Also, we describe a genetic algorithm that includes, as a mutation operator, a local search procedure. We report the results of a computational study that provides evidence that the proposed optimization-based approach delivers high-quality solutions and consistently outperforms the genetic algorithm. However, the genetic algorithm delivers reasonably good solutions while requiring significantly shorter CPU times.     

An approximation algorithm for the traveling tournament problem

This paper describes the traveling tournament problem, a well-known benchmark problem in the field of tournament timetabling. We propose a new lower bound for the traveling tournament problem, and construct a randomized approximation algorithm yielding a feasible solution whose approximation ratio is less than 2+(9/4)/(n−1), where n is the number of teams. Additionally, we propose a deterministic approximation algorithm with the same approximation ratio using a derandomization technique. For the traveling tournament problem, the proposed algorithms are the first approximation algorithms with a constant approximation ratio, which is less than 2+3/4.     

Hyperbolic smoothing function method for minimax problems

In this article, an approach for solving finite minimax problems is proposed. This approach is based on the use of hyperbolic smoothing functions. In order to apply the hyperbolic smoothing we reformulate the objective function in the minimax problem and study the relationship between the original minimax and reformulated problems. We also study main properties of the hyperbolic smoothing function. Based on these results an algorithm for solving the finite minimax problem is proposed and this algorithm is implemented in general algebraic modelling system. We present preliminary results of numerical experiments with well-known nonsmooth optimization test problems. We also compare the proposed algorithm with the algorithm that uses the exponential smoothing function as well as with the algorithm based on nonlinear programming reformulation of the finite minimax problem.     

On the unique solvability of a family of two-point boundary-value problems for systems of ordinary differential equations

We consider a family of two-point boundary-value problems for systems of ordinary differential equations with functional parameters. This family is the result of the reduction of a boundary-value problem with nonlocal condition for a system of second-order, quasilinear hyperbolic equations by the introduction of additional functions. Using the parametrization method, we establish necessary and sufficient conditions of the unique solvability of the family of two-point boundary-value problems for a linear system in terms of the initial data. We also prove sufficient conditions of the unique solvability of the problem considered and propose an algorithm for its solution. __________ Translated from Fundamentalnaya i Prikladnaya Matematika, Vol. 12, No. 4, pp. 21–39, 2006.     

Efficient risk simulations for linear asset portfolios in the t-copula model

We consider the problem of calculating tail probabilities of the returns of linear asset portfolios. As a flexible and accurate model for the logarithmic returns we use the t-copula dependence structure and marginals following the generalized hyperbolic distribution. Exact calculation of the tail-loss probabilities is not possible and even simulation leads to challenging numerical problems. Applying a new numerical inversion method for the generation of the marginals and importance sampling with carefully selected mean shift we develop an efficient simulation algorithm. Numerical results for a variety of realistic portfolio examples show an impressive performance gain.     

Exploring the constrained maximum edge-weight connected graph problem

Given an edge weighted graph, the maximum edge-weight connected graph （MECG） is a connected subgraph with a given number of edges and the maximal weight sum. Here we study a special case, i.e. the Constrained Maximum Edge-Weight Connected Graph problem （CMECG）, which is an MECG whose candidate subgraphs must include a given set of k edges, then also called the k-CMECG. We formulate the k-CMECG into an integer linear programming model based on the network flow problem. The k-CMECG is proved to be NP-hard. For the special case 1-CMECG, we propose an exact algorithm and a heuristic algorithm respectively. We also propose a heuristic algorithm for the k-CMECG problem. Some simulations have been done to analyze the quality of these algorithms. Moreover, we show that the algorithm for 1-CMECG problem can lead to the solution of the general MECG problem.     

Memetic algorithm for the antibandwidth maximization problem

The antibandwidth maximization problem (AMP) consists of labeling the vertices of a n-vertex graph G with distinct integers from 1 to n such that the minimum difference of labels of adjacent vertices is maximized. This problem can be formulated as a dual problem to the well known bandwidth problem. Exact results have been proved for some standard graphs like paths, cycles, 2 and 3-dimensional meshes, tori, some special trees etc., however, no algorithm has been proposed for the general graphs. In this paper, we propose a memetic algorithm for the antibandwidth maximization problem, wherein we explore various breadth first search generated level structures of a graph—an imperative feature of our algorithm. We design a new heuristic which exploits these level structures to label the vertices of the graph. The algorithm is able to achieve the exact antibandwidth for the standard graphs as mentioned. Moreover, we conjecture the antibandwidth of some 3-dimensional meshes and complement of power graphs, supported by our experimental results.     

Boundary difference-integral equation method and its error estimates for second order hyperbolic partial differential equation

Combining difference method and boundary integral equation method, we propose a new numerical method for solving initial-boundary value problem of second order hyperbolic partial differential equations defined on a bounded or unbounded domain inR ³ and obtain the error estimates of the approximate solution in energy norm and local maximum norm.China State Major Key Project for Basic Researches.     

A high-precision projection method for a fourth-order differential equation

Using the projection method we construct two difference schemes for a boundary-value problem for a fourth-order ordinary differential equation. We propose a high-precision algorithm whose output is the sum of the solution of an algebraic problem with a symmetric matrix and a polynomial correction.Translated fromVychislitel'naya i Prikladnaya Matematika, Issue 71, 1990, pp. 27–33.     

Asymptotic expansions for hyperbolic–parabolic systems with a small parameter

In this paper we consider initial-boundary value problems for systems with a small parameter ?. The problems are mixed hyperbolic–parabolic when ? > 0 and hyperbolic when ? = 0. Often the solution can be expanded asymptotically in ? and to first approximation it consists of the solution of the corresponding hyperbolic problem and a boundary layer part. We prove sufficient conditions for the expansion to exist and give estimates of the remainder. We also examine how the boundary conditions should be choosen to avoid O(1) boundary layers.     

A Lagrangian Based Branch-and-Bound Algorithm for Production-transportation Problems

We propose a branch-and-bound algorithm of Falk–Soland's type for solving the minimum cost production-transportation problem with concave production costs. To accelerate the convergence of the algorithm, we reinforce the bounding operation using a Lagrangian relaxation, which is a concave minimization but yields a tighter bound than the usual linear programming relaxation in O(mn log n) additional time. Computational results indicate that the algorithm can solve fairly large scale problems.     

A numerical algorithm for flame propagation in premixed gases

The propagation speed of a premixed laminar flame or a weak deflagration wave is not uniquely determined in the hyperbolic theory of reactive gas flow. In this paper, we take a hyperbolic system of conservation laws as a governing system of equations for reacting gases and propose an algorithm to determine a wave propagation speed uniquely. The wave speed and states around a flame are computed through solving a Riemann problem near a flame in the phase space. The Riemann problem can be solved by combining the information from the internal wave structure, which is ignored in the hyperbolic approximation, and characteristic information. Therefore, the wave speed comes to depend on the internal variables such as viscosity and diffusion. This method can be used to track a premixed laminar flame when combined with any front tracking method. Some computational results are also presented.     

Two noniterative algorithms for computing posteriors

In this paper, we first propose a noniterative sampling method to obtain an i.i.d. sample approximately from posteriors by combining the inverse Bayes formula, sampling/importance resampling and posterior mode estimates. We then propose a new exact algorithm to compute posteriors by improving the PMDA-Exact using the sampling-wise IBF. If the posterior mode is available from the EM algorithm, then these two algorithms compute posteriors well and eliminate the convergence problem of Markov Chain Monte Carlo methods. We show good performances of our methods by some examples.     

Domain decomposition methods for hyperbolic problems

In this paper a method is developed for solving hyperbolic initial boundary value problems in one space dimension using domain decomposition, which can be extended to problems in several space dimensions. We minimize a functional which is the sum of squares of the L ² norms of the residuals and a term which is the sum of the squares of the L ² norms of the jumps in the function across interdomain boundaries. To make the problem well posed the interdomain boundaries are made to move back and forth at alternate time steps with sufficiently high speed. We construct parallel preconditioners and obtain error estimates for the method. The Schwarz waveform relaxation method is often employed to solve hyperbolic problems using domain decomposition but this technique faces difficulties if the system becomes characteristic at the inter-element boundaries. By making the inter-element boundaries move faster than the fastest wave speed associated with the hyperbolic system we are able to overcome this problem.