Reconstructing edge-disjoint paths

For an undirected graph G=(V,E), the edge connectivity values between every pair of nodes of G can be succinctly recorded in a flow-equivalent tree that contains the edge connectivity value for a linear number of pairs of nodes. We generalize this result to show how we can efficiently recover a maximum set of disjoint paths between any pair of nodes of G by storing such sets for a linear number of pairs of nodes. At the heart of our result is an observation that combining two flow solutions of the same value, one between nodes s and r and the second between nodes r and t, into a feasible flow solution of value f between nodes s and t, is equivalent to solving a stable matching problem on a bipartite multigraph.Our observation, combined with an observation of Chazelle, leads to a data structure, which takes O(n^3.5) time to generate, that can construct the maximum number λ(u,v) of edge-disjoint paths between any pair (u,v) of nodes in time O(α(n,n)λ(u,v)n) time.     

A mean–variance optimization problem for discounted Markov decision processes

In this paper, we consider a mean–variance optimization problem for Markov decision processes (MDPs) over the set of (deterministic stationary) policies. Different from the usual formulation in MDPs, we aim to obtain the mean–variance optimal policy that minimizes the variance over a set of all policies with a given expected reward. For continuous-time MDPs with the discounted criterion and finite-state and action spaces, we prove that the mean–variance optimization problem can be transformed to an equivalent discounted optimization problem using the conditional expectation and Markov properties. Then, we show that a mean–variance optimal policy and the efficient frontier can be obtained by policy iteration methods with a finite number of iterations. We also address related issues such as a mutual fund theorem and illustrate our results with an example.     

An FPTAS for minimizing the product of two non-negative linear cost functions

We consider a quadratic programming (QP) problem (Π) of the form min x ^T C x subject to Ax ≥ b, x ≥ 0 where \({C\in {\mathbb R}^{n \times n}_+, {\rm rank}(C)=1}\) and \({A\in {\mathbb R}^{m \times n}, b\in {\mathbb R}^m}\) . We present an fully polynomial time approximation scheme (FPTAS) for this problem by reformulating the QP (Π) as a parameterized LP and “rounding” the optimal solution. Furthermore, our algorithm returns an extreme point solution of the polytope. Therefore, our results apply directly to 0–1 problems for which the convex hull of feasible integer solutions is known such as spanning tree, matchings and sub-modular flows. They also apply to problems for which the convex hull of the dominant of the feasible integer solutions is known such as s, t-shortest paths and s, t-min-cuts. For the above discrete problems, the quadratic program Π models the problem of obtaining an integer solution that minimizes the product of two linear non-negative cost functions.     

A general Trotter-Kato formula for a class of evolution operators

In this article we prove new results concerning the existence and various properties of an evolution system UA+B(t,s)_0?s?t?T generated by the sum −(A(t)+B(t)) of two linear, time-dependent and generally unbounded operators defined on time-dependent domains in a complex and separable Banach space B. In particular, writing L(B) for the algebra of all linear bounded operators on B, we can express UA+B(t,s)_0?s?t?T as the strong limit in L(B) of a product of the holomorphic contraction semigroups generated by −A(t) and −B(t), respectively, thereby proving a product formula of the Trotter-Kato type under very general conditions which allow the domain D(A(t)+B(t)) to evolve with time provided there exists a fixed set D⊂_?t∈[0,T]D(A(t)+B(t)) everywhere dense in B. We obtain a special case of our formula when B(t)=0, which, in effect, allows us to reconstruct UA(t,s)_0?s?t?T very simply in terms of the semigroup generated by −A(t). We then illustrate our results by considering various examples of nonautonomous parabolic initial-boundary value problems, including one related to the theory of time-dependent singular perturbations of self-adjoint operators. We finally mention what we think remains an open problem for the corresponding equations of Schrödinger type in quantum mechanics.     

On symmetry of nonnegative solutions of elliptic equations

We consider the Dirichlet problem for a class of fully nonlinear elliptic equations on a bounded domain Ω. We assume that Ω is symmetric about a hyperplane H and convex in the direction perpendicular to H. By a well-known result of Gidas, Ni and Nirenberg and its generalizations, all positive solutions are reflectionally symmetric about H and decreasing away from the hyperplane in the direction orthogonal to H. For nonnegative solutions, this result is not always true. We show that, nonetheless, the symmetry part of the result remains valid for nonnegative solutions: any nonnegative solution u is symmetric about H  . Moreover, we prove that if u?0$u?0$, then the nodal set of u divides the domain Ω into a finite number of reflectionally symmetric subdomains in which u has the usual Gidas–Ni–Nirenberg symmetry and monotonicity properties. We also show several examples of nonnegative solutions with a nonempty interior nodal set.     

On the Hermitian positive definite solutions of nonlinear matrix equation X + A∗XA = Q

Nonlinear matrix equation X^s + A∗X^−tA = Q, where A, Q are n × n complex matrices with Q Hermitian positive definite, has widely applied background. In this paper, we consider the Hermitian positive definite solutions of this matrix equation with two cases: s ? 1, 0 < t ? 1 and 0 < s ? 1, t ? 1. We derive necessary conditions and sufficient conditions for the existence of Hermitian positive definite solutions for the matrix equation and obtain some properties of the solutions. We also propose iterative methods for obtaining the extremal Hermitian positive definite solution of the matrix equation. Finally, we give some numerical examples to show the efficiency of the proposed iterative methods.     

Scheduling interfering job sets on parallel machines

We consider bicriteria scheduling on identical parallel machines in a nontraditional context: jobs belong to two disjoint sets, and each set has a different criterion to be minimized. The jobs are all available at time zero and have to be scheduled (non-preemptively) on m parallel machines. The goal is to generate the set of all non-dominated solutions, so the decision maker can evaluate the tradeoffs and choose the schedule to be implemented. We consider the case where, for one of the two sets, the criterion to be minimized is makespan while for the other the total completion time needs to be minimized. Given that the problem is NP-hard, we propose an iterative SPT–LPT–SPT heuristic and a bicriteria genetic algorithm for the problem. Both approaches are designed to exploit the problem structure and generate a set of non-dominated solutions. In the genetic algorithm we use a special encoding scheme and also a unique strategy – based on the properties of a non-dominated solution – to ensure that all parts of the non-dominated front are explored. The heuristic and the genetic algorithm are compared with a time-indexed integer programming formulation for small and large instances. Results indicate that the both the heuristic and the genetic algorithm provide high solution quality and are computationally efficient. The heuristics proposed also have the potential to be generalized for the problem of interfering job sets involving other bicriteria pairs.     

Induced disjoint paths problem in a planar digraph

As an extension of the disjoint paths problem, we introduce a new problem which we call the induced disjoint paths problem. In this problem we are given a graph G and a collection of vertex pairs {(s₁,t₁),…,(s_k,t_k)}. The objective is to find k paths P₁,…,P_k such that P_i is a path from s_i to t_i and P_i and P_j have neither common vertices nor adjacent vertices for any distinct i,j.The induced disjoint paths problem has several variants depending on whether k is a fixed constant or a part of the input, whether the graph is directed or undirected, and whether the graph is planar or not. We investigate the computational complexity of several variants of the induced disjoint paths problem. We show that the induced disjoint paths problem is (i) solvable in polynomial time when k is fixed and G is a directed (or undirected) planar graph, (ii) NP-hard when k=2 and G is an acyclic directed graph, (iii) NP-hard when k=2 and G is an undirected general graph.As an application of our first result, we show that we can find in polynomial time certain structures called a “hole” and a “theta” in a planar graph.     

Single item lot-sizing problem for a warm/cold process with immediate lost sales

We consider the dynamic lot-sizing problem with finite capacity and possible lost sales for a process that could be kept warm at a unit variable cost for the next period t + 1 only if more than a threshold value Q_t has been produced and would be cold, otherwise. Production with a cold process incurs a fixed positive setup cost, K_t and setup time, S_t, which may be positive. Setup costs and times for a warm process are negligible. We develop a dynamic programming formulation of the problem, establish theoretical results on the structure of the optimal production plan in the presence of zero and positive setup times with Wagner–Whitin-type cost structures. We also show that the solution to the dynamic lot-sizing problem with lost sales are generated from the full commitment production series improved via lost sales decisions in the presence of a warm/cold process.     

An Initial-Boundary Value Problem for the Korteweg–de Vries Equation with Dominant Surface Tension

We consider the initial-boundary value problem (IBVP) for the Korteweg–de Vries equation with zero boundary conditions at x=0 and arbitrary smooth decreasing initial data. We prove that the solution of this IBVP can be found by solving two linear inverse scattering problems (SPs) on two different spectral planes. The first SP is associated with the KdV equation. The second SP is self-conjugate and its scattering function is found in terms of entries of the scattering matrix s(k) for the first SP. Knowing the scattering function, we solve the second inverse SP for finding the potential self-conjugate matrix. Consequently, the unknown object entering coefficients in the system of evolution equations for s(k,t) is found. Then, the time-dependent scattering matrix s(k,t) is expressed in terms of s(k)=s(k,0) and of solutions of the self-conjugate SP. Knowing s(k,t), we find the solution of the IBVP in terms of the solution of the Gelfand–Levitan–Marchenko equation in the first inverse SP.     

Minmax regret location–allocation problem on a network under uncertainty

We consider a robust location–allocation problem with uncertainty in demand coefficients. Specifically, for each demand point, only an interval estimate of its demand is known and we consider the problem of determining where to locate a new service when a given fraction of these demand points must be served by the utility. The optimal solution of this problem is determined by the “minimax regret” location, i.e., the point that minimizes the worst-case loss in the objective function that may occur because a decision is made without knowing which state of nature will take place. For the case where the demand points are vertices of a network we show that the robust location–allocation problem can be solved in O(min{p, n − p}n³m) time, where n is the number of demand points, p (p < n) is the fixed number of demand points that must be served by the new service and m is the number of edges of the network.     

The set of periodic scalar differential equations with cubic nonlinearities

We study the structure induced by the number of periodic solutions on the set of differential equations x^′=f(t,x) where f∈C³(R²) is T-periodic in t, fx³(t,x)<0 for every (t,x)∈R², and f(t,x)→?∞ as x→∞, uniformly on t. We find that the set of differential equations with a singular periodic solution is a codimension-one submanifold, which divides the space into two components: equations with one periodic solution and equations with three periodic solutions. Moreover, the set of differential equations with exactly one periodic singular solution and no other periodic solution is a codimension-two submanifold.     

A nonlinear problem having a continuous locus of singular points and no multiple solutions

The boundary-value problem ?z″ = (z² ? t²)z′, ? > 0, z(? 1) = α, z(0) = β, t? [?1, 0], has been shown to have a solution, and moreover, depending on the choice of α and β, multiple solutions to it exist. We consider the more general equation f(z, t)z″ = (z^r ? t^s)z′ for a particular non-negative function f(z, t), and integrate the equation exactly. Depending on α and β, we find that either there are no solutions, or that only unique solutions exist. The conclusion is that the presence of a continuous locus of singular points, given by z^r = t^s, does not necessarily produce multiple solutions.     

Min–max and min–max regret versions of combinatorial optimization problems: A survey

Min–max and min–max regret criteria are commonly used to define robust solutions. After motivating the use of these criteria, we present general results. Then, we survey complexity results for the min–max and min–max regret versions of some combinatorial optimization problems: shortest path, spanning tree, assignment, min cut, min s–t cut, knapsack. Since most of these problems are NP-hard, we also investigate the approximability of these problems. Furthermore, we present algorithms to solve these problems to optimality.     

Existence and asymptotic decay for a Boussinesq-type model

In this article, we study the initial value problem associated with a five-parameter Boussinesq-type system. We prove local existence and uniqueness of the solution and that the supremum norm of the solution decays algebraically to zero as (1+t)^−1/3 when t approaches to infinity, provided the initial data are sufficiently small and regular. We further present a high-accurate spectral numerical method to approximate the solutions and validate the theoretical results.     

Second Order Nonlinear Evolution Inclusions Ⅰ： Existence and Relaxation Results

This is the first part of a work on second order nonlinear, nonmonotone evolution inclusions defined in the framework of an evolution triple of spaces and with a multivalued nonlinearity depending on both x（t） and x（t）. In this first part we prove existence and relaxation theorems. We consider the case of an usc, convex valued nonlinearity and we show that for this problem the solution set is nonempty and compact in C^1 （T, H）. Also we examine the Isc, nonconvex case and again we prove the existence of solutions. In addition we establish the existence of extremal solutions and by strengthening our hypotheses, we show that the extremal solutions are dense in C^1 （T, H） to the solutions of the original convex problem （strong relaxation）. An example of a nonlinear hyperbolic optimal control problem is also discussed.     

Nonlinear operator equations with a functional perturbation of the argument of neutral type

We construct small solutions x(t) → 0 as t → 0 of nonlinear operator equations F(x(t), x(α(t)),t) = 0 with a functional perturbation α(t) of the argument. By the Newton diagram method, we reduce the problem to quasilinear operator equations with a functional perturbation of the argument. We show that the solutions of such equations can have not only algebraic but also logarithmic branching points and contain free parameters. The number of free parameters and the form of the solution depend on the properties of the Jordan structure of the operator coefficients of the equation.     

Competitive subset selection with two agents

We address an optimization problem in which two agents, each with a set of weighted items, compete in order to maximize the total weight of their winning sets. The latter are built according to a sequential game consisting in a fixed number of rounds. In every round each agent submits one item for possible inclusion in its winning set. We study two natural rules to decide the winner of each round.For both rules we deal with the problem from different perspectives. From a centralized point of view, we investigate (i) the structure and the number of efficient (i.e. Pareto optimal) solutions, (ii) the complexity of finding such solutions, (iii) the best-worst ratio, i.e. the ratio between the efficient solution with largest and smallest total weight, and (iv) existence of Nash equilibria.Finally, we address the problem from a single agent perspective. We consider preventive or maximin strategies, optimizing the objective of the agent in the worst case, and best response strategies, where the items submitted by the other agent are known in advance either in each round (on-line) or for the whole game (off-line).     

Nonautonomous Ornstein-Uhlenbeck operators in weighted spaces of continuous functions

We consider the nonautonomous Ornstein-Uhlenbeck operator in some weighted spaces of continuous functions in $\mathbb{R}^{N}$ . We prove sharp uniform estimates for the spatial derivatives of the associated evolution operator P _s,t , which we use to prove optimal Schauder estimates for the solution to some nonhomogeneous parabolic Cauchy problems associated with the Ornstein-Uhlenbeck operator. We also prove that, for any t>s, the evolution operator P _s,t is compact in the previous weighted spaces.     

Equivalences and the complete hierarchy of intersection graphs of paths in a tree

An (h,s,t)-representation of a graph G consists of a collection of subtrees of a tree T, where each subtree corresponds to a vertex in G, such that (i) the maximum degree of T is at most h, (ii) every subtree has maximum degree at most s, (iii) there is an edge between two vertices in the graph G if and only if the corresponding subtrees have at least t vertices in common in T. The class of graphs that have an (h,s,t)-representation is denoted by [h,s,t]. It is well known that the class of chordal graphs corresponds to the class [3, 3, 1]. Moreover, it was proved by Jamison and Mulder that chordal graphs correspond to orthodox-[3, 3, 1] graphs defined below.In this paper, we investigate the class of [h,2,t] graphs, i.e., the intersection graphs of paths in a tree. The [h,2,1] graphs are also known as path graphs [F. Gavril, A recognition algorithm for the intersection graphs of paths in trees, Discrete Math. 23 (1978) 211-227] or VPT graphs [M.C. Golumbic, R.E. Jamison, Edge and vertex intersection of paths in a tree, Discrete Math. 55 (1985) 151-159], and [h,2,2] graphs are known as the EPT graphs. We consider variations of [h,2,t] by three main parameters: h, t and whether the graph has an orthodox representation. We give the complete hierarchy of relationships between the classes of weakly chordal, chordal, [h,2,t] and orthodox-[h,2,t] graphs for varied values of h and t.