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)
Abstract. Let P be a random 0/1-polytope in Rd with n(d) vertices, and denote by νr (P ) the
quotient of the number of faces of P with exactly r vertices and n(d) (the r-density of P ). For each
r
r ≥ 3, we establish the existence of a sharp threshold for the r-density and determine the values of
the threshold numbers τr such that, for all ε > 0,
E [νr (P )] =
1 − o(1)
o(1)
if n(d) ≤ 2(τr −ε)d for all d
if n(d) ≥ 2(τr +ε)d for all d
holds for the expected value of νr (P ). The threshold for r = 2 has already been determined in [8].
In particular, these results indicate that the high densities often encountered in polyhedral com-
binatorics (e.g., the cut-polytope has both 2- and 3-density equal to one) is due to the geometry of
0/1-polytopes rather than to the special combinatorics of the underlying problems.
We consider the scheduling problem of minimizing the average-weighted completion time on identical parallel machines when jobs are arriving over time. For both the preemptive and the nonpreemptive setting, we show that straightforward extensions of Smith's ratio rule yield smaller competitive ratios than the previously best-known deterministic on-line algorithms.
How to Whack Moles
(2004)
In the classical whack-a-mole game moles that pop up at
certain locations must be whacked by means of a hammer before they
go under ground again. The goal is to maximize the number of moles
caught. This problem can be formulated as an online optimization problem:
Requests (moles) appear over time at points in a metric space and
must be served (whacked) by a server (hammer) before their deadlines
(i.e., before they disappear). An online algorithm learns each request
only at its release time and must base its decisions on incomplete information.
We study the online whack-a-mole problem (wham) on the real
line and on the uniform metric space. While on the line no deterministic
algorithm can achieve a constant competitive ratio, we provide competitive
algorithms for the uniform metric space. Our online investigations
are complemented by complexity results for the offline problem.
In this paper we analyze decompositions of reversible nearly uncoupled
Markov chains into rapidly mixing subchains. We state upper
bounds on the 2nd eigenvalue for restriction and stochastic complementation
chains of reversible Markov chains, as well as a relation between
them. We illustrate the obtained bounds analytically for bunkbed
graphs, and furthermore apply them to restricted Markov chains that
arise when analyzing conformation dynamics of a small biomolecule.
Fractional multistep methods were introduced by C. Lubich for the quadrature of Abel integral operators and the solution of weakly singular Volterra integral equations of the first kind with exactly given right-hand sides. In the current paper, we consider the regularizing properties of these methods to solve the mentioned integral equations of the first kind for perturbed right-hand sides. Finally, numerical results are presented.
We present an algorithm that constructs parametrizations of boundary
and interface surfaces automatically. Starting with high-resolution triangulated
surfaces describing the computational domains, we iteratively
simplify the surfaces yielding a coarse approximation of the boundaries
with the same topological type. While simplifying we construct a function
that is defined on the coarse surface and whose image is the original
surface. This function allows access to the correct shape and surface normals
of the original surface as well as to any kind of data defined on it.
Such information can be used by geometric multigrid solvers doing adaptive
mesh refinement. Our algorithm runs stable on all types of input
surfaces, including those that describe domains consisting of several materials.
We have used our method with success in different fields and we
discuss examples from structural mechanics and biomechanics.
We use a numerical optimization method to determine the control parameters
frequency, power, and coil position for the radio frequency (RF) induction
heating of the growth apparatus during sublimation growth of SiC single crystals
via physical vapor transport (PVT) (also called the modified Lely method). The
control parameters are determined to minimize a functional, tuning the radial
temperature gradient on the single crystal surface as well as the vertical temperature
gradient between SiC source and seed, both being crucial for high-quality
growth. The optimization is subject to constraints with respect to a required
temperature difference between source and seed, a required temperature range at
the seed, and an upper bound for the temperature in the entire apparatus. The
numerical computations use a stationary mathematical model for the heat transport,
including heat conduction, radiation, and RF heating to solve the forward
problem, and a Nelder-Mead method for optimization. A minimal radial temperature
gradient is found to coincide with a minimal temperature at the single
crystal surface, and a maximal temperature gradient between source and seed is
found to coincide with a low coil position.
The UMTS radio network planning problem poses the challenge of designing a cost-effective network that provides users with sufficient coverage and capacity. We describe an optimization model for this problem that is based on comprehensive planning data of the EU project MOMENTUM. We present heuristic mathematical methods for this realistic model, including computational results.
Relaying is a protocol extension for cellular wireless computer networks; in order to utilize radio resources more efficiently, several hops are allowed within one cell. This paper investigates the principle potential of relaying by casting transmission scheduling as a mathematical optimization problem, namely, a linear program. We analyze the throughput gains showing that, irrespective of the concrete scheduling algorithm, performance gains of up to 30\% on average for concrete example networks are achievable.
Relaying - allowing multiple wireless hops - is a protocol extension
for cellular networks conceived to improve data throughput. Its benefits have only
been quantfied for small example networks. For assessing its general potential,
we define a complex resource allocation/scheduling problem. Several mathematical
models are presented for this problem; while a time-expanded MIP approach turns
out intractable, a sophisticated column generation scheme leads to good computational
results. We thereby show that for selected cases relaying can increase data
throughput by 30% on the average.