<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:st1="urn:schemas-microsoft-com:office:smarttags" xmlns="http://www.w3.org/TR/REC-html40">
<head>
<meta http-equiv=Content-Type content="text/html; charset=us-ascii">
<meta name=ProgId content=Word.Document>
<meta name=Generator content="Microsoft Word 11">
<meta name=Originator content="Microsoft Word 11">
<link rel=File-List href="cid:filelist.xml@01C7914A.2F06CA10">
<o:SmartTagType namespaceuri="urn:schemas-microsoft-com:office:smarttags"
name="City"/>
<o:SmartTagType namespaceuri="urn:schemas-microsoft-com:office:smarttags"
name="place"/>
<!--[if gte mso 9]><xml>
<o:OfficeDocumentSettings>
<o:DoNotRelyOnCSS/>
</o:OfficeDocumentSettings>
</xml><![endif]--><!--[if gte mso 9]><xml>
<w:WordDocument>
<w:SpellingState>Clean</w:SpellingState>
<w:GrammarState>Clean</w:GrammarState>
<w:DocumentKind>DocumentEmail</w:DocumentKind>
<w:EnvelopeVis/>
<w:ValidateAgainstSchemas/>
<w:SaveIfXMLInvalid>false</w:SaveIfXMLInvalid>
<w:IgnoreMixedContent>false</w:IgnoreMixedContent>
<w:AlwaysShowPlaceholderText>false</w:AlwaysShowPlaceholderText>
<w:Compatibility>
<w:BreakWrappedTables/>
<w:SnapToGridInCell/>
<w:WrapTextWithPunct/>
<w:UseAsianBreakRules/>
<w:UseWord2002TableStyleRules/>
<w:UseFELayout/>
</w:Compatibility>
<w:BrowserLevel>MicrosoftInternetExplorer4</w:BrowserLevel>
</w:WordDocument>
</xml><![endif]--><!--[if gte mso 9]><xml>
<w:LatentStyles DefLockedState="false" LatentStyleCount="156">
</w:LatentStyles>
</xml><![endif]--><!--[if !mso]>
<style>
st1\:*{behavior:url(#default#ieooui) }
</style>
<![endif]-->
<style>
<!--
/* Font Definitions */
@font-face
{font-family:SimSun;
panose-1:2 1 6 0 3 1 1 1 1 1;
mso-font-alt:\5B8B\4F53;
mso-font-charset:134;
mso-generic-font-family:auto;
mso-font-pitch:variable;
mso-font-signature:3 135135232 16 0 262145 0;}
@font-face
{font-family:"\@SimSun";
panose-1:2 1 6 0 3 1 1 1 1 1;
mso-font-charset:134;
mso-generic-font-family:auto;
mso-font-pitch:variable;
mso-font-signature:3 135135232 16 0 262145 0;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{mso-style-parent:"";
margin:0pt;
margin-bottom:.0001pt;
mso-pagination:widow-orphan;
font-size:12.0pt;
font-family:"Times New Roman";
mso-fareast-font-family:SimSun;
mso-fareast-language:ZH-CN;}
a:link, span.MsoHyperlink
{color:blue;
text-decoration:underline;
text-underline:single;}
a:visited, span.MsoHyperlinkFollowed
{color:purple;
text-decoration:underline;
text-underline:single;}
p.MsoAutoSig, li.MsoAutoSig, div.MsoAutoSig
{margin:0pt;
margin-bottom:.0001pt;
mso-pagination:widow-orphan;
font-size:12.0pt;
font-family:"Times New Roman";
mso-fareast-font-family:"Times New Roman";}
span.EmailStyle17
{mso-style-type:personal-compose;
mso-style-noshow:yes;
mso-ansi-font-size:10.0pt;
mso-bidi-font-size:10.0pt;
font-family:Arial;
mso-ascii-font-family:Arial;
mso-hansi-font-family:Arial;
mso-bidi-font-family:Arial;
color:windowtext;}
span.SpellE
{mso-style-name:"";
mso-spl-e:yes;}
span.GramE
{mso-style-name:"";
mso-gram-e:yes;}
@page Section1
{size:612.0pt 792.0pt;
margin:72.0pt 90.0pt 72.0pt 90.0pt;
mso-header-margin:36.0pt;
mso-footer-margin:36.0pt;
mso-paper-source:0;}
div.Section1
{page:Section1;}
-->
</style>
<!--[if gte mso 10]>
<style>
/* Style Definitions */
table.MsoNormalTable
{mso-style-name:"Table Normal";
mso-tstyle-rowband-size:0;
mso-tstyle-colband-size:0;
mso-style-noshow:yes;
mso-style-parent:"";
mso-padding-alt:0pt 5.4pt 0pt 5.4pt;
mso-para-margin:0pt;
mso-para-margin-bottom:.0001pt;
mso-pagination:widow-orphan;
font-size:10.0pt;
font-family:"Times New Roman";
mso-ansi-language:#0400;
mso-fareast-language:#0400;
mso-bidi-language:#0400;}
</style>
<![endif]--><!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="2050" />
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1" />
</o:shapelayout></xml><![endif]-->
</head>
<body lang=EN-US link=blue vlink=purple style='tab-interval:36.0pt'>
<div class=Section1>
<p class=MsoNormal><font size=2 face=Arial><span style='font-size:10.0pt;
font-family:Arial'><o:p> </o:p></span></font></p>
<p class=MsoNormal><font size=2 face=Arial><span style='font-size:10.0pt;
font-family:Arial'>Guest Speaker<o:p></o:p></span></font></p>
<p class=MsoNormal><font size=2 face=Arial><span style='font-size:10.0pt;
font-family:Arial'><o:p> </o:p></span></font></p>
<p class=MsoNormal><font size=2 face=Arial><span style='font-size:10.0pt;
font-family:Arial'>Presented by: <st1:City w:st="on">Toyota</st1:City>
Technological Institute at <st1:City w:st="on"><st1:place w:st="on">Chicago</st1:place></st1:City><o:p></o:p></span></font></p>
<p class=MsoNormal><b style='mso-bidi-font-weight:normal'><font size=2
face=Arial><span style='font-size:10.0pt;font-family:Arial;font-weight:bold;
mso-bidi-font-weight:normal'><o:p> </o:p></span></font></b></p>
<p class=MsoNormal><b style='mso-bidi-font-weight:normal'><font size=2
face=Arial><span style='font-size:10.0pt;font-family:Arial;font-weight:bold;
mso-bidi-font-weight:normal'>Speaker: Hubert Chan<o:p></o:p></span></font></b></p>
<p class=MsoNormal><font size=2 face=Arial><span style='font-size:10.0pt;
font-family:Arial'>Speaker’s home page: <a
href="http://www.cs.uwaterloo.ca/~hy3chan">http://www.cs.uwaterloo.ca/~hy3chan</a>
<o:p></o:p></span></font></p>
<p class=MsoNormal><font size=2 face=Arial><span style='font-size:10.0pt;
font-family:Arial'><o:p> </o:p></span></font></p>
<p class=MsoNormal><b style='mso-bidi-font-weight:normal'><font size=2
face=Arial><span style='font-size:10.0pt;font-family:Arial;font-weight:bold;
mso-bidi-font-weight:normal'>Date: Tuesday, May 08, 2007<o:p></o:p></span></font></b></p>
<p class=MsoNormal><b style='mso-bidi-font-weight:normal'><font size=2
face=Arial><span style='font-size:10.0pt;font-family:Arial;font-weight:bold;
mso-bidi-font-weight:normal'>Time: 12:00 <o:p></o:p></span></font></b></p>
<p class=MsoNormal><font size=2 face=Arial><span style='font-size:10.0pt;
font-family:Arial'>Location: TTI-C Conference room<o:p></o:p></span></font></p>
<p class=MsoNormal><font size=2 face=Arial><span style='font-size:10.0pt;
font-family:Arial'><o:p> </o:p></span></font></p>
<p class=MsoNormal><font size=2 face=Arial><span style='font-size:10.0pt;
font-family:Arial'><o:p> </o:p></span></font></p>
<p class=MsoNormal><b style='mso-bidi-font-weight:normal'><font size=2
face=Arial><span style='font-size:10.0pt;font-family:Arial;font-weight:bold;
mso-bidi-font-weight:normal'>Title:</span></font></b><font size=2 face=Arial><span
style='font-size:10.0pt;font-family:Arial'> Notions of Metric Dimension<o:p></o:p></span></font></p>
<p class=MsoNormal><font size=2 face=Arial><span style='font-size:10.0pt;
font-family:Arial'><o:p> </o:p></span></font></p>
<p class=MsoNormal><b style='mso-bidi-font-weight:normal'><font size=2
face=Arial><span style='font-size:10.0pt;font-family:Arial;font-weight:bold;
mso-bidi-font-weight:normal'>Abstract:<o:p></o:p></span></font></b></p>
<p class=MsoNormal><font size=2 face=Arial><span style='font-size:10.0pt;
font-family:Arial'><o:p> </o:p></span></font></p>
<p class=MsoNormal><font size=2 face=Arial><span style='font-size:10.0pt;
font-family:Arial'>The study of finite metrics is an important area of
research, because of its wide applications to many different problems.<span
style='mso-spacerun:yes'> </span>Hence, it is desirable to know what
metrics admit better algorithms.<span style='mso-spacerun:yes'>
</span>Many NP-hard problems become more tractable for low-dimensional
Euclidean metrics.<o:p></o:p></span></font></p>
<p class=MsoNormal><font size=2 face=Arial><span style='font-size:10.0pt;
font-family:Arial'>However, the notion of Euclidean dimension <span
class=GramE>cannot be applied</span> to general metrics.<span
style='mso-spacerun:yes'> </span>Clearly, a better notion of dimension <span
class=GramE>should be used</span> to characterize the complexity of a general
metric space.<o:p></o:p></span></font></p>
<p class=MsoNormal><font size=2 face=Arial><span style='font-size:10.0pt;
font-family:Arial'><o:p> </o:p></span></font></p>
<p class=MsoNormal><font size=2 face=Arial><span style='font-size:10.0pt;
font-family:Arial'>One such notion is the doubling dimension, which is popular
among the theory community.<span style='mso-spacerun:yes'> </span>Many
efficient algorithms for problems on low-dimensional Euclidean space have
counterparts for metrics with low<o:p></o:p></span></font></p>
<p class=MsoNormal><span class=GramE><font size=2 face=Arial><span
style='font-size:10.0pt;font-family:Arial'>doubling dimension.</span></font></span><font
size=2 face=Arial><span style='font-size:10.0pt;font-family:Arial'><span
style='mso-spacerun:yes'> </span>Sparse spanners <span class=GramE>are
well studied</span> for Euclidean<o:p></o:p></span></font></p>
<p class=MsoNormal><font size=2 face=Arial><span style='font-size:10.0pt;
font-family:Arial'>metrics and we extend the framework to doubling
metrics.<span style='mso-spacerun:yes'> </span>For instance, we construct
linear sized (1 + \eps)-spanners for doubling metrics.<o:p></o:p></span></font></p>
<p class=MsoNormal><font size=2 face=Arial><span style='font-size:10.0pt;
font-family:Arial'><o:p> </o:p></span></font></p>
<p class=MsoNormal><font size=2 face=Arial><span style='font-size:10.0pt;
font-family:Arial'>Observe that doubling dimension imposes a restriction on the
local growth rate everywhere in a metric.<span style='mso-spacerun:yes'>
</span>Therefore, an otherwise simple metric with a small locally complex
region would have high doubling dimension.<span style='mso-spacerun:yes'>
</span>We investigate a new notion of metric dimension that captures the global
behavior of a metric.<span style='mso-spacerun:yes'> </span>For metrics
with low global dimension, one would expect better guarantees for problems whose
objectives depend globally on the input metrics.<span
style='mso-spacerun:yes'> </span>Indeed, for the Traveling Salesman
Problem on such metrics, we give a sub-exponential time algorithm with
approximation ratio arbitrarily close to <span class=GramE>1</span>.<o:p></o:p></span></font></p>
<p class=MsoNormal><font size=2 face=Arial><span style='font-size:10.0pt;
font-family:Arial'><o:p> </o:p></span></font></p>
<p class=MsoNormal><span class=GramE><font size=2 face=Arial><span
style='font-size:10.0pt;font-family:Arial'>If you have any questions or would
like to meet the speaker,</span></font></span><font size=2 face=Arial><span
style='font-size:10.0pt;font-family:Arial'> please contact Ponda Barnes at <a
href="mailto:pondabarnes@tti-c.org">pondabarnes@tti-c.org</a><o:p></o:p></span></font></p>
<p class=MsoNormal><font size=2 face=Arial><span style='font-size:10.0pt;
font-family:Arial'>For future TTI-C talks and events please go to <a
href="http://ttic.uchicago.edu/cal/month.php">http://ttic.uchicago.edu/cal/month.php</a><o:p></o:p></span></font></p>
<p class=MsoNormal><font size=2 face=Arial><span style='font-size:10.0pt;
font-family:Arial'><o:p> </o:p></span></font></p>
<p class=MsoNormal><font size=2 face=Arial><span style='font-size:10.0pt;
font-family:Arial'><o:p> </o:p></span></font></p>
<p class=MsoNormal><font size=2 face=Arial><span style='font-size:10.0pt;
font-family:Arial'><o:p> </o:p></span></font></p>
<p class=MsoNormal><font size=2 face=Arial><span style='font-size:10.0pt;
font-family:Arial'><o:p> </o:p></span></font></p>
<p class=MsoNormal><font size=3 face="Times New Roman"><span style='font-size:
12.0pt'><o:p> </o:p></span></font></p>
</div>
</body>
</html>