Paintshop, odd cycles and necklace splitting

The following problem has been presented in [T. Epping, W. Hochstättler, P. Oertel, Complexity results on a paint shop problem, Discrete Applied Mathematics 136 (2004) 217-226] by Epping, Hochstättler and Oertel: cars have to be painted in two colors in a sequence where each car occurs twice; assign the two colors to the two occurrences of each car so as to minimize the number of color changes. More generally, the “paint shop scheduling problem” is defined with an arbitrary multiset of colors given for each car, where this multiset has the same size as the number of occurrences of the car; the mentioned article states two conjectures about the general problem and proves its NP-hardness. In a subsequent paper in [P. Bonsma, Th. Epping, W. Hochstättler, Complexity results for restricted instances of a paint shop problem for words, Discrete Applied Mathematics 154 (2006) 1335-1343], Bonsma, Epping and Hochstättler proved its APX-hardness and noticed the applicability of some classical results in special cases.We first identify the problem concerning two colors as a minimum odd circuit cover problem in particular graphs, exactly situating the problem. A resulting two-way reduction to a special minimum uncut problem leads to polynomial algorithms for subproblems, to observing APX-hardness through MAX CUT in 3-regular graphs, and to a solution with at most 3/4th of all possible remaining color changes (when all obliged color changes have been made).For the general problem concerning an arbitrary number of colors, we realize that the two aforementioned conjectures are corollaries of the celebrated “necklace splitting” theorem of Alon, Goldberg and West.     

Approximating a Zero of Sum of Two Monotone Operators Which Solves a Fixed Point Problem in Reflexive Banach Spaces

Abstract

The purpose of this paper is to introduce an iterative method for approximating a point in the set of zeros of the sum of two monotone mappings, which is also a solution of a fixed point problem for a Bregman strongly nonexpansive mapping in a real reflexive Banach space. With our iterative technique, we state and prove a strong convergence theorem for approximating an element in the intersection of the set of solutions of a variational inclusion problem for sum of two monotone mappings and the set of solutions of a fixed point problem for Bregman strongly nonexpansive mapping. We give applications of our result to convex minimization problem, convex feasibility problem, variational inequality problem, and equilibrium problem. Our result complements and extends some recent results in literature.     

Multiple pickup and delivery traveling salesman problem with last-in-first-out loading and distance constraints

We extend the traveling salesman problem with pickup and delivery and LIFO loading (TSPPDL) by considering two additional factors, namely the use of multiple vehicles and a limitation on the total distance that a vehicle can travel; both of these factors occur commonly in practice. We call the resultant problem the multiple pickup and delivery traveling salesman problem with LIFO loading and distance constraints (MTSPPD-LD). This paper presents a thorough preliminary investigation of the MTSPPD-LD. We propose six new neighborhood operators for the problem that can be used in search heuristics or meta-heuristics. We also devise a two-stage approach for solving the problem, where the first stage focuses on minimizing the number of vehicles required and the second stage minimizes the total travel distance. We consider two possible approaches for the first stage (simulated annealing and ejection pool) and two for the second stage (variable neighborhood search and probabilistic tabu search). Our computational results serve as benchmarks for future researchers on the problem.     

A Note on the Stability of the Integral-Differential Equation of the Hyperbolic Type in a Hilbert Space

In this paper, the initial-value problem for integral-differential equation of the hyperbolic type in a Hilbert space H is considered. The unique solvability of this problem is established. The stability estimates for the solution of this problem are obtained. The difference scheme approximately solving this problem is presented. The stability estimates for the solution of this difference scheme are obtained. In applications, the stability estimates for the solutions of the nonlocal boundary problem for one-dimensional integral-differential equation of the hyperbolic type with two dependent limits and of the local boundary problem for multidimensional integral-differential equation of the hyperbolic type with two dependent limits are obtained. The difference schemes for solving these two problems are presented. The stability estimates for the solutions of these difference schemes are obtained.     

The split common fixed point problem for generalized demimetric mappings in two Banach spaces

ABSTRACT

In this paper, we consider the split common fixed point problem for new demimetric mappings in two Banach spaces. Using the hybrid method, we prove a strong convergence theorem for finding a solution of the split common fixed point problem in two Banach spaces. Furthermore, using the shrinking projection method, we obtain another strong convergence theorem for finding a solution of the problem in two Banach spaces. Using these results, we obtain well-known and new strong convergence theorems in Hilbert spaces and Banach spaces.     

On the dynamic Markov-Dubins problem: From path planning in robotics and biolocomotion to computational anatomy

Andrei Andreyevich Markov proposed in 1889 the problem (solved by Dubins in 1957) of finding the twice continuously differentiable (arc length parameterized) curve with bounded curvature, of minimum length, connecting two unit vectors at two arbitrary points in the plane. In this note we consider the following variant, which we call the dynamic Markov-Dubins problem (dM-D): to find the time-optimal C ² trajectory connecting two velocity vectors having possibly different norms. The control is given by a force whose norm is bounded. The acceleration may have a tangential component, and corners are allowed, provided the velocity vanishes there. We show that for almost all the two vectors boundary value conditions, the optimization problem has a smooth solution. We suggest some research directions for the dM-D problem on Riemannian manifolds, in particular we would like to know what happens if the underlying geodesic problem is completely integrable. Path planning in robotics and aviation should be the usual applications, and we suggest a pursuit problem in biolocomotion. Finally, we suggest a somewhat unexpected application to “dynamic imaging science”. Short time processes (in medicine and biology, in environment sciences, geophysics, even social sciences?) can be thought as tangent vectors. The time needed to connect two processes via a dynamic Markov-Dubins problem provides a notion of distance. Statistical methods could then be employed for classification purposes using a training set.     

Solution of Special Linear Programming Problems with Additional Constraints

This paper gives a method of solution for linear programming problems whose constraints can be split into two sets, the first having a special structure, such as that of the transportation problem for example, while the second set is quite general. A problem with only the first set of constraints is referred to as a favoured problem, while a problem with both sets is called a complete problem.The proposed method is basically the simplex procedure specialized for a problem with a particular structure, and the feasibility and optimality criteria and the rules for basis change are the same as those used in the simplex procedure. However, the method takes advantage of the simple algorithms developed for the favoured problem and uses them to solve the complete problem in an efficient manner.Such problems could also be solved by the Decomposition Principle and, vice versa, Decomposition problems can be solved by the present method. The two methods are, however, essentially different in their approach to the problem.     

A Subdivision Approach to Maximum Parsimony

Determining an optimal phylogenetic tree using maximum parsimony, also referred to as the Steiner tree problem in phylogenetics, is NP hard. Here we provide a new formulation for this problem which leads to an analytical and linear time solution when the dimensionality (sequence length, or number of characters) is at most two. This new formulation of the problem provides a direct link between the maximum parsimony problem and the maximum compatibility problem via the intersection graph. The solution for the “two character case” has numerous practical applications in phylogenetics, some of which are discussed. Received January 16, 2006     

LOCAL CLASSICAL SOLUTION OF FREE BOUNDARY PROBLEM FOR A COUPLED SYSTEM

This paper considers a two-phase free boundary problem for coupled system including one parabolic equation and two elliptic equations. The problem comes from the discussion of a growth model of self-lnaintaining protocell in multidimensional case. The local classical solution of the problem with free boundary F : y = g(x,t) between two domains is being seeked. The local existence and uniqueness of the problem will be proved in multidimensional case.     

Generalized intersection bodies

We study the structures of two types of generalizations of intersection-bodies and the problem of whether they are in fact equivalent. Intersection-bodies were introduced by Lutwak and played a key role in the solution of the Busemann–Petty problem. A natural geometric generalization of this problem considered by Zhang, led him to introduce one type of generalized intersection-bodies. A second type was introduced by Koldobsky, who studied a different analytic generalization of this problem. Koldobsky also studied the connection between these two types of bodies, and noted that an equivalence between these two notions would completely settle the unresolved cases in the generalized Busemann–Petty problem. We show that these classes share many identical structural properties, proving the same results using integral geometry techniques for Zhang's class and Fourier transform techniques for Koldobsky's class. Using a functional analytic approach, we give several surprising equivalent formulations for the equivalence problem, which reveal a deep connection to several fundamental problems in the integral geometry of the Grassmann manifold.     

On Gilmore-Gomory's open question for the bottleneck TSP

Consider the traveling salesman problem where the distance between two cities A and B is an integrable function of the y-coordinate of A and the x-coordinate of B. This problem finds important applications in operations management and combinatorial optimization. Gilmore and Gomory (Oper. Res. 12 (1964) 655) gave a polynomial time algorithm for this problem. In the bottleneck variant of this problem (BP), we seek a tour that minimizes the maximum distance between any two consecutive cities. For BP, Gilmore and Gomory state that they “do not yet know how to solve the problem for general integrable functions”. We show that BP is strongly NP-complete. Also, we use this reduction to provide a method for proving NP-completeness of other combinatorial problems.     

Local networks for computer communications: A. WEST and P. JANSON (Eds.) Proceedings of the IFIP Working Group 6.4, International Workshop on Local Networks,Zürich,Switzerland, August 27–29, 1980, North-Holland,Amsterdam, 1981, xiii + 470 pages,Dfl.125.00

In this paper we present two lower bounds for the p-median problem, the problem of locating p facilities (medians) on a network. These bounds are based on two separate lagrangean relaxations of a zero-one formulation of the problem with subgradient optimisation being used to maximise these bounds. Penalty tests based on these lower bounds and a heuristically determined upper bound to the problem are developed and shown to result in a large reduction in problem size. The incorporation of the lower bounds and the penalty tests into a tree search procedure is described and computational results are given for problems with an arbitrary number of medians and having up to 200 vertices. A comparison is also made between these algorithms and the dual-based algorithm of Erlenkotter.     

A Bellman function proof of the L 2 bump conjecture

We approach the problem of finding the sharp sufficient condition for boundedness of all two weight Calderón-Zygmund operators. We solve this problem in L ² by writing a formula for a Bellman function of the problem.     

The biobjective undirected two-commodity minimum cost flow problem

We address the two-commodity minimum cost flow problem considering two objectives. We show that the biobjective undirected two-commodity minimum cost flow problem can be split into two standard biobjective minimum cost flow problems using the change of variables approach. This technique allows us to develop a method that finds all the efficient extreme points in the objective space for the two-commodity problem solving two biobjective minimum cost flow problems. In other words, we generalize the Hu's theorem for the biobjective undirected two-commodity minimum cost flow problem. In addition, we develop a parametric network simplex method to solve the biobjective problem.     

Two‐grid methods for time‐harmonic Maxwell equations

In this paper, we develop several two‐grid methods for the Nédélec edge finite element approximation of the time‐harmonic Maxwell equations. We first present a two‐grid method that uses a coarse space to solve the original problem and then use a fine space to solve a corresponding symmetric positive definite problem. Then, we present two types of iterative two‐grid methods, one is to add the kernel of the curl ‐operator in the fine space to a coarse mesh space to solve the original problem and the other is to use an inner iterative method for dealing with the kernel of the curl ‐operator in the fine space and the coarse space, separately. We provide the error estimates for the first two methods and present numerical experiments to show the efficiency of our methods.Copyright © 2012 John Wiley & Sons, Ltd.     

An inverse source problem for a two dimensional time fractional diffusion equation with nonlocal boundary conditions

We consider the inverse source problem for a time fractional diffusion equation. The unknown source term is independent of the time variable, and the problem is considered in two dimensions. A biorthogonal system of functions consisting of two Riesz bases of the space L²[(0,1) × (0,1)], obtained from eigenfunctions and associated functions of the spectral problem and its adjoint problem, is used to represent the solution of the inverse problem. Using the properties of the biorthogonal system of functions, we show the existence and uniqueness of the solution of the inverse problem and its continuous dependence on the data. Copyright © 2012 John Wiley & Sons, Ltd.     

New formulations for the Kissing Number Problem

Determining the maximum number of D-dimensional spheres of radius r that can be adjacent to a central sphere of radius r is known as the Kissing Number Problem (KNP). The problem has been solved for two, three and very recently for four dimensions. We present two nonlinear (nonconvex) mathematical programming models for the solution of the KNP. We solve the problem by using two stochastic global optimization methods: a Multi Level Single Linkage algorithm and a Variable Neighbourhood Search. We obtain numerical results for two, three and four dimensions.     

A comparison of two methods for solving 0–1 integer programs using a general purpose simulated annealing algorithm

0–1 problems are often difficult to solve. Although special purpose algorithms (exact as well as heuristic) exist for solving particular problem classes or problem instances, there are few general purpose algorithms for solving practical-sized instances of 0–1 problems. This paper deals with a general purpose heuristic algorithm for 0–1 problems. In this paper, we compare two methods based on simulated annealing for solving general 0–1 integer programming problems. The two methods differe in the scheme used for neighbourhood transitions in the simulated annealing framework. We compare the performance of the two methods on the set partitioning problem.     

On two-coefficient identification in elliptic variational inequalities

Abstract

This paper is concerned with elliptic variational inequalities that depend on two parameters. First, we investigate the dependence of the solution of the forward problem on these parameters and prove a Lipschitz estimate. Then, we study the inverse problem of identification of these two parameters and formulate two optimization approaches to this parameter identification problem. We extend the output least-squares approach, provide an existence result and establish a convergence result for finite-dimensional approximation. Further, we investigate the modified output least-squares approach which is based on energy functionals. This latter approach can be related to vector approximation.     

Allocation strategies in hub networks

In this paper, we study allocation strategies and their effects on total routing costs in hub networks. Given a set of nodes with pairwise traffic demands, the p-hub median problem is the problem of choosing p nodes as hub locations and routing traffic through these hubs at minimum cost. This problem has two versions; in single allocation problems, each node can send and receive traffic through a single hub, whereas in multiple allocation problems, there is no such restriction and a node may send and receive its traffic through all p hubs. This results in high fixed costs and complicated networks. In this study, we introduce the r-allocation p-hub median problem, where each node can be connected to at most r hubs. This new problem generalizes the two versions of the p-hub median problem. We derive mixed-integer programming formulations for this problem and perform a computational study using well-known datasets. For these datasets, we conclude that single allocation solutions are considerably more expensive than multiple allocation solutions, but significant savings can be achieved by allowing nodes to be allocated to two or three hubs rather than one. We also present models for variations of this problem with service quality considerations, flow thresholds, and non-stop service.