Refine
Year of publication
Language
- English (1103) (remove)
Keywords
- optimal control (27)
- stability (14)
- integer programming (11)
- Stochastic programming (9)
- finite elements (9)
- mixed integer programming (9)
- Hamiltonian matrix (8)
- finite element method (8)
- model reduction (8)
- state constraints (8)
Periodic timetabling for railway networks is usually modeled by the Periodic Event Scheduling
Problem (PESP). This model permits to express many requirements that practitioners impose
on periodic railway timetables. We discuss a requirement practitioners are asking for, but which,
so far, has not been the topic of mathematical studies: the concept of symmetry.
Several motivations why symmetric timetables might seem promising will be given. However,
we provide examples showing that symmetry leads to suboptimality.
To integrate symmetry into the graph model of the PESP, there are many obstacles to overcome.
Nevertheless, adding symmetry requirements to mixed-integer programming formulations
explicitly, enables MIP solvers such as CPLEX
to terminate earlier with good solutions.
This paper is concerned with transparent boundary conditions
(TBCs) for the time-dependent Schrödinger equation in one and two
dimensions. Discrete TBCs are introduced in the numerical simulations
of whole space problems in order to reduce the computational
domain to a finite region. Since the discrete TBC for the Schrödinger
equation includes a convolution w.r.t. time with a weakly decaying
kernel, its numerical evaluation becomes very costly for large-time
simulations.
As a remedy we construct approximate TBCs with a kernel having
the form of a finite sum-of-exponentials, which can be evaluated
in a very efficient recursion. We prove stability of the resulting initialboundary
value scheme, give error estimates for the considered approximation
of the boundary condition, and illustrate the efficiency of
the proposed method on several examples.
In this paper we introduce the notion of smoothed competitive analysis of online
algorithms. Smoothed analysis has been proposed by Spielman and Teng [22] to explain
the behaviour of algorithms that work well in practice while performing very poorly
from a worst case analysis point of view. We apply this notion to analyze the Multi-
Level Feedback (MLF) algorithm to minimize the total flow time on a sequence of
jobs released over time when the processing time of a job is only known at time of
completion.
The initial processing times are integers in the range [1, 2K ]. We use a partial bit
randomization model, where the initial processing times are smoothened by changing
the k least significant bits under a quite general class of probability distributions. We
show that MLF admits a smoothed competitive ratio of O(max((2k /σ)3 , (2k /σ)2 2K−k )),
where σ denotes the standard deviation of the distribution. In particular, we obtain a
competitive ratio of O(2K−k ) if σ = Θ(2k ). We also prove an Ω(2K−k ) lower bound for
any deterministic algorithm that is run on processing times smoothened according to
the partial bit randomization model. For various other smoothening models, including
the additive symmetric smoothening model used by Spielman and Teng [22], we give a
higher lower bound of Ω(2K ).
A direct consequence of our result is also the first average case analysis of MLF. We
show a constant expected ratio of the total flow time of MLF to the optimum under
several distributions including the uniform distribution.
The paper presents a new affine invariant theory on asymptotic mesh
independence of Newton’s method for discretized nonlinear operator equations.
Compared to earlier attempts, the new approach is both much simpler
and more intuitive from the algorithmic point of view. The theory
is exemplified at collocation methods for ODE boundary value problems
and at finite element methods for elliptic PDE problems.
In this article, we use numerical simulation to investigate transient temperature
phenomena during sublimation growth of SiC single crytals via physical
vapor transport (also called the modified Lely method). We consider the evolution
of temperatures at the SiC source and at the SiC seed crystal, which
are highly relevant to the quality of the grown crystals, but inaccessible to
direct measurements. The simulations are based on a transient mathematical
model for the heat transport, including heat conduction, radiation, and radio
frequency (RF) induction heating. Varying the position of the induction coil
as well as the heating power, it is shown that the measurable temperature difference
between the bottom and the top of the growth apparatus can usually
not be used as a simple indicator for the respective temperature difference
between SiC source and seed. Moreover, it is shown that there can be a time
lack of 1.5 hours between the heating of the temperature measuring points
and the heating of the interior of the SiC source.
We discuss the problem to count, or, more modestly, to estimate
the number f(m; n) of unimodular triangulations of the planar grid of
size m * n.
Among other tools, we employ recursions that allow one to compute
the (huge) number of triangulations for small m and rather large n by
dynamic programming; we show that this computation can be done in
polynomial time if m is fixed, and present computational results from
our implementation of this approach.
We also present new upper and lower bounds for large m and n,
and we report about results obtained from a computer simulation of
the random walk that is generated by
ips.
We investigate the worst-case behavior of the simplex algorithm on linear programs
with 3 variables, that is, on 3-dimensional simple polytopes. Among the
pivot rules that we consider, the “random edge” rule yields the best asymptotic
behavior as well as the most complicated analysis. All other rules turn out to be
much easier to study, but also produce worse results: Most of them show essentially
worst-possible behavior; this includes both Kalai’s “random-facet” rule, which is
known to be subexponential without dimension restriction, as well as Zadeh’s deterministic
history-dependent rule, for which no non-polynomial instances in general
dimensions have been found so far.
Abstract. Let Xd,n be an n-element subset of {0, 1}d chosen uniformly
at random, and denote by Pd,n := conv Xd,n its convex hull. Let ∆d,n
be the density of the graph of Pd,n (i.e., the number of one-dimensional
faces of Pd,n divided by n ). Our main result is that, for any function 2
n(d), the expected value of ∆d,n(d) converges (with d → ∞) to one if, √
for some arbitrary ε < 0, n(d) ≤ ( 2 − ε)d holds for all large d, while it √
converges to zero if n(d) ≥ ( 2 + ε)d holds for all large d.