210 research outputs found
Stabilized branch-price-and-cut for the commodity-constrained split delivery vehicle routing problem
No full textIn the commodity-constrained split delivery vehicle routing problem (C-SDVRP), customer demands are composed of sets of different commodities. The C-SDVRP asks for a minimum-distance set of routes such that all customer demands are met and vehicle capacities are respected. Moreover, whenever a commodity is delivered by a vehicle to a customer, the entire amount requested by this customer must be provided. Different commodities demanded by one customer, however, can be delivered by different vehicles. Thus, the C-SDVRP is a relaxation of the capacitated vehicle routing problem and a restriction of the split delivery vehicle routing problem. For its exact solution, we propose a branch-price-and-cut algorithm that employs and tailors stabilization techniques that have been successfully applied to several cutting and packing problems. More precisely, we make use of (deep) dual-optimal inequalities which are particularly suited to reduce the negative effects caused by the inherent symmetry of C-SDVRP instances. One main issue here is the interaction Rc{between} branching and cutting decisions and the different classes of dual inequalities. Extensive computational tests on existing and extended benchmark instances show that all stabilized variants of our branch-price-and-cut are clearly superior to the non-stabilized version. On the existing benchmark, our algorithm is significantly faster than the state-of-the-art algorithm and provides several new optima for instances with up to 60 customers and 180 tasks. Lower bounds are reported for all tested instances with up to 80 customers and 480 tasks, improving the bounds for all unsolved instances and providing first lower bounds for several instances
ENCLOSING MANY BOXES BY AN OPTIMAL PAIR OF BOXES
No full textWe look at the problem: Given a set M of n d-dimensional intervals, find two d-dimensional intervals S, T, such that all intervals in M are enclosed by S or by T, the distribution is balanced and the intervals S and T fulfill a geometric criterion, e.g. like minimum area sum. Up to now no polynomial time algorithm was known for that problem. We present an O(dn log n + d2n2d-1) algorithm for finding an optimal solution
A branch-and-price framework for decomposing graphs into relaxed cliques
No full textWe study the family of problems of partitioning and covering a graph into/ with a minimum number of relaxed cliques. Relaxed cliques are subsets of vertices of a graph for which a clique-defining property—for example, the degree of the vertices, the distance between the vertices, the density of the edges, or the connectivity between the vertices—is relaxed. These graph partitioning and covering problems have important applications in many areas such as social network analysis, biology, and disease-spread prevention. We propose a unified framework based on branch-and-price techniques to compute optimal decompositions. For this purpose, new, effective pricing algorithms are developed, and new branching schemes are invented. In extensive computational studies, we compare several algorithmic designs, such as structure-preserving versus dichotomous branching, and their interplay with different pricing algorithms. The final chosen branch- and-price setup produces results that demonstrate the effectiveness of all components of the newly developed framework and the validity of our approach when applied to social network instances
A branch-and-price framework for decomposing graphs into relaxed cliques
No full textWe study the family of problems of partitioning and covering a graph into/ with a minimum number of relaxed cliques. Relaxed cliques are subsets of vertices of a graph for which a clique-defining property—for example, the degree of the vertices, the distance between the vertices, the density of the edges, or the connectivity between the vertices—is relaxed. These graph partitioning and covering problems have important applications in many areas such as social network analysis, biology, and disease-spread prevention. We propose a unified framework based on branch-and-price techniques to compute optimal decompositions. For this purpose, new, effective pricing algorithms are developed, and new branching schemes are invented. In extensive computational studies, we compare several algorithmic designs, such as structure-preserving versus dichotomous branching, and their interplay with different pricing algorithms. The final chosen branch- and-price setup produces results that demonstrate the effectiveness of all components of the newly developed framework and the validity of our approach when applied to social network instances
Photographic film and its interaction with light : detection of dust and scratches for image restoration
No full textA considerable portion of the cultural heritage of the last century is constituted by images impressed on photographic film, the majority of which are frames of motion picture films.
At present time, a large part of this heritage is at risk of being lost; this loss would break historical links, which are important for the economic, social and cultural development of future generations. The current ''digital revolution' has already produced drastic changes in image production technology, and 'classical photography' is disappearing; this leaves the field open for new powerful technical opportunities, but, at the same time, poses huge dilemmas for long-term archiving. The demise of classical photography is taking place in a precipitous and often ruinous way, causing several historied companies to go bankrupt.
Today's information society needs efficient and economic solutions for the digitization of this photographic heritage. The costs of the processes determine the amount of films that can be digitized, restored and made available to the community.
Research about digital movie restoration began around 1990, when it became possible to scan movie films in 2K resolution, thus providing high enough quality for the digitized images of a 35mm movie film. In recent years, several research projects about digital movie restoration have been undertaken. The research-project AURORA concentrated on the real-time restoration of image defects, which are typical for old videotapes; the main partners were the INA (Institut National d'Audiovisuelle, Paris), BBC-London and Snell & Wilcox, UK. PRESTO (Preservation Technology for European Archives) and the subsequent project PRESTOSPACE, within European Commission 6th Framework Programme for Research, provided technical solutions and integrated systems for a complete digital preservation of all kinds of audiovisual collections.
Audiovisual archiving is a complex and multi-disciplinary domain including such diverse fields as chemistry, physics, imaging technology, signal processing, robotics, artificial intelligence and semantic interpretation. These EU-projects bring together participants including archive owners, broadcasters, research centers from archive institutions, general research centers and universities, industries, and international non-profit institutions.
An important result of the movie restoration research is the development of new software: e.g. FRAME and its further development DIAMANT. Several early movies were reconstructed using DIAMANT, the most famous being Metropolis in 2001. LIMELIGHT was a software project that was further developed by the University of La Rochelle to become RETOUCHE.
In the period of 2010-2013, the Swiss National Science Foundation financed the project 'Dust BW: Detection of dust and scratches on photographic silver-halide (black/white) material by polarized dark-field illumination'. Partner of the project were the Imaging & Media Lab of the University of Basel and the Audiovisual Communications Laboratory School of the EPFL (École Polytechnique Fédérale de Lausanne). The present thesis reports the results of this research project.
Several factors are responsible for the deterioration of photographic material; we will only focus on dust and scratches. Different methods have been adopted up to now for the automatic detection of dust and scratches; each method has pros and cons, and a limited field of effectiveness. Infrared radiation (e.g. Digital ICE) and the spatio-temporal image analysis are among the most effective methods, although they have their limits. The infrared radiation only works for dye-based material and the spatio-temporal image analysis is not applicable for still images. The spatio-temporal image analysis is also limited due to motion in the scene and it is not effective for defects appearing in sequences spanning more than one frame (e.g. vertical scratches and lens dust). This thesis presents a comprehensive range of methods for optical flaw detection, applicable on any type of photographic film (both silver-based and dye-based material, as well as still images and moving images). It also presents innovative methods that combine different optical techniques and computational photography.
This thesis begins by describing the structure of a processed photographic film, analyzing its constitutive elements layer by layer. Afterwards, we will provide a list of the most common types of decay affecting the photographic film, classified on the basis of the layer that is primarily affected. This will be followed by a summary of the state-of-the-art strategies and solutions for the restoration of local flaws. The successive analysis of the interaction between light and photographic film provides the scientific framework needed to understand the optical phenomena involved in the experiments. The following chapter explains the phenomena and the techniques involved in imaging photographic film. A specific chapter surveys the optical methods available for flaw detection on any type of photographic transparency, including innovative solutions. The successive chapter defines the procedure we adopted for the numerical evaluation of the performances of the methods analyzed in the experiments. Prior to the conclusions, the thesis finally addresses the experimental analysis, identifying the best parameters for the proposed methods and comparing the innovative methods with the most effective traditional ones
Investigations on the Molecular Mechanisms of EGFR Signal Transactivation in Human Cancer
No full textGait, mobility, and falls in older people
No full textMy doctoral thesis contributes to the understanding of gait, mobility, and falls in older people. All
presented projects investigated the most prominent and sensitive markers for fall-related gait changes,
that is gait velocity and gait variability. Based on the measurement of these spatio-temporal gait
parameters, particularly when using a change-sensitive dual task paradigm, it is possible to make
conclusions regarding walking, balance, activities of daily living, and falls in older people. The
research summarized in my doctoral thesis will help in the detection of early fall risk and modulation of
therapeutic interventions to improve gait and consequently reduce fall risk in older people.
To identify modifiable fall risk factors, such as gait disorders, the GAITRite electronic walkway system
was used for objective spatio-temporal gait analysis. The simplicity and feasibility of the administration
of single and dual task gait analysis make it a desirable clinical and research measurement tool. Gait
analysis with walking as a single task condition alone is often insufficient to reveal underlying gait
disorders present during everyday activities. However, measuring gait with a dual task paradigm can
detect subtle gait deficits. Dual-tasking, walking while simultaneously performing an additional task,
was used to assess the effects of divided attention on motor performance and gait control.
The presented publications in this doctoral thesis investigated the association between gait
parameters and several hypothesized fall-related modalities: (a) Our first review article highlighted the
association between gait disorders and falls, and how related motor and cognitive impairments can be
detected by measuring gait while dual-tasking. (b) A second review looked at how the dual task
paradigm can be used for gait assessment in older people and how spatio-temporal gait parameters
are associated with increased fall risk. (c) Our systematic literature review provided evidence about
effective fall prevention interventions (exercise, home modifications, footwear, and walking aids) to
reduce the risk of falls in vulnerable older people. (d) To evaluate which exercise modalities are
effective in modifying risk factors for falls, we conducted an eight-week salsa intervention trial and
measured the effect of dancing on static and dynamic balance, and leg muscle power in older people.
(e) Besides exercise, inadequate nutritional intake is another modifiable risk factor for falls in older
people, and therefore our most recent cross-sectional study examined how serum 25-hydroxvitamin D
levels are associated with functional mobility in older people assessed in a memory clinic. (c) Walking
aids are commonly prescribed for older people with a high risk of falls which is why we examined the
influence of walking aids on spatio-temporal gait parameters in older people who used a cane, a
crutch or a walker. (g) Finally, besides predominantly investigating fall risk factors for motor abilities,
our prolonged and ongoing randomized, double-blind, and placebo-controlled intervention trial
explores the potential influence of ginkgo biloba on the cognitive domain relevant for dual-tasking in
older people with mild cognitive impairment
An Optimal Algorithm for Approximating a Set of Rectangles by Two Minimum Area Rectangles
No full textExperience with lightweight distributed component technologies in Business Intelligence systems
No full textEnclosing a set of objects by two minimum area rectangles
No full textIn this paper, we face the problem of computing an enclosing pair of axis-parallel rectangles of a set of polygonal objects in the plane, serving as a simple container. We propose an O(n alpha(n)log n) worst-case time algorithm, where alpha() is the inverse Ackermann's function, for finding, given a set M of points, segments and polygons defined by n vertices, a pair of axis-parallel rectangles (s,t) such that s boolean OR t encloses all objects in M and area(s) + area(t) is minimum. The algorithm works in O(n alpha (n) log log n) worst-case space. Moreover, we prove an Omega(n log n) lower bound for the one-dimensional version of the problem. We also show that for the special case of enclosing a set of polygons with axis-parallel sides, our algorithm runs in optimal worst-case time O(n log n), using worst-case space O(n log log n). (C) 1996 Academic Press, Inc
- …
