Seth Pettie
Friday, March 3rd
3:30pm
WEH 7220
Low-distortion Graph Spanners
A spanner H of an undirected, unweighted graph G is a subgraph such that the distance between two points w.r.t. H is not too far from their distance in G, where “not too far” is captured by a distortion function f. Specifically, H is an f-spanner if dist_H(u,v) is at most f(dist_G(u,v)). Nearly all work on spanners and related structures considered only multiplicative distortion, and, in general, provided an undesirable tradeoff between the size of H and the coefficient of distortion.
The “holy grail” question in this area is whether there exist arbitrarily sparse spanners whose distortion is additive and constant. It was known that any graph has an additive 2-spanner with O(n^{3/2}) edges. In this talk I’ll present a completely new method for constructing spanners based on an economics-inspired view of the problem. The main result is an additive 6-spanner with O(n^{4/3}) edges. In addition, the technique leads to a spectrum of arbitrarily sparse spanners whose distortion is additive and sublinear in the distance being approximated.
One nice feature of Subversion is its automatic end-of-line conversion capability. Regardless of what’s in the repository, you can ensure that files in your local working copy use the native EOL style.
That is, if you have it set up properly. 
The trick is to use the properties feature of Subversion. For each file, Subversion allows us to attach a list of properties (key := value). Some properties have special meanings and svn:eol-style is the key that we are interested in today.
When the value of its key is set to native, Subversion will ensure that the file is in the native EOL style every time you update the file in your working copy. And when you check in the file, the conversion will happen automatically so that there are no accidents.
But isn’t it too tedious to have to setup this property for every file that you want automatic EOL conversion to apply? Well, this is when the Subversion local config file comes in.
The config file that I ask my fellows to use contains an auto-property section. Basically, Subversion allows us to automatically attach a property to files of any extension. For instance, to have all my TeX files to use native EOL:
*.tex = svn:eol-style=native
Lovely.
P.S. The auto properties are added when you add a file to version control. So, just replacing the config file will not affect the files that are already under version control. In that case, assuming you have the command line client, use
svn propset -R svn:eol-style native *.tex
to set the property on all TeX files (or other appropriate file types) in the current directory and its descendants.
