DIMACS/CCICADA Interdisciplinary Seminar Series Presents Two Seminars - Monday, March 21, 2011 and Thursday, March 24, 2011 ***************************************************************** ***Monday, March 21, 2011*** Title: The Large Scale Curvature of Networks and its Implications for Network Management and Security Speaker: Iraj Saniee, Bell Laboratories, Alcatel-Lucent Date: Monday, March 21, 2011 12:00 - 1:00 pm Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ ************************************************************ Abstract: Understanding key structural properties of large-scale networks is critical for analyzing and optimizing their performance, improving their reliability and security. In this talk we show that these networks may possess a previously unnoticed feature, global curvature, which we argue has a critical impact on core congestion: the load at the core of a network with N nodes scales as O(N^2) as compared to O(N^1.5) for a flat network. We substantiate this claim through analysis of a collection of IP-layer data networks across the globe as measured and documented by previous researchers. We further show that the observed scaling is intrinsic to the geometry and metric properties of these networks with clear implications for network management and security. We conclude with a preliminary classification of large-scale networks that we believe better describes the structure of complex networks than those currently used within the research community. This is joint work with Onuttom Narayan, University of California, Santa Cruz. ***************************************************************** ***Thursday, March 24, 2011 ** Please note special day and time*** Title: Some heuristics for the binary paint shop problem and their expected number of colour changes Speaker: Winfried Hochstaettler, University of Hagen, Germany Date: **Thursday, March 24, 2011 1:00 - 2:00 pm** Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ Abstract: In the binary paint shop problem we are given a word on $n$ characters of length $2n$ where every character occurs exactly twice. The objective is to colour the letters of the word in two colours, such that each character receives both colours and the number of colour changes of consecutive letters is minimized. Amini et.\ al proved that the expected number of colour changes of the heuristic greedy colouring is at most $2n/3$. They also conjectured that the true value is $n/2$. We verify their conjecture and, furthermore, compute an expected number of $2n/3$ colour changes for a heuristic, named first, which behaves well on some worst case examples for the greedy algorithm. >From our proof method, finally, we derive a new recursive greedy heuristichich achieves an average number of $2n/5$ colour changes.