The process of implementing, debugging, testing, engineering, and experimentally analyzing algorithmic
codes is a complex and delicate task, fraught with many difficulties and pitfalls. Algorithm
visualization environments provide tools for abstracting irrelevant program details and for
conveying the high-level algorithmic behavior of a piece of software into still or animated images.
In this talk I will discuss some aspects of visualization as a tool in algorithm engineering. I will
survey the main approaches and discuss difficulties and relevant examples where visualization
systems have helped developers gain insights about algorithms, test implementation weaknesses,
and tune suitable heuristics for improving the practical performances of algorithmic codes.
(Part of this talk is based on joint work with Irene Finocchi, Guiseppe F. Italiano, and Stefan
Näher.)
|
Camil Demetrescu received his Ph.D. in Computer Engineering in 2001
from the University of Rome "La Sapienza", and his dissertation was
awarded the 2002 EATCS Italian Chapter Prize for the best two Ph.D.
Theses in Theoretical Computer Science. He has been visiting
scientist at the AT&T Research Laboratories (Florham Park, NJ, USA),
joining the Networks Group, and at the Theory Group of the IT
University of Copenhagen. He has been consultant at Microsoft
Research - Silicon Valley. He is currently Assistant Professor in
Computer Science at the University of Rome "La Sapienza". His
research interests include graph algorithms, data structures,
algorithm engineering, and software systems. His scientific results
appeared in prestigious venues such as Journal of the ACM, IEEE
Symposium on Foundations of Computer Science, and ACM Symposium on
Theory of Computing. He has organized several scientific events,
including the 45th IEEE Symposium on Foundations of Computer Science
and the 9th DIMACS Implementation Challenge. He is continuously
invited to serve as program committee member or program committee
chair of international scientific meetings.
|
In the classical 1-dimensional packing problem, we are given a
list of items with sizes between 0 and 1, and asked to pack them into a
minimum number of unit-capacity bins.
This was one of the first NP-Hard problems to be studied from the
``approximation algorithm'' point of view, and has been the source of
many surprising results about the average case behavior of such algorithms.
Many of these surprises were first revealed by experimentation, which
led to conjectures and then to proofs. In this talk I will
survey these results, and also highlight some as-yet-unproved
conjectures suggested by the experimental data.
|
David S. Johnson is the Head of the Algorithms and Optimization Department at AT & T Labs - Research in Florham Park, NJ, and has been a researcher
at the Labs (in its many incarnations) since 1973, when he received his
PhD from MIT. The author of over 100 technical papers, he is perhaps
best known as the co-author of COMPUTERS AND INTRACTABILITY: A GUIDE TO
THE THEORY OF NP-COMPLETENESS, for which he shared the Lanchester Prize
of the Operations Research Society of America in 1979, His research
interests (in addition to the theory of NP-Completeness) include
approximation algorithms for combinatorial problems, a subject on which
he had several of the first key papers, starting with his PhD thesis on
the bin packing problem. His involvemenet in experimental analysis of
algorithms began in 1983, inspired by his skepticism about the then-new
idea of ``simulated annealing.'' He has taken a lead in encouraging
better-quality experimental research, and is the founder and coordinator
of the ongoing series of DIMACS Implementation Callenges.
|
In this talk we apply metaheuristics-based heuristics to find optimal
or near-optimal solutions to two network design problems. The first
problem arises in local access network design, where we want to balance
the potential revenue that can be obtained by providing service to
customers and the cost to build the network. The second problem deals
with IP networks where the OSPF, or Open Shortest Path First, protocol
is used for routing. Given a network topology (routers and arcs where
capacity can be deployed), a set of link types to be deployed, each
having a different capacity and cost, and predicted traffic demands,
the problem is to find a set of OSPF weights and determine the types and
numbers of links to be deployed such that network cost is minimized
subject to single arc, node, or span failures.
To solve the first problem, we propose a hybrid GRASP with perturbations
that uses path-relinking for search intensification and a variable
neighborhood search in a post-optimization phase. Computational results
show the good quality of the solutions found. To solve the second
problem, we propose a random-keys genetic algorithm that assigns OSPF
weights and an optimal composite-link assignment algorithm.
|
Mauricio G. C. Resende is a researcher at the Algorithms and Optimization
Research Department at the AT&T Shannon Laboratory of AT&T Labs
Research. His undergraduate studies were in electrical engineering
(systems concentration) at the Catholic University of Rio de Janeiro
(PUC-Rio), Brazil and he earned a M.Sc. in operations research at the
Georgia Institute of Technology. He has been at AT&T Bell Labs and
AT&T Labs Research since 1987, when he earned his Ph.D. in operations
research at the University of California, Berkeley. His research has
concentrated on experimental analysis of optimization algorithms,
including interior point algorithms for linear programming, network
optimization, and nonlinear programming, as well as heuristics for
discrete optimization problems. A large part of his work with heuristics
has focused on GRASP (greedy randomized adaptive search procedures),
a metaheuristic that he and Thomas A. Feo developed in the late 1980s.
He has published over 100 papers and is co-editor of several books,
including the Handbook of Optimization in Telecommunications and the
Handbook of Applied Optimization. He is on the editorial boards of
several journals, including Networks, Journal of Heuristics, Journal of
Global Optimization, and Computational Optimization and Applications.
Besides working in the telecommunications industry, he has worked in
the electrical power and semiconductor manufacturing industries, where
he developed several decision support systems (tools) for optimization
problems.
|
