COST293  Graphs and algorithms in communication networks		ADONET  Algorithmic Discrete Optimization Network

Kamal Jain is a researcher in Microsoft Research. He has a doctorate degree from Georgia Institute of Technology. In his research carrier he has won several awards of excellence including the Optimization Prize. He has written research articles in several different areas of Computer Science, Electrical Engineering and Economics. Most notables of them are the algorithms for Networking problems, Facility Location problems, Network Coding problems and Cost sharing problems. Recently he has been working on auctions. For more information please visit his somewhat outdated webpage, http://www.cc.gatech.edu/~kjain.

Tibor Jordán received the PhD degree in mathematics from the Hungarian Academy of Sciences in 1995. He had visiting positions at CWI, Amsterdam, Odense University, and at BRICS, University of Aarhus. In 2000 he joined the Department of Operations Research, Eötvös University, where he is presently an Associate Professor.

His research interests include combinatorial optimization, graph algorithms, graph theory, network connectivity, matroid theory, and combinatorial rigidity.

Dr Radzik obtained PhD in Computer Science from Stanford University in 1992, and has been at the Department of Computer Science, King's College London, since 1993. His main research area is Design and Analysis of Algorithms. His research contributions include analysis of algorithms for various network optimization problems, design of parallel algorithms, design and analysis of data structures for dynamic graph problems, and analysis of some global optimization methods. He has recently worked on design of communication algorithms for ad-hoc radio networks and on algorithms for exploration of networks with mobile agents. He investigates theoretical aspects of algorithms as well as their practical performance.

Studies in Freiburg and Bonn, PhD January 1997, University of Bonn. Full Professor since April 2003. Research focuses on Combinatorial Optimization and VLSI Design. Head of a long-term project on Discrete Mathematics and Applications with the Northrhine-Westphalian Academy of Sciences since October 2004. Long-term industrial cooperation with IBM and Magma Design Automation on VLSI Design (managed jointly with Bernhard Korte). Author of approximately 50 scientific papers, and of the book "Combinatorial Optimization: Theory and Algorithms" (jointly with Bernhard Korte) with three English and one Japanese edition. Member of three editorial boards of scientific journals and eight program committees of international conferences.

See my homepage for further information.

Lajos Hanzo received his first-class Master degree in electronics in 1976, his PhD in 1983 and his Doctor of Sciences (DSc) degree in 2004. He is a Fellow of the Royal Academy of Engineering (FREng). During his career in telecommunications he has held various research and academic posts in Hungary, Germany and the UK. Since 1986 he has been with the School of ECS, University of Southampton, UK, where holds the Chair in Telecommunications.

He co-authored 12 books totalling 9000 pages on mobile radio communications, published in excess of 600 research papers (http://www-mobile.ecs.soton.ac.uk), organised and chaired IEEE/IEE conferences, such as WCNC’06, ISSSTA’06 and the IEE 3G and Beyond conference, presented keynote lectures and has been awarded a number of distinctions. Currently he heads an academic research team, working on a range of research projects in the field of wireless multimedia communications sponsored by industry, the Engineering and Physical Sciences Research Council (EPSRC) UK, the European IST Programme and the Mobile Virtual Centre of Excellence (VCE), UK. He is an enthusiastic supporter of industrial and academic liaison and he offers a range of industrial courses. Lajos is also an IEEE Distinguished Lecturer of both the IEEE Communications as well as the Vehicular Technology Society and a Fellow of both the IEE and IEEE. For further information on research in progress and associated publications please refer to http://wwwmobile.ecs.soton.ac.uk

Emilio Leonardi was born in Cosenza, Italy, in 1967. He received a Dr.Ing degree in Electronics Engineering in 1991 and a Ph.D. in Telecommunications Engineering in 1995 both from Politecnico di Torino.

He is currently an Associate Professor at the Dipartimento di Elettronica of Politecnico di Torino.

In 1995, he visited the Computer Science Department of the University of California, Los Angeles (UCLA), in summer 1999 he joined the High Speed Networks Research Group, at Bell Laboratories/Lucent Technologies, Holmdel (NJ); in summer 2001, the Electrical Engineering Department of the Stanford University and finally in summer 2003, the IP Group at Sprint, Advanced Technologies Laboratories, Burlingame CA.

He participated in several national and european projects such as IST-SONATA and IST-DAVID amd the NoE e-Photon-One . He is also involved in several consulting and research project with private industries, including Lucent Technologies-Bell Labs., IBM, British Telecom, Alcatel and TILAB.

He has co-authored over 150 papers published in international journals and presented in leading international conferences, all of them in the area of telecommunication networks. He received the IEEE TCGN best paper award for paper presented at at the IEEE Globecom 2002, "High Speed Networks Symposium".

He participated to the program committees of several conferences including: IEEE infocom, IEEE Globecom and IEEE ICC. He was guest editor of two special issues of IEEE Journal of Selected Areas of Communications focused on high speed switches and routers.

His research interests are in the field of: performance evaluation of communication networks, all-optical networks, queueing theory, packet switching.

Michał Pióro is a full professor at the Faculty of Electronics and Information Technology at Warsaw University of Technology, Poland, where he heads the Department of Computer Net-works and Switching at the Institute of Telecommunications. He is also a full professor at the Department of Communication Systems at Lund University, Sweden. He received a PhD degree and a DSc degree in 1979 and 1990, respectively, both from Warsaw University of Technology. In 2002 he received a Polish State Professorship, the highest scientific title in Poland. His research interests concentrate on modeling, design, optimization, and perfor-mance analysis of telecommunication networks and systems. He has lead many research projects for telecom industry in this field. Prof. Pióro is an author of four books (including M.Pióro and D.Medhi: Routing, Flow and Capacity Design in Communication and Computer Networks, Morgan Kaufmann Publishers - Elsevier, 770 pages, 2004), and around 100 papers presented in international telecom and OR journals and conference proceedings. He is a member of the program committees of many international conferences and a technical editor of IEEE Communications Magazine. He is deeply involved in European research, including the EU 6th Framework Project.

Arun K. Somani is currently Jerry R. Junkins Endowed Chair Professor of Electrical and Computer Engineering at Iowa State University. He earned his MSEE and PhD degrees in electrical engineering from the McGill University, Montreal, Canada, in 1983 and 1985, respectively. He worked as Scientific Officer for Govt. of India, New Delhi from 1974 to 1982. He was a faculty member at the University of Washington, Seattle, WA from 1985 to 1997.

Professor Somani's research interests are in the area of fault tolerant computing, computer interconnection networks, WDM-based optical fiber networking, parallel computer system, and reconfigurable architecture including FPGA-based hardware components. He has published more than 250 technical papers, several book chapters, a book, and has supervised more than 60 MS and more than 25 PhD students.

He was the chief architect of an anti-submarine warfare system (developed for Indian navy), Meshkin fault-tolerant computer system architecture (developed for the Boeing Company), several robust interconnection topologies, and Proteus multicomputer system. A 46-node prototype of Proteus system supporting a large grain message-passing system with separate data and control planes was implemented at University of Washington.

He has served on several program committees of various conferences. He has served as the General Chair of IEEE Fault Tolerant Computing Symposium 1997 and BroadNets 2005; Technical Program Committee Chair of International Conference on Computer Communications and Networks, 1999, and OPTICOMM 2003; and Tutorial Chair of ICC 1995 and FTCS 1999. He has served as IEEE distinguished visitor and IEEE distinguished tutorial speaker. He has given several key note speeches, tutorials and distinguished and invited talks all over the world. He has been elected a Fellow of IEEE for his contributions to theory and applications of computer networks

Shortest path and minimum spanning tree are among the simplest network design problems. Both of them have been mostly understood. There are multiple polynomial time algorithms to solve them. A common generalization of both these problems is Steiner tree. This is NP-hard. Further generalizations are Steiner forest and Steiner network. All of these problems exhibit factor 2 approximation algorithm, except the Steiner tree for which even better approximation algorithms are known.

These problems have been tackled with two basic techniques in linear programming based approximation algorithm. The first is the primal-dual schema. And the other is the rounding schema. We should be spending roughly equal time in studying both these schemas.

Problems of selecting the best location for facilities in a given network that satisfy a certain property are called location problems. Consider, for example, a multimedia network where we wish to locate a set of `source vertices' which can offer several types of services for the `users', i.e. for the remaining vertices in the network. In this setting it is natural to require a sufficiently high flow-amount (or edge-connectivity) between the set of sources and each of the users in the network.

Another type of location problem occurs in localization problems of sensor networks. In such a network the fundamental problem is to determine the locations of the sensors from a subset of pairwise distances and the exact location of a set of special sensors, which are called the `anchor vertices' of the network. A related location problem is how to minimize the number of anchors in order to achieve unique localizability for arbitrary distance data.

We shall investigate the algorithmic questions arising in location problems with connectivity or localizability conditions and show how to obtain optimal solutions for some versions by employing various methods of combinatorial optimization.

We will study various combinatorial optimization problems that arise in VLSI design. We concentrate on placement, routing, and repeater tree design. The combaintorial optimization problems that we encounter include minimum cost flows, shortest paths, Steiner trees, multicommodity flows, minimum mean cycles, facility location and network design.

With the advent of fiber optic transmission systems and Wavelength Division Multiplexing, the amount of information that can be carried over a single fiber is soaring. With increasing deployment of fibers in networks, the risk of losing large volumes of traffic due to a link failure has also increased tremendously. Failure recovery is a challenging issue in the mesh network topologies. There are different tradeoffs between ring and mesh restoration. An important element of the architecture is how much recovery to plan. Another important problem in optical fiber networks with wavelength division multiplexing is that of traffic grooming. The capacity of a single wavelength channel has been increasing constantly reaching at the level of 10 to 40 GHz/channel. At the same time individual user requirements are not increasing at the same rate although the overall number of users and applications are increasingly dramatically. Thus, it is important to accommodate all the applications while utilizing the resources efficiently. Traffic grooming is a technique for multiplexing different sub-wavelength capacity traffic requirements on a single wavelength so that the wavelength and hence the capacity requirements of the whole network is minimized. We provide a brief overview of trends and technologies for survivable network design and restoration architectures in mesh optical networks and traffic grooming.

Next we raise a question. Should the traffic be still be maintained the way we do now. We will pose some future research problems that may management of traffic simpler.

András Frank received the PhD degree in 1976, and became Doctor of the Hungarian Academy of Sciences in 1990. He is Professor at Eötvös Loránd University since 1991. From 1990 to 1993 he was visiting professor at Bonn University. He had visiting positions in Bonn, Waterloo, Grenoble, and Lausanne. His main research interests are matroid theory, submodular functions, graph theory, and polynomial algorithms in combinatorial optimization.