A Polynomial-Time Algorithm for Finding Regular Simple Paths in Outerplanar Graphs

Let G be a labeled directed graph with arc labels drawn from alphabet Σ, R be a regular expression over Σ, and x and y be a pair of nodes from G. The regular simple path (RSP) problem is to determine whether there is a simple path p in G from x to y, such that the concatenation of arc labels along p satisfies R. Although RSP is known to be NP-hard in general, we show that it is solvable in polynomial time when G is outerplanar. The proof proceeds by presenting an algorithm which gives a polynomial-time reduction of RSP for outerplanar graphs to RSP for directed acyclic graphs, a problem which has been shown to be solvable in polynomial time.     

Sample-path conservation laws,with applications to scheduling queues and fluid systems

The achievable-region approach, based on strong conservation laws, has most often been applied to stochastic scheduling and other control problems in the context of performance measures that are steady-state expected quantities. For some problems, however, strong conservation laws hold for performance measures at every time point on every sample path. We exploit this property to study optimal control for certain scheduling problems on a sample-path basis. Examples include preemptive scheduling to minimize a weighted sum of work in the system in each class, nonpreemptive scheduling to minimize a weighted sum of the number of customers in each class (when all classes have the same service-time distribution), and scheduling the processing of fluid in a multiclass fluid system operating in a random environment. The last problem is solved by considering the related Skorohod problem and its minimal solution. This revised version was published online in June 2006 with corrections to the Cover Date.     

Integral representation of generalized grey Brownian motion

ABSTRACT

In this paper, we investigate the representation of a class of non-Gaussian processes, namely generalized grey Brownian motion, in terms of a weighted integral of a stochastic process which is a solution of a certain stochastic differential equation. In particular, the underlying process can be seen as a non-Gaussian extension of the Ornstein–Uhlenbeck process, hence generalizing the representation results of Muravlev, Russian Math. Surveys 66 (2), 2011 as well as Harms and Stefanovits, Stochastic Process. Appl. 129, 2019 to the non-Gaussian case.     

Regularity and decomposition of two-parameter supermartingales

The well-known Doob-Meyer decomposition of a supermartingale as the difference of a martingale and an increasing process is extended in several ways for two-parameter stochastic processes. In particular, the notion of laplacian is introduced which gives more explicit decomposition for potentials. The optional sampling theorem is stated for a wide class of supermartingales justifying the study of local martingales. Conditions for regularity and continuity for two-parameter processes are given using approximate laplacians. By introducing the notion of optional increasing path, the relation between the regularity of certain quasimartingales and the continuity of the associated integrable variation process is proved.     

Two Paths Joining Given Vertices in 2k-Edge-Connected Graphs

Let k≥2 be an integer and G = (V(G), E(G)) be a k-edge-connected graph. For X⊆V(G), e(X) denotes the number of edges between X and V(G) − X. Let {s_i, t_i}⊆X_i⊆V(G) (i=1,2) and X₁∩X₂=∅. We here prove that if k is even and e(X_i)≤2k−1 (i=1,2), then there exist paths P₁ and P₂ such that P_i joins s_i and t_i, V(P_i)⊆X_i (i=1,2) and G − E(P₁∪P₂) is (k−2)-edge-connected (for odd k, if e(X₁)≤2k−2 and e(X₂)≤2k−1, then the same result holds [10]), and we give a generalization of this result and some other results about paths not containing given edges.     

An exact algorithm for a single-vehicle routing problem with time windows and multiple routes

This paper describes an exact algorithm for solving a problem where the same vehicle performs several routes to serve a set of customers with time windows. The motivation comes from the home delivery of perishable goods, where vehicle routes are short and must be combined to form a working day. A method based on an elementary shortest path algorithm with resource constraints is proposed to solve this problem. The method is divided into two phases: in the first phase, all non-dominated feasible routes are generated; in the second phase, some routes are selected and sequenced to form the vehicle workday. Computational results are reported on Euclidean problems derived from benchmark instances of the classical vehicle routing problem with time windows.     

Arc routing problems with time-dependent service costs

This paper studies an arc routing problem with capacity constraints and time-dependent service costs. This problem is motivated by winter gritting applications where the “timing” of each intervention is crucial. The exact problem-solving approach reported here first transforms the arc routing problem into an equivalent node routing problem. Then, a column generation scheme is used to solve the latter. The master problem is a classical set covering problem, while the subproblems are time-dependent shortest path problems with resource constraints. These subproblems are solved using an extension of a previously developed algorithm. Computational results are reported on problems derived from a set of classical instances of the vehicle routing problem with time windows.     

Path Capacity Dimensioning in a Multiprotocol Label Switched Network: Analysis of Optimal and Suboptimal Solutions

In recent years, the problem of capacity allocation for a label switched patch (LSP) in a multiprotocol label switched (MPLS) network has received great attention due to its relevance in the context of traffic control. In this paper, the problem of capacity allocation is formulated as an optimal control problem and its solution is obtained by assuming the knowledge of the bandwidth requests on the entire control interval. A suboptimal solution is also given which has the advantage of requiring limited information about future bandwidth requests. The analysis of the suboptimal solution is explored both analytically and numerically by using simulated and real data. This study demonstrates that the suboptimal solution, also with limited knowledge of the future, yields a good approximation of the optimal one and requires little additional cost.     

Accelerated label setting algorithms for the elementary resource constrained shortest path problem

A label setting algorithm for solving the Elementary Resource Constrained Shortest Path Problem, using node resources to forbid repetition of nodes on the path, is implemented. A state-space augmenting approach for accelerating run times is considered. Several augmentation strategies are suggested and compared numerically.     

A variation embedding theorem and applications

Fractional Sobolev spaces, also known as Besov or Slobodetski spaces, arise in many areas of analysis, stochastic analysis in particular. We prove an embedding into certain q-variation spaces. Applications include a new route to a regularity result by Kusuoka for stochastic differential equations, integration against Besov-paths, a regularity criterion for rough paths and a new regularity result for Cameron-Martin paths associated to fractional Brownian motion.