Refine
Year of publication
- 2005 (113) (remove)
Keywords
- optimal stopping (2)
- stability (2)
- American options (1)
- BSDE (1)
- Becker-Doering equations (1)
- Finance (1)
- Hidden Markov Model (1)
- Hierarchical matrices (1)
- IP (1)
- Instances (1)
We consider the design of a logical network topology, together with node hardware, link capacities, and a survivable routing of demands. In addition to all single node failures, the routing must also survive multiple logical link failures caused by single failures in the underlying physical network. Furthermore, the number of logical links supported by a physical link is bounded. We propose an integer linear programming model for this design problem, together with a branch-and-cut based solution approach combined with column generation. The model and algorithm are tested on three real-world test instances, and preliminary results are given.
We present a new mathematical approach to metabolic pathway analysis, characterizing a metabolic network by minimal metabolic behaviors and the reversible metabolic space. Our method uses an outer description of the steady state flux cone, based on sets of irreversible reactions. This is different from existing approaches, such as elementary flux modes or extreme pathways, which use an inner description, based on sets of generating vectors. The resulting description of the flux cone is much more compact. By focussing on the reversible and irreversible reactions, our approach provides a different view of the network, which may also lead to new biological insights.
Descriptor systems present a general
mathematical framework for the modelling, simulation and control of complex dynamical systems arising in many areas of mechanical,
electrical and chemical engineering. This
paper presents a survey of the current theory of descriptor systems,concerning
solvability, stability, model reduction, controllability, observability and optimal control.
Many online problems encountered in real-life involve a two-stage decision process: upon arrival of a new request, an irrevocable
first-stage decision (the assignment of a specific resource to the request) must be made immediately, while in a second stage process, certain ``subinstances'' (that is, the instances of all requests assigned to a particular resource) can be solved to optimality (offline) later.
We introduce the novel concept of an Online Target Date Assignment Problem (OnlineTDAP) as a general framework for online problems with this nature. Requests for the OnlineTDAP become known at certain dates. An online algorithm has to assign a target date to each request, specifying on which date the request should be processed (e.g., an appointment with a customer for a
washing machine repair). The cost at a target date is given by the downstream cost, the optimal cost of processing all requests
at that date w.r.t. some fixed downstream offline optimization problem (e.g., the cost of an optimal dispatch for service
technicians). We provide general competitive algorithms for the OnlineTDAP independently of the particular downstream problem,
when the overall objective is to minimize either the sum or the maximum of all downstream costs. As the first basic examples, we analyze the competitive ratios of our algorithms for the particular academic downstream problems of bin-packing, nonpreemptive scheduling on identical parallel machines, and routing a traveling salesman.
We consider a model for scheduling under uncertainty. In this model, we combine the main characteristics of online and stochastic scheduling in a simple and natural way. Job processing times are assumed to be stochastic, but in contrast to traditional stochastic scheduling models, we assume that jobs arrive online, and there is no knowledge about the jobs that will arrive in the future. The model incorporates both, stochastic scheduling and online scheduling
as a special case. The particular setting we consider is non-preemptive parallel machine scheduling, with the objective to
minimize the total weighted completion times of jobs. We analyze
simple, combinatorial online scheduling policies for that model, and
derive performance guarantees that match performance guarantees previously
known for stochastic and online parallel machine scheduling, respectively.
For processing times that follow NBUE distributions, we
improve upon previously best known performance bounds from
stochastic scheduling, even though we consider a more general
setting.
In this paper we discuss the stability and model order reduction of coupled linear
time-invariant systems. Sufficient conditions for a closed-loop system to be asymptotically stable are
given. We present a model reduction approach for coupled systems based on reducing the order of the
subsystems and coupling the reduced-order subsystems by the same interconnection matrices as for
the original model. Such an approach allows to obtain error bounds for the reduced-order closed-loop
system in terms of the errors in the reduced-order subsystems. Model reduction of coupled systems
with unstable subsystems is also considered. Numerical examples are given.
We present structure preserving algorithms for the numerical com-
putation of structured staircase forms of skew-symmetric/symmetric
matrix pencils along with the Kronecker indices of the associated skew-
symmetric/symmetric Kronecker-like canonical form. These methods
allow deflation of the singular structure and deflation of infinite eigenvalues with index greater than one. Two algorithms are proposed: one
for general skew-symmetric/symmetric pencils and one for pencils in
0
which the skew-symmetric matrix is a direct sum of 0 and J = −I I .
0
We show how to use the structured staircase form to solve boundary
value problems arising in control applications and present numerical
examples.
Classical results about the local existence and uniqueness of
DAE solutions are based on the derivative array [2] or on a geometrical
approach [13]. Thus these results can't be applied to equations with nonsmooth
coefficients. Also, sufficient conditions that guarantee solvability
are hard to check in general [6, 13]. In this paper a new approach to proving
local existence and uniqueness of DAE solutions is presented. The
main tool is a decoupling procedure that makes it possible to split DAE
solutions into their characteristic parts. Thus it is possible to weaken
the smoothness requirements considerably. In order for the decoupling
procedure to work we require a certain structural condition to hold. In
contrast to results already known, this condition can be easily verified.
We introduce FreeLence, a lossless single-rate connectivity compression algorithm for triangle surface meshes. Based upon a geometry-driven traversal scheme we present two novel and simple concepts: free-valence connectivity encoding and entropy coding based on geometric context. Together these techniques yield signicantly smaller rates for connectivity compression than current state of the art approaches - valence-based algorithms and Angle- Analyzer, with an average of 36% improvement over the former and an average of 18% over the latter on benchmark 3D models, combined with the ability to well adapt to the regularity of meshes. We also prove that our algorithm exhibits a smaller worst case entropy
for a class of ”well-behaved” triangle meshes than valence-driven connectivity encoding approaches.