[CCICADA-announce] DIMACS/CCICADA Interdisciplinary Seminar Series - Two Seminars

[Linda Casals]

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.