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.     

On the power and limitations of affine policies in two-stage adaptive optimization

We consider a two-stage adaptive linear optimization problem under right hand side uncertainty with a min–max objective and give a sharp characterization of the power and limitations of affine policies (where the second stage solution is an affine function of the right hand side uncertainty). In particular, we show that the worst-case cost of an optimal affine policy can be times the worst-case cost of an optimal fully-adaptable solution for any δ > 0, where m is the number of linear constraints. We also show that the worst-case cost of the best affine policy is times the optimal cost when the first-stage constraint matrix has non-negative coefficients. Moreover, if there are only k ≤ m uncertain parameters, we generalize the performance bound for affine policies to , which is particularly useful if only a few parameters are uncertain. We also provide an -approximation algorithm for the general case without any restriction on the constraint matrix but the solution is not an affine function of the uncertain parameters. We also give a tight characterization of the conditions under which an affine policy is optimal for the above model. In particular, we show that if the uncertainty set, is a simplex, then an affine policy is optimal. However, an affine policy is suboptimal even if is a convex combination of only (m + 3) extreme points (only two more extreme points than a simplex) and the worst-case cost of an optimal affine policy can be a factor (2 − δ) worse than the worst-case cost of an optimal fully-adaptable solution for any δ > 0.     

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.     

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     

On saturation effects in the Neumann boundary control of elliptic optimal control problems

A Neumann boundary control problem for a linear-quadratic elliptic optimal control problem in a polygonal domain is investigated. The main goal is to show an optimal approximation order for discretized problems after a postprocessing process. It turns out that two saturation processes occur: The regularity of the boundary data of the adjoint is limited if the largest angle of the polygon is at least 2π/3. Moreover, piecewise linear finite elements cannot guarantee the optimal order, if the largest angle of the polygon is greater than π/2. We will derive error estimates of order h ^α with α∈[1,2] depending on the largest angle and properties of the finite elements. Finally, numerical test illustrates the theoretical results.     

Reconstructing a random scenery observed with random errors along a random walk path

 We show that an i.i.d. uniformly colored scenery on ℤ observed along a random walk path with bounded jumps can still be reconstructed if there are some errors in the observations. We assume the random walk is recurrent and can reach every point with positive probability. At time k, the random walker observes the color at her present location with probability 1−δ and an error Y _k with probability δ. The errors Y _k , k≥0, are assumed to be stationary and ergodic and independent of scenery and random walk. If the number of colors is strictly larger than the number of possible jumps for the random walk and δ is sufficiently small, then almost all sceneries can be almost surely reconstructed up to translations and reflections. Received: 3 February 2002 / Revised version: 15 January 2003 Published online: 28 March 2003 Mathematics Subject Classification (2000): 60K37, 60G50 Key words or phrases:Scenery reconstruction – Random walk – Coin tossing problems     

An exact algorithm for minimum CDS with shortest path constraint in wireless networks

In this paper, we study a minimum connected dominating set problem (CDS) in wireless networks, which selects a minimum CDS with property that all intermediate nodes inside every pairwise shortest path should be included. Such a minimum CDS (we name this problem as SPCDS) is an important tache of some other algorithms for constructing a minimum CDS. We prove that finding such a minimum SPCDS can be achieved in polynomial time and design an exact algorithm with time complexity O(δ ² n), where δ is the maximum node degree in communication graph.     

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 .     

Cantor-Bendixson degrees and convexity in ℝ2

We present an ordinal rank, δ³, which refines the standard classification of non-convexity among closed planar sets. The class of closed planar sets falls into a hierarchy of order type ω₁ + 1 when ordered by δ-rank. The rank δ³ (S) of a setS is defined by means of topological complexity of 3-cliques in the set. A 3-clique in a setS is a subset ofS all of whose unordered 3-tuples fail to have their convex hull inS. Similarly, δⁿ (S) is defined for alln>1. The classification cannot be done using δ², which considers only 2-cliques (known in the literature also as “visually independent subsets”), and in dimension 3 or higher the analogous classification is not valid.     

Optimal quality of exceptional points for the Lebesgue density theorem

In spite of the Lebesgue density theorem, there is a positive δ such that, for every non-trivial measurable set S⊂ℝ, there is a point at which both the lower densities of S and of ℝ∖S are at least δ. The problem of determining the supremum of possible values of this δ was studied in a paper of V. I. Kolyada, as well as in some recent papers. We solve this problem in the present work.     

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.     

Approximation bounds for quadratic maximization and max-cut problems with semidefinite programming relaxation

In this paper,we consider a class of quadratic maximization problems.For a subclass of the problems,we show that the SDP relaxation approach yields an approximation solution with the ratio is dependent on the data of the problem with α being a uniform lower bound.In light of this new bound,we show that the actual worst-case performance ratio of the SDP relaxation approach (with the triangle inequalities added) is at least α δd if every weight is strictly positive,where δd ＞ 0 is a constant depending on the problem dimension and data.     

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.     

Not collapsing cardinals ≤<Emphasis Type="Italic">κ</Emphasis> in (<<Emphasis Type="Italic">κ</Emphasis>)-support iterations

We deal with the problem of preserving various versions of completeness in (<κ)-support iterations of forcing notions, generalizing the case “S-complete proper is preserved by CS iterations for a stationary costationaryS⊆ω ₁”. We give applications to Uniformization and the Whitehead problem. In particular, for a strongly inaccessible cardinalκ and a stationary setS⊆κ with fat complement we can have uniformization for every (A _δ :δ ∈S′),A _δ ⊆δ = supA _δ , cf (δ) = otp(A _δ ) and a stationary non-reflecting setS′⊆S (see B.8.2). Research supported by The German-Israeli Foundation for Scientific Research & Development Grant No. G-294.081.06/93 and by The National Science Foundation Grant No. 144-EF67. Publication No. 587.     

Optimization problems with algebraic solutions: Quadratic fractional programs and ratio games

A mathematical program with a rational objective function may have irrational algebraic solutions even when the data are integral. We suggest that for such problems the optimal solution will be represented as follows: If λ* denotes the optimal value there will be given an intervalI and a polynomialP(λ) such thatI contains λ* and λ* is the unique root ofP(λ) inI. It is shown that with this representation the solutions to convex quadratic fractional programs and ratio games can be obtained in polynomial time.     

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.     

Optimal Topological Simplification of Discrete Functions on Surfaces

Given a function f on a surface and a tolerance δ>0, we construct a function f _δ subject to ‖f _δ −f‖_∞≤δ such that f _δ has a minimum number of critical points. Our construction relies on a connection between discrete Morse theory and persistent homology and completely removes homological noise with persistence ≤2δ from the input function f. The number of critical points of the resulting simplified function f _δ achieves the lower bound dictated by the stability theorem of persistent homology. We show that the simplified function can be computed in linear time after persistence pairs have been computed.     

Two-level additive Schwarz preconditioners for C 0 interior penalty methods

We study two-level additive Schwarz preconditioners that can be used in the iterative solution of the discrete problems resulting from C⁰ interior penalty methods for fourth order elliptic boundary value problems. We show that the condition number of the preconditioned system is bounded by C(1+(H³/δ³)), where H is the typical diameter of a subdomain, δ measures the overlap among the subdomains and the positive constant C is independent of the mesh sizes and the number of subdomains. This work was supported in part by the National Science Foundation under Grant No. DMS-03-11790.     

Centering Problems for Probability Measures on Finite-Dimensional Vector Spaces

The paper deals with various centering problems for probability measures on finite-dimensional vector spaces. We show that for every such measure, there exists a vector h satisfying μ δ(h)=S(μ δ(h)) for each symmetry S of μ, generalizing thus Jurek’s result obtained for full measures. An explicit form of the h is given for infinitely divisible μ. The main result of the paper consists in the analysis of quasi-decomposable (operator-semistable and operator-stable) measures and finding conditions for the existence of a “universal centering” of such a measure to a strictly quasi-decomposable one.     

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 ε.