A faster capacity scaling algorithm for minimum cost submodular flow

We describe an O(n ⁴ hmin{logU,n ²logn}) capacity scaling algorithm for the minimum cost submodular flow problem. Our algorithm modifies and extends the Edmonds–Karp capacity scaling algorithm for minimum cost flow to solve the minimum cost submodular flow problem. The modification entails scaling a relaxation parameter δ. Capacities are relaxed by attaching a complete directed graph with uniform arc capacity δ in each scaling phase. We then modify a feasible submodular flow by relaxing the submodular constraints, so that complementary slackness is satisfied. This creates discrepancies between the boundary of the flow and the base polyhedron of a relaxed submodular function. To reduce these discrepancies, we use a variant of the successive shortest path algorithm that augments flow along minimum cost paths of residual capacity at least δ. The shortest augmenting path subroutine we use is a variant of Dijkstra’s algorithm modified to handle exchange capacity arcs efficiently. The result is a weakly polynomial time algorithm whose running time is better than any existing submodular flow algorithm when U is small and C is big. We also show how to use maximum mean cuts to make the algorithm strongly polynomial. The resulting algorithm is the first capacity scaling algorithm to match the current best strongly polynomial bound for submodular flow. Received: August 6, 1999 / Accepted: July 2001?Published online October 2, 2001     

Efficient Algorithms for Approximating Polygonal Chains

We consider the problem of approximating a polygonal chain C by another polygonal chain C' whose vertices are constrained to be a subset of the set of vertices of C . The goal is to minimize the number of vertices needed in the approximation C' . Based on a framework introduced by Imai and Iri [25], we define an error criterion for measuring the quality of an approximation. We consider two problems. (1) Given a polygonal chain C and a parameter ɛ \geq 0 , compute an approximation of C , among all approximations whose error is at most ɛ , that has the smallest number of vertices. We present an O(n ^{4/3 + δ} ) -time algorithm to solve this problem, for any δ > 0; the constant of proportionality in the running time depends on δ . (2) Given a polygonal chain C and an integer k , compute an approximation of C with at most k vertices whose error is the smallest among all approximations with at most k vertices. We present a simple randomized algorithm, with expected running time O(n ^{4/3 + δ} ) , to solve this problem. Received September 17, 1998, and in revised form July 8, 1999.     

Existence of rainbow matchings in properly edge-colored graphs

Let G be a properly edge-colored graph. A rainbow matching of G is a matching in which no two edges have the same color. Let δ denote the minimum degree of G. We show that if |V(G)| > (δ ² + 14δ + 1)/4, then G has a rainbow matching of size δ, which answers a question asked by G. Wang [Electron. J. Combin., 2011, 18: #N162] affirmatively. In addition, we prove that if G is a properly colored bipartite graph with bipartition (X, Y) and max{|X|, |Y|} > (δ ² + 4δ − 4)/4, then G has a rainbow matching of size δ.     

Standing waves in the FitzHugh-Nagumo system and a problem in combinatorial geometry

We show that there is a close relation between standing-wave solutions for the FitzHugh-Nagumo system where 0<a<1/2 and δ γ=β ² ∈ (0,a), and the following combinatorial problem: (*) Given K points Q ₁ , . . . , Q _K ∈R ^N with minimum distance 1, find out the maximum number of times that the minimum distance 1 can occur. More precisely, we show that for any given positive integer K, there is a δ _K >0 such that for 0<δ<δ _K , there exists a standing-wave solution (u _δ ,ν _δ ) to the FitzHugh-Nagumo system with the property that u _δ has K spikes Q ^δ ₁,. . .,Q ^δ _K and approaches an optimal configuration in (*), where .     

Effect of aspect ratio on the meridional circulation of a rotating homogeneous fluid

The effect of aspect ratio on the meridional circulation of a homogeneous fluid is analyzed. Aspect ratio is allowed to range between zero and unity. Relationships between possible horizontal and vertical length scales are obtained by length scale analysis as well as by solving an idealized problem. It is found that whenE ^1/2 ≪ Z ≪ E^1/2/δ, whereE is the Ekman number, the stream lines are closely packed near the sidewall within a thickness ofO(E ^1/2). The effect of stratification is unimportant within this depth range. In the depth rangeE ^1/2 /δ ≪ Z ≪ 1/Eδ the vertical boundary layer in which the streamlines are packed is ofO(EZδ) ^1/3. WhenZ ≫ 1/Eδ it is shown that the circulation decays algebraically with depth as 1/Z.     

On the number of Galois points for a plane curve in positive characteristic,III

We consider the following problem: For a smooth plane curve C of degree d ≥ 4 in characteristic p > 0, determine the number δ(C) of inner Galois points with respect to C. This problem seems to be open in the case where d ≡ 1 mod p and C is not a Fermat curve F(p ^e  + 1) of degree p ^e  + 1. When p ≠ 2, we completely determine δ(C). If p = 2 (and C is in the open case), then we prove that δ(C) = 0, 1 or d and δ(C) = d only if d−1 is a power of 2, and give an example with δ(C) = d when d = 5. As an application, we characterize a smooth plane curve having both inner and outer Galois points. On the other hand, for Klein quartic curve with suitable coordinates in characteristic two, we prove that the set of outer Galois points coincides with the one of \mathbbF₂{\mathbb{F}_{2}} -rational points in \mathbbP²{\mathbb{P}^{2}}.     

Representing a Functional Curve by Curves with Fewer Peaks

In this paper, we study the problems of (approximately) representing a functional curve in 2-D by a set of curves with fewer peaks. Representing a function (or its curve) by certain classes of structurally simpler functions (or their curves) is a basic mathematical problem. Problems of this kind also find applications in applied areas such as intensity-modulated radiation therapy (IMRT). Let f\bf f be an input piecewise linear functional curve of size n. We consider several variations of the problems. (1) Uphill–downhill pair representation (UDPR): Find two nonnegative piecewise linear curves, one nondecreasing (uphill) and one nonincreasing (downhill), such that their sum exactly or approximately represents f\bf f. (2) Unimodal representation (UR): Find a set of unimodal (single-peak) curves such that their sum exactly or approximately represents f\bf f. (3) Fewer-peak representation (FPR): Find a piecewise linear curve with at most k peaks that exactly or approximately represents f\bf f. Furthermore, for each problem, we consider two versions. For the UDPR problem, we study its feasibility version: Given ε>0, determine whether there is a feasible UDPR solution for f\bf f with an approximation error ε; its min-ε version: Compute the minimum approximation error ε ^∗ such that there is a feasible UDPR solution for f\bf f with error ε ^∗. For the UR problem, we study its min-k version: Given ε>0, find a feasible solution with the minimum number k ^∗ of unimodal curves for f\bf f with an error ε; its min-ε version: given k>0, compute the minimum error ε ^∗ such that there is a feasible solution with at most k unimodal curves for f\bf f with error ε ^∗. For the FPR problem, we study its min-k version: Given ε>0, find one feasible curve with the minimum number k ^∗ of peaks for f\bf f with an error ε; its min-ε version: given k≥0, compute the minimum error ε ^∗ such that there is a feasible curve with at most k peaks for f\bf f with error ε ^∗. Little work has been done previously on solving these functional curve representation problems. We solve all the problems (except the UR min-ε version) in optimal O(n) time, and the UR min-ε version in O(n+mlog m) time, where m<n is the number of peaks of f\bf f. Our algorithms are based on new geometric observations and interesting techniques.     

Approximation Algorithm for MAX DICUT with Given Sizes of Parts

Given a directed graph G and an edge weight function w : A(G)→ R^ , the maximum directed cut problem (MAX DICUT) is that of finding a directed cut δ(S) with maximum total weight. We consider a version of MAX DICUT -- MAX DICUT with given sizes of parts or MAX DICUT WITH GSP -- whose instance is that of MAX DICUT plus a positive integer k, and it is required to find a directed cut δ(S) having maximum weight over all cuts δ(S) with |S| -- k. We present an approximation algorithm for this problem which is based on semidefinite programming (SDP) relaxation. The algorithm achieves the presently best performance guarantee for a range of k.     

Construction of nonlinear regulators in economic growth models

We prove an inequality for the second moduli of continuity of continuous functions. Applying this inequality, we construct a nonnegative nonincreasing continuous function ω on [0, +g8) that vanishes at zero and is such that the function ω(δ)/δ ² decreases on (0, +g8) while ω is not asymptotically (as δ → 0) equivalent to the second modulus of continuity of any continuous function.     

Extensions to online delay management on a single train line: new bounds for delay minimization and profit maximization

We present extensions to the Online Delay Management Problem on a Single Train Line. While a train travels along the line, it learns at each station how many of the passengers wanting to board the train have a delay of δ. If the train does not wait for them, they get delayed even more since they have to wait for the next train. Otherwise, the train waits and those passengers who were on time are delayed by δ. The problem consists in deciding when to wait in order to minimize the total delay of all passengers on the train line. We provide an improved lower bound on the competitive ratio of any deterministic online algorithm solving the problem using game tree evaluation. For the extension of the original model to two possible passenger delays δ ₁ and δ ₂, we present a 3-competitive deterministic online algorithm. Moreover, we study an objective function modeling the refund system of the German national railway company, which pays passengers with a delay of at least Δ a part of their ticket price back. In this setting, the aim is to maximize the profit. We show that there cannot be a deterministic competitive online algorithm for this problem and present a 2-competitive randomized algorithm.     

New improvements on connectivity of cages

A (δ, g)-cage is a δ-regular graph with girth g and with the least possible number of vertices. In this paper, we show that all (δ, g)-cages with odd girth g ≥ 9 are r-connected, where (r − 1)² ≤ δ + $ \sqrt \delta $ \sqrt \delta − 2 < r ² and all (δ, g)-cages with even girth g ≥ 10 are r-connected, where r is the largest integer satisfying $ \frac{{r\left( {r - 1} \right)^2 }} {4} + 1 + 2r\left( {r - 1} \right) \leqslant \delta $ \frac{{r\left( {r - 1} \right)^2 }} {4} + 1 + 2r\left( {r - 1} \right) \leqslant \delta . These results support a conjecture of Fu, Huang and Rodger that all (δ, g)-cages are δ-connected.     

Optimal Stochastic Impulse Control with Delayed Reaction

We study impulse control problems of jump diffusions with delayed reaction. This means that there is a delay δ>0 between the time when a decision for intervention is taken and the time when the intervention is actually carried out. We show that under certain conditions this problem can be transformed into a sequence of iterated no-delay optimal stopping problems and there is an explicit relation between the solutions of these two problems. The results are illustrated by an example where the problem is to find the optimal times to increase the production capacity of a firm, assuming that there are transaction costs with each new order and the increase takes place δ time units after the (irreversible) order has been placed.     

Sharp Upper Bounds on the Minimum Number of Components of 2-factors in Claw-free Graphs

Let G be a claw-free graph with order n and minimum degree δ. We improve results of Faudree et al. and Gould & Jacobson, and solve two open problems by proving the following two results. If δ = 4, then G has a 2-factor with at most (5n − 14)/18 components, unless G belongs to a finite class of exceptional graphs. If δ ≥ 5, then G has a 2-factor with at most (n − 3)/(δ − 1) components, unless G is a complete graph. These bounds are best possible in the sense that we cannot replace 5/18 by a smaller quotient and we cannot replace δ − 1 by δ, respectively.     

Partitioning series-parallel multigraphs into ν *-excluding edge covers

We prove that, for any given vertex ν* in a series-parallel graph G, its edge set can be partitioned into κ = min{κ′(G) + 1, δ(G)} subsets such that each subset covers all the vertices of G possibly except for ν*, where δ(G) is the minimum degree of G and κ′(G) is the edge-connectivity of G. In addition, we show that the results in this paper are best possible and a polynomial time algorithm can be obtained for actually finding such a partition by our proof.     

Wavelet characterization of Hörmander symbol classS ρ,δ m and applications

In this paper, we characterize the symbol in Hormander symbol classS _ρ ^m ,δ (m ∈ R, ρ, δ ≥ 0) by its wavelet coefficients. Consequently, we analyse the kerneldistribution property for the symbol in the symbol classS _ρ ^m ,δ (m ∈R, ρ > 0, δ≥ 0) which is more general than known results ; for non-regular symbol operators, we establish sharp L²-continuity which is better than Calderón and Vaillancourt’s result, and establishL ^p (1 ≤p ≤∞) continuity which is new and sharp. Our new idea is to analyse the symbol operators in phase space with relative wavelets, and to establish the kernel distribution property and the operator’s continuity on the basis of the wavelets coefficients in phase space.     

Random homeomorphisms and fourier expansions — The pointwise behaviour

Let ϕ be a Dubins-Freedman random homeomorphism on [0, 1] derived from the base measure uniform on {x=1/2}, and letf be a periodic function satisfying |f(δ)−f(0)|=o(log log log 1/δ)⁻¹. Then the Fourier expansion off o ϕ converges at 0 with probability 1. In the condition onf, o cannot be replaced byO. Also we deduce some 0–1 laws for this kind of problem. The research was supported by The Israel Science Foundation (grant no. 4/01).     

The extrapolation of band-limited signals in L2 with sampling errors

In this paper we will provide a theory for an extrapolation algorithm of band-limited signals with sampling errors or low noises. The main result is as follows: Suppose thatf(t) is in L² and is a continuous Ω band-limited signal. Then for any positive numbers T, A(>T) and ε, there exists a δ>0 such that when the sampling errors (or noises) off(t) on [−T, T] is less than δ we can extrapolate the values off(t) on the interval [−A, A] such that the difference between the extrapolated value and the exact value off(t) does not exceed ε.     

Boundary Value Problems with Compatible Boundary Conditions

If Y is a subset of the space ℝⁿ × ℝⁿ, we call a pair of continuous functions U, V Y-compatible, if they map the space ℝⁿ into itself and satisfy Ux · Vy ≥ 0, for all (x, y) ∈ Y with x · y ≥ 0. (Dot denotes inner product.) In this paper a nonlinear two point boundary value problem for a second order ordinary differential n-dimensional system is investigated, provided the boundary conditions are given via a pair of compatible mappings. By using a truncation of the initial equation and restrictions of its domain, Brouwer's fixed point theorem is applied to the composition of the consequent mapping with some projections and a one-parameter family of fixed points P _δ is obtained. Then passing to the limits as δ tends to zero the so-obtained accumulation points are solutions of the problem.     

Perturbed boundary eigenvalue problem for the Schrödinger operator on an interval

A perturbed two-parameter boundary value problem is considered for a second-order differential operator on an interval with Dirichlet conditions. The perturbation is described by the potential μ⁻¹ V((x − x ₀)ɛ⁻¹), where 0 < ɛ ≪ 1 and μ is an arbitrary parameter such that there exists δ > 0 for which ɛ/μ = o(ɛ^δ). It is shown that the eigenvalues of this operator converge, as ɛ → 0, to the eigenvalues of the operator with no potential. Complete asymptotic expansions of the eigenvalues and eigenfunctions of the perturbed operator are constructed.     

Notes on δ-Koszul Algebras

This paper is a continuous work of δ-Koszul algebras, which were first introduced by Green and Marcos in 2005 (see Green and Marcos, Commun Algebra 33(6):1753–1764, 2005). Let K^d(A)\mathcal{K}^{\delta}(A) be the category of δ-Koszul modules. It is proved that K^d(A)\mathcal{K}^{\delta}(A) preserves kernels of epimorphisms if and only if the “minimal Horseshoe Lemma” (“MHL” for short) holds. Further, a special class of δ-Koszul algebras named periodic δ -algebras are introduced, which have close connection with Koszul algebras and provide answers to the questions raised by Green and Marcos (Commun Algebra 33(6):1753–1764, 2005). Finally, we construct new periodic δ-algebras from the given ones in terms of one-point extension and sum-extension.