Coloring Geometric Range Spaces

We study several coloring problems for geometric range-spaces. In addition to their theoretical interest, some of these problems arise in sensor networks. Given a set of points in ?² or ?³, we want to color them so that every region of a certain family (e.g., every disk containing at least a certain number of points) contains points of many (say, k) different colors. In this paper, we think of the number of colors and the number of points as functions of k. Obviously, for a fixed k using k colors, it is not always possible to ensure that every region containing k points has all colors present. Thus, we introduce two types of relaxations: either we allow the number of colors used to increase to c(k), or we require that the number of points in each region increases to p(k).Symmetrically, given a finite set of regions in ?² or ?³, we want to color them so that every point covered by a sufficiently large number of regions is contained in regions of k different colors. This requires the number of covering regions or the number of allowed colors to be greater than k.The goal of this paper is to bound these two functions for several types of region families, such as halfplanes, halfspaces, disks, and pseudo-disks. This is related to previous results of Pach, Tardos, and Tóth on decompositions of coverings.     

Extending the process of comparison in soft systems methodology

Soft systems methodology (SSM) is a leading interpretive approach to real-world problem management and the idea of comparison is one of its core concepts. However, it is argued in this paper that the concept of comparison could be usefully enriched and made easier to operationalise since it has received very little attention in the research literature. The paper explores comparison as a problem area and proposes a framework consisting of expectation, desirability and importance as a basis for extending and clarifying the notion of comparison.     

Parametric Integer Programming Analysis: A Contraction Approach

An algorithm is presented for solving families of integer linear programming problems in which the problems are "related" by having identical objective coefficients and constraint matrix coefficients. The righthand-side constants have the form b + θd where b and d are conformable vectors and θ varies from zero to one.The approach consists primarily of solving the most relaxed problem (θ = 1) using cutting planes and then contracting the region of feasible integer solutions in such a manner that the current optimal integer solution is eliminated.The algorithm was applied to 1800 integer linear programming problems with reasonable success. Integer programming problems which have proved to be unsolvable using cutting planes have been solved by expanding the region of feasible integer solutions (θ = 1) and then contracting to the original region.     

Fast separation for the three-index assignment problem

A critical step in a cutting plane algorithm is separation, i.e., establishing whether a given vector x violates an inequality belonging to a specific class. It is customary to express the time complexity of a separation algorithm in the number of variables n. Here, we argue that a separation algorithm may instead process the vector containing the positive components of x,  denoted as supp(x),  which offers a more compact representation, especially if x is sparse; we also propose to express the time complexity in terms of |supp(x)|. Although several well-known separation algorithms exploit the sparsity of x,  we revisit this idea in order to take sparsity explicitly into account in the time-complexity of separation and also design faster algorithms. We apply this approach to two classes of facet-defining inequalities for the three-index assignment problem, and obtain separation algorithms whose time complexity is linear in |supp(x)| instead of n. We indicate that this can be generalized to the axial k-index assignment problem and we show empirically how the separation algorithms exploiting sparsity improve on existing ones by running them on the largest instances reported in the literature.     

Local and global Carleman estimates for parabolic operators with coefficients with jumps at interfaces

In (0,T)×Ω, Ω open subset of ? ⁿ , n≥2, we consider a parabolic operator P=? _t ?? _x δ(t,x)? _x , where the (scalar) coefficient δ(t,x) is piecewise smooth in space yet discontinuous across a smooth interface S. We prove a global in time, local in space Carleman estimate for P in the neighborhood of any point of the interface. The “observation” region can be chosen independently of the sign of the jump of the coefficient δ at the considered point. The derivation of this estimate relies on the separation of the problem into three microlocal regions related to high and low tangential frequencies at the interface. In the high-frequency regime we use Calderón projectors. In the low-frequency regime we follow a more classical approach. Because of the parabolic nature of the problem we need to introduce Weyl-Hörmander anisotropic metrics, symbol classes and pseudo-differential operators. Each frequency regime and the associated technique require a different calculus. A global in time and space Carleman estimate on (0,T)×M, M a manifold, is also derived from the local result.     

The optimal solution set of the interval linear programming problems

Several methods exist for solving the interval linear programming (ILP) problem. In most of these methods, we can only obtain the optimal value of the objective function of the ILP problem. In this paper we determine the optimal solution set of the ILP as the intersection of some regions, by the best and the worst case (BWC) methods, when the feasible solution components of the best problem are positive. First, we convert the ILP problem to the convex combination problem by coefficients 0 ≤ λ _j , μ _ij , μ _i  ≤ 1, for i = 1, 2, . . . , m and j = 1, 2, . . . , n. If for each i, j, μ _ij  = μ _i  = λ _j  = 0, then the best problem has been obtained (in case of minimization problem). We move from the best problem towards the worst problem by tiny variations of λ _j , μ _ij and μ _i from 0 to 1. Then we solve each of the obtained problems. All of the optimal solutions form a region that we call the optimal solution set of the ILP. Our aim is to determine this optimal solution set by the best and the worst problem constraints. We show that some theorems to validity of this optimal solution set.     

Mixed problem for the wave equation with integrable potential in the case of two-point boundary conditions of distinct orders

We study a mixed problem for the wave equation with integrable potential and with two-point boundary conditions of distinct orders for the case in which the corresponding spectral problem may have multiple spectrum. Based on the resolvent approach in the Fourier method and the Krylov convergence acceleration trick for Fourier series, we obtain a classical solution u(x, t) of this problem under minimal constraints on the initial condition u(x, 0) = ?(x). We use the Carleson–Hunt theorem to prove the convergence almost everywhere of the formal solution series in the limit case of ?(x) ∈ L _p[0, 1], p > 1, and show that the formal solution is a generalized solution of the problem.     

On approximation of dominating tree in wireless sensor networks

We study the following problem: Given a weighted graph G = (V, E, w) with \({w: E \rightarrow \mathbb{Z}^+}\) , the dominating tree (DT) problem asks us to find a minimum total edge weight tree T such that for every \({v \in V}\) , v is either in T or adjacent to a vertex in T. To the best of our knowledge, this problem has not been addressed in the literature. Solving the DT problem can yield a routing backbone for broadcast protocols since (1) each node does not have to construct their own broadcast tree, (2) utilize the virtual backbone to reduce the message overhead, and (3) the weight of backbone representing the energy consumption is minimized. We prove the hardness of this problem, including the inapproximability result and present an approximation algorithm together with an efficient heuristic. Finally, we verify the effectiveness of our proposal through simulation.     

Improved difference scheme of the solution decomposition method for a singularly perturbed reaction-diffusion equation

A Dirichlet problem is considered for a singularly perturbed ordinary differential reaction-diffusion equation. For this problem, a new approach is developed in order to construct difference schemes that converge uniformly with respect to the perturbation parameter ?, ? ∈ (0, 1]. The approach is based on the decomposition of a discrete solution into regular and singular components, which are solutions of discrete subproblems on uniform grids. Using the asymptotic construction technique, a difference scheme of the solution decomposition method is constructed that converges ?-uniformly in the maximum norm at the rate O (N ^?2 ln² N), where N + 1 is the number of nodes in the grid used; for fixed values of the parameter ?, the scheme converges at the rate O(N ^?2). Using the Richardson technique, an improved scheme of the solution decomposition method is constructed, which converges ?-uniformly in the maximum norm at the rate O(N ^?4 ln⁴ N).     

A Note on Directed Genera of Some Tournaments

An embedding of a digraph in an orientable surface is an embedding as the underlying graph and arcs in each region force a directed cycle. The directed genus is the minimum genus of surfaces in which the digraph can be directed embedded. Bonnington, Conder, Morton and McKenna [J. Combin. Theory Ser. B, 85(2002) 1-20] gave the problem that which tournaments on n vertices have the directed genus ?(n?3)(n?4)/12 ?, the genus of K_n. In this paper, we use the current graph method to show that there exists a tournament, which has the directed genus ?(n?3)(n?4)/12 ?, on n vertices if and only if n ≡ 3 or 7 (mod 12).     

Analytic continuation formulas and Jacobi-type relations for Lauricella function

An approach for constructing a complete system of formulas for the analytic continuation of the Lauricella generalized hypergeometric function F_D^(N) with any N beyond the boundary of the unit polydisk is proposed. The approach is exposed in detail for the continuation of the function under consideration in neighborhoods of points whose all N components equal 1 or ∞. For the Lauricella function, differential relations being analogues of Jacobi’s formula for the Gaussian hypergeometric function are also presented. The results can be applied to solve the crowding problem for the Schwarz–Christoffel integral and to the theory of the Riemann–Hilbert problem.     

Asymptotics of the Velocity Potential of an Ideal Fluid Flowing around a Thin Body

We consider the Neumann problem outside a small neighborhood of a planar disk in the three-dimensional space. The surface of this neighborhood is assumed to be smooth, and its thickness is characterized by a small parameter ε. A uniform asymptotic expansion of the solution of this problem with respect to ε is constructed by the matching method. Since the problem turned out to be bisingular, an additional inner asymptotic expansion in the so-called stretched variables is constructed near the edge of the disk. A physical interpretation of the solution of this boundary value problem is the velocity potential of a laminar flow of an ideal fluid around a thin body, which is the neighborhood of the disk. It is assumed that this flow has unit velocity at a large distance from the disk, which is equivalent to the following condition for the potential: u(x₁, x₂, x₃, ε) = x₃+O(r^?2) as r → ∞, where r is the distance to the origin. The boundary condition of this problem is the impermeability of the surface of the body: ?u/?n = 0 at the boundary. After subtracting x₃ from the solution u(x₁, x₂, x₃, ε), we get a boundary value problem for the potential ?(x₁, x₂, x₃, ε) of the perturbed motion. Since the integral of the function ??/?n over the surface of the body is zero, we have ?(x₁, x₂, x₃, ε) = O(r^?2) as r → ∞. Hence, all the coefficients of the outer asymptotic expansion with respect to ε have the same behavior at infinity. However, these coefficients have growing singularities at the approach to the edge of the disk, which implies the bisingularity of the problem.     

Inverse problem with nonlocal observation of finding the coefficient multiplying <Emphasis Type="Italic">u</Emphasis> <Subscript> <Emphasis Type="Italic">t</Emphasis> </Subscript> in the parabolic equation

We study the inverse problem of the reconstruction of the coefficient ?(x, t) = ?⁰(x, t) + r(x) multiplying u_t in a nonstationary parabolic equation. Here ?⁰(x, t) ≥ ?⁰ > 0 is a given function, and r(x) ≥ 0 is an unknown function of the class L_∞(Ω). In addition to the initial and boundary conditions (the data of the direct problem), we pose the problem of nonlocal observation in the form ∫₀^Tu(x, t) dμ(t) = χ(x) with a known measure dμ(t) and a function χ(x). We separately consider the case dμ(t) = ω(t)dt of integral observation with a smooth function ω(t). We obtain sufficient conditions for the existence and uniqueness of the solution of the inverse problem, which have the form of ready-to-verify inequalities. We suggest an iterative procedure for finding the solution and prove its convergence. Examples of particular inverse problems for which the assumptions of our theorems hold are presented.     

On DP-coloring of graphs and multigraphs

While solving a question on the list coloring of planar graphs, Dvo?ák and Postle introduced the new notion of DP-coloring (they called it correspondence coloring). A DP-coloring of a graph G reduces the problem of finding a coloring of G from a given list L to the problem of finding a “large” independent set in the auxiliary graph H(G,L) with vertex set {(v, c): v ∈ V (G) and c ∈ L(v)}. It is similar to the old reduction by Plesnevi? and Vizing of the k-coloring problem to the problem of finding an independent set of size |V(G)| in the Cartesian product G□K _k, but DP-coloring seems more promising and useful than the Plesnevi?–Vizing reduction. Some properties of the DP-chromatic number χ _DP (G) resemble the properties of the list chromatic number χ _l (G) but some differ quite a lot. It is always the case that χ _DP (G) ≥ χ _l (G). The goal of this note is to introduce DP-colorings for multigraphs and to prove for them an analog of the result of Borodin and Erd?s–Rubin–Taylor characterizing the multigraphs that do not admit DP-colorings from some DP-degree-lists. This characterization yields an analog of Gallai’s Theorem on the minimum number of edges in n-vertex graphs critical with respect to DP-coloring.     

Tool replacement policy for one-sided processes with low fraction defective

In most manufacturing industries, tool replacement policy is essential for minimizing the fraction defective and the manufacturing cost. Tool wear is caused by the action of sliding chips in the shear zone, and the friction generated between the tool flank and workpiece. This wear, apparently, is a dominant and irremovable component of variability in many machining processes, which is a systematic assignable cause. As the tool wear occurs in the machining processes, the fraction of defectives would gradually become significant. When the fraction defective reaches a certain level, the tool must be replaced. Therefore, detecting suitable time for tool replacement operation becomes essential. In this paper, we present an analytical approach for unilateral processes based on the one-sided process capability index C _PU (or C _PL ) to find the appropriate time for tool replacement. Accurate process capability must be calculated, particularly, when the data contains assignable cause variation. By calculating the index C _PU (or C _PL ) in a dynamical environment, we propose estimators of C _PU (or C _PL ) and obtain exact form of the sampling distribution in the presence of systematic assignable cause. The proposed procedure is then applied to a real manufacturing process involving tool wear problem, to demonstrate the applicability of the proposed approach.     

The connected <Emphasis Type="Italic">p</Emphasis>-median problem on block graphs

In this paper, we study a variant of the p-median problem on block graphs G in which the p-median is asked to be connected, and this problem is called the connected p-median problem. We first show that the connected p-median problem is NP-hard on block graphs with multiple edge weights. Then, we propose an O(n)-time algorithm for solving the problem on unit-edge-weighted block graphs, where n is the number of vertices in G.     

On the solvability of the first nonlocal boundary value problem for an elliptic equation

We consider problems of the existence, uniqueness, and sign-definiteness of the classical solutions of the problem

$(Lu)(x) = f(x)(x \in D),u(x) - \beta (x)u(\sigma x) = \psi (x)(x \in S),$

where L is a linear second-order operator elliptic in the closure of a domain D ? R ⁿ and σ is a single-valued continuous mapping of S ≡ ?D into \(\bar D\).

We show that, under natural assumptions on the smoothness of β, σ, and the coefficients of L, this problem is Fredholm provided that either σ has no attractors on S or σ generates an attractor Θ on S and the spectral radius of the operator A defined on η(x) ∈ C(Θ) by the formula (Aη)(x) = |β(x)|η(σx) is less than unity.We obtain semieffective (in terms of a test function) conditions for the unique solvability of the problem.     

Strict <Emphasis Type="Italic">K</Emphasis>-monotonicity and <Emphasis Type="Italic">K</Emphasis>-order continuity in symmetric spaces

This paper is devoted to strict K-monotonicity and K-order continuity in symmetric spaces. Using a local approach to the geometric structure in a symmetric space E we investigate a connection between strict K-monotonicity and global convergence in measure of a sequence of the maximal functions. Next, we solve an essential problem whether an existence of a point of K-order continuity in a symmetric space E on \([0,\infty )\) implies that the embedding \(E\hookrightarrow {L^1}[0,\infty )\) does not hold. We present a complete characterization of an equivalent condition to K-order continuity in a symmetric space E using a notion of order continuity and the fundamental function of E. We also investigate a relationship between strict K-monotonicity and K-order continuity in symmetric spaces and show some examples of Lorentz spaces and Marcinkiewicz spaces having these properties or not. Finally, we discuss a local version of a crucial correspondence between order continuity and the Kadec–Klee property for global convergence in measure in a symmetric space E.     

A gradual rank increasing process for matrix completion

The matrix completion problem is easy to state: let A be a given data matrix in which some entries are unknown. Then, it is needed to assign “appropriate values” to these entries. A common way to solve this problem is to compute a rank-k matrix, B _k , that approximates A in a least squares sense. Then, the unknown entries in A attain the values of the corresponding entries in B _k . This raises the question of how to determine a suitable matrix rank. The method proposed in this paper attempts to answer this question. It builds a finite sequence of matrices \(B_{k}, k = 1, 2, \dots \), where B _k is a rank-k matrix that approximates A in a least squares sense. The computational effort is reduced by using B _k-1 as starting point in the computation of B _k . The ability of B _k to serve as substitute for A is measured with two objective functions: a “training” function that measures the distance between the known part of A and the corresponding part of B _k , and a “probe” function that assesses the quality of the imputed entries. Watching the changes in these functions as k increases enables us to find an optimal matrix rank. Numerical experiments illustrate the usefulness of the proposed approach.