On the solution of discrete bottleneck problems

We consider a class of discrete bottleneck problems which includes bottleneck integral flow problems. It is demonstrated that a problem in this class, with k discrete variables, can be optimized by solving atmost k problems with real valued variables.     

Polynomial time approximation schemes and parameterized complexity

In this paper, we study the relationship between the approximability and the parameterized complexity of NP optimization problems. We introduce a notion of polynomial fixed-parameter tractability and prove that, under a very general constraint, an NP optimization problem has a fully polynomial time approximation scheme if and only if the problem is polynomial fixed-parameter tractable. By enforcing a constraint of planarity on the W-hierarchy studied in parameterized complexity theory, we obtain a class of NP optimization problems, the planar W-hierarchy, and prove that all problems in this class have efficient polynomial time approximation schemes (EPTAS). The planar W-hierarchy seems to contain most of the known EPTAS problems, and is significantly different from the class introduced by Khanna and Motwani in their efforts in characterizing optimization problems with polynomial time approximation schemes.     

What Is the Complexity of Solution-Restricted Operator Equations?

We study the worst case complexity of operator equations Lu = f where L: G → X is a bounded linear injection of normed linear spaces. Past work on the complexity of such problems has generally required the class F of problem elements f to be the unit ball of X. However, there are many problems for which this choice of F yields unsatisfactory results. Mixed elliptic—hyperbolic problems are one example. the difficulty being that our technical tools are nor strong enough to give good complexity bounds. Ill-posed problems are another example. because we know that the complexity of computing finite-error approximations is infinite if F is a ball in X. In this paper, we pursue another idea. Rather than directly restrict the class F of problem elements f, we will consider problems that are solution-restricted: i.e., we restrict the class U of solution elements u. In particular, we assume that U is the unit hall of a normed linear space W that is densely, continuously embedded in G. The main idea is that our problem can now be reduced to the standard approximation problem of approximating the embedding of W into G.This allows us to characterize optimal information and algorithms for our problem..We use this idea to study three problems: the Tricomi problem (a mixed hyperbolic— elliptic problem arising in the study of transonic flow), the inverse finite Laplace transform (an ill-posed problem arising. e.g.. in geomathematics), and the backwards heat equation. We determine the problem complexity and derive nearly optimal algorithms for each of these problems.     

The best approximation to a class of functions of several variables by another class and related extremum problems

We study the relationship between several extremum problems for unbounded linear operators of convolution type in the spaces $L_\gamma = L_\gamma (\mathbb{R}^m )$ , m ≥ 1, 1 ≤ γ ≤ ∞. For the problem of calculating the modulus of continuity of the convolution operatorA on the function classQ defined by a similar operator and for the Stechkin problem on the best approximation of the operatorA on the classQ by bounded linear operators, we construct dual problems in dual spaces, which are the problems on, respectively, the best and the worst approximation to a class of functions by another class.     

Coxeter-biCatalan combinatorics

We pose counting problems related to the various settings for Coxeter-Catalan combinatorics (noncrossing, nonnesting, clusters, Cambrian). Each problem is to count “twin” pairs of objects from a corresponding problem in Coxeter-Catalan combinatorics. We show that the problems all have the same answer, and, for a given finite Coxeter group W, we call the common solution to these problems the W-biCatalan number. We compute the W-biCatalan number for all W and take the first steps in the study of Coxeter-biCatalan combinatorics.     

A new heuristic approach for the P-median problem

The Euclidean p-median problem is concerned with the decision of the locations for public service centres. Existing methods for the planar Euclidean p-median problems are capable of efficiently solving problems of relatively small scale. This paper proposes two new heuristic algorithms aiming at problems of large scale. Firstly, to reflect the different degrees of proximity to optimality, a new kind of local optimum called level-m optimum is defined. For a level-m optimum of a p-median problem, where m<p, each of its subsets containing m of the p partitions is a global optimum of the corresponding m-median subproblem. Starting from a conventional local optimum, the first new algorithm efficiently improves it to a level-2 optimum by applying an existing exact algorithm for solving the 2-median problem. The second new algorithm further improves it to a level-3 optimum by applying a new exact algorithm for solving the 3-median problem. Comparison based on experimental results confirms that the proposed algorithms are superior to the existing heuristics, especially in terms of solution quality.     

Revisiting <Emphasis Type="Italic">k</Emphasis>-sum optimization

In this paper, we address continuous, integer and combinatorial k-sum optimization problems. We analyze different formulations of this problem that allow to solve it through the minimization of a relatively small number of minisum optimization problems. This approach provides a general tool for solving a variety of k-sum optimization problems and at the same time, improves the complexity bounds of many ad-hoc algorithms previously reported in the literature for particular versions of this problem. Moreover, the results developed for k-sum optimization have been extended to the more general case of the convex ordered median problem, improving upon existing solution approaches.     

A generalized Stieltjes criterion for the complete indeterminacy of interpolation problems

The main result of this paper is a generalized Stieltjes criterion for the complete indeterminacy of interpolation problems in the Stieltjes class. This criterion is a generalization to limit interpolation problems of the classical Stieltjes criterion for the indeterminacy of moment problems. It is stated in terms of the Stieltjes parameters M _j and N _j . We obtain explicit formulas for the Stieltjes parameters. General constructions are illustrated by examples of the Stieltjes moment problem and the Nevanlinna-Pick problem in the Stieltjes class.     

<Emphasis Type="Italic">G</Emphasis>-Convergence of systems of generalized Beltrami equations

Many problems of mathematical physics lead to problems of G-convergence of differential operators and, in particular, to the problem of homogenization of partial differential operators. Similar problems arise in elasticity theory, electrodynamics, and other fields of physics and mechanics. In this paper, we consider the problem of G-convergence of systems of Beltrami operators. We prove that the class of such systems is G-compact and study the properties of G-convergence.     

Medi-centre Location Problems

In this paper we consider two medi-centre location problems. One is the m-medi-centre problem in which we add to the m-median problem uniform distance constraints. The other problem is the uncapacitated medi-centre facility location problem where we include the fixed costs of establishing the facilities and thus the number of facilities is also a decision variable. For the two problems we present algorithms and discuss computational experience.     

On the construction of ε-optimal strategies in partially observed MDPs

The purpose of the paper is to give a survey of methods, partly derived by the author in joint work with other researchers, concerning the problem of constructingε-optimal strategies for partially observable MDPs. The methods basically consist in transforming the problem into one of approximation: Starting from the original problem a sequence of approximating problems is constructed such that:

1. For each approximating problem an optimal strategy can actually be computed.
2. Givenε>0, there exists an approximating problem such that the optimal strategy for the latter isε-optimal for the original problem.

     

Degree bounded matroids and submodular flows

We consider two related problems, the Minimum Bounded Degree Matroid Basis problem and the Minimum Bounded Degree Submodular Flow problem. The first problem is a generalization of the Minimum Bounded Degree Spanning Tree problem: We are given a matroid and a hypergraph on its ground set with lower and upper bounds f(e)≤g(e) for each hyperedge e. The task is to find a minimum cost basis which contains at least f(e) and at most g(e) elements from each hyperedge e. In the second problem we have a submodular flow problem, a lower bound f(v) and an upper bound g(v) for each node v, and the task is to find a minimum cost 0–1 submodular flow with the additional constraint that the sum of the incoming and outgoing flow at each node v is between f(v) and g(v). Both of these problems are NP-hard (even the feasibility problems are NP-complete), but we show that they can be approximated in the following sense. Let opt be the value of the optimal solution. For the first problem we give an algorithm that finds a basis B of cost no more than opt such that f(e)?2Δ+1≤|B∩e|≤g(e)+2Δ?1 for every hyperedge e, where Δ is the maximum degree of the hypergraph. If there are only upper bounds (or only lower bounds), then the violation can be decreased to Δ?1. For the second problem we can find a 0–1 submodular flow of cost at most opt where the sum of the incoming and outgoing flow at each node v is between f(v)?1 and g(v)+1. These results can be applied to obtain approximation algorithms for several combinatorial optimization problems with degree constraints, including the Minimum Crossing Spanning Tree problem, the Minimum Bounded Degree Spanning Tree Union problem, the Minimum Bounded Degree Directed Cut Cover problem, and the Minimum Bounded Degree Graph Orientation problem.     

Tocher's Principle of Modelling: Practical Significance and Mathematical Implications

This paper describes an important principle of modelling put forward by the late K. D. Tocher, namely that a clear distinction should be made between a system modelled and problems about the system. An example illustrates the many different practical problems one may be led to solve about a given economic system, e.g. an industrial firm. The example also shows that problems often result from the solutions to other problems, and thus cannot all be simultaneously anticipated. This suggests the need for a modelling system which, given a model of a system, may be used to solve any problem about the system.The overall problem can be described as that of solving an underdetermined system of equations. The precise meaning of the problem is defined for the case of sparse systems. Finally, the main features of a computer program based on Tocher's philosopy are outlined.     

Heuristic Solution Methods for Two Location Problems with Unreliable Facilities

In this paper, the p-median and p-centre problems are generalized by considering the possibility that one or more of the facilities may become inactive. The unreliable p-median problem is defined by introducing the probability that a facility becomes inactive. The (p, q)-centre problem is defined when p facilities need to be located but up to q of them may become unavailable at the same time. An heuristic procedure is presented for each problem. A rigorous procedure is discussed for the (p, q)-centre problem. Computational results are presented.     

Algorithms for Large-scale Travelling Salesman Problems

The paper describes a new algorithm to produce r-optimal tours for the travelling salesman problem. This algorithm is faster than the original r-optimal method, and computation times increase much less rapidly with problem size. The new algorithm makes it possible to solve large-scale travelling salesman problems and examples are given for problems varying in size from 100 to 500 cities. The paper also discusses r-optimality in terms of multistage 2-optimality.     

On the complexity of inverse convex ordered 1-median problem on the plane and on tree networks

An ordered median function is used in location theory to generalize a class of problems, including median and center problems. In this paper we consider the complexity of inverse ordered 1-median problems on the plane and on trees, where the multipliers are sorted nondecreasingly. Based on the convexity of the objective function, we prove that the problems with variable weights or variable coordinates on the line are NP-hard. Then we can directly get the NP-hardness result for the corresponding problem on the plane. We finally develop a cubic time algorithm that solves the inverse convex ordered 1-median problem on trees with relaxation on modification bounds.     

Duality for a class of nondifferentiable mathematical programming problems

Two dual problems are proposed for the minimax problem: minimize max_y?Yφ(x, y), subject to g(x) ? 0. A duality theorem is established for each dual problem. It is revealed that these problems are intimately related to a class of nondifferentiable programming problems.     

Operations policy for a supply chain system with fixed-interval delivery and linear demand

This research addresses a production-supply problem for a supply-chain system with fixed-interval delivery. A strategy that determines the optimal batch sizes, cycle times, numbers of orders of raw materials, and production start times is prescribed to minimize the total costs for a given finite planning horizon. The external demands are time-dependent following a life-cycle pattern and the shipment quantities follow the demand pattern. The shipment quantities to buyers follow various phases of the demand pattern in the planning horizon where demand is represented by piecewise linear model. The problem is formulated as an integer, non-linear programming problem. The model also incorporates the constraint of inventory capacity. The problem is represented using the network model where an optimal characteristic has been analysed. To obtain an optimal solution with N shipments in a planning horizon, an algorithm is proposed that runs with the complexity of Θ(N²) for problems with a single-phase demand and O(N³) for problems with multi-phase demand.     

Scale-integration and scale-disintegration in nonlinear homogenization

This work is devoted to scale transformations of stationary nonlinear problems. A class of coarse-scale problems is first derived by integrating a family of two-scale minimization problems (scale-integration), in presence of appropriate orthogonality conditions. The equivalence between the two formulations is established by showing that conversely any solution of the coarse-scale problem can be represented as the fine-scale average of a solution of the two-scale problem (scale-disintegration). This procedure may be applied to the homogenization of several quasilinear problems, and is related to De Giorgi’s notion of Γ-convergence. As an example the homogenization of a simple nonlinear model of magnetostatics is illustrated: a two-scale minimization problem is first derived via Nguetseng’s notion of two-scale convergence, and afterwards the equivalence with a coarse-scale problem is proved.