-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathindex.html
More file actions
executable file
·1103 lines (957 loc) · 51.1 KB
/
index.html
File metadata and controls
executable file
·1103 lines (957 loc) · 51.1 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<html>
<head>
<title>Ulrich Bauer</title>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<meta name="description" content="Prof. Dr. Ulrich Bauer, Professor for Applied and Computational Topology, Deptartment of Mathematics, TUM)">
<meta name="author" content="Ulrich Bauer">
<meta name="robots" content="follow">
<link href="stylesheets/styles.css" rel="stylesheet" type="text/css" id="style_1">
<!-- Google Analytics -->
<script async src="https://www.googletagmanager.com/gtag/js?id=G-JKS0Q38RBY"></script>
<script>
window.dataLayer = window.dataLayer || [];
function gtag(){dataLayer.push(arguments);}
gtag('js', new Date());
gtag('config', 'G-JKS0Q38RBY');
</script>
<!-- End Google Analytics -->
</head>
<body>
<div id="rumpf">
<div id="contentwrapper">
<div id="rechtespalte">
<div class="innen_content">
<br>
<font class="ueberschrift">Ulrich Bauer</font><br><br>
<p>
I am an associate professor (W3) in the
<a HREF="http://www.ma.tum.de">department of mathematics</a>
at the
<a HREF="http://www.tum.de">Technical University of Munich (TUM)</a>,
leading the
<a HREF="https://geo.ma.tum.de/en/research/computational-topology.html">Applied & Computational Topology</a>
group.
My research revolves around application-motivated concepts and computational methods
in topology and geometry, popularized by application areas such as topological data analysis.
Some of my key research areas are persistent homology, discrete Morse theory, and geometric complexes.
My research is supported by funding from DFG (Collaborative Research Center <a href="https://www.discretization.de">Discretization in Geometry and Dynamics</a>) and <a href="https://www.mdsi.tum.de">MDSI (Munich Data Science Institute)</a>.
</p>
<br/>
<p>
I am the author of
<a HREF="http://ripser.org">Ripser</a>,
a leading software for the computation of Vietoris–Rips persistence barcodes.
</p>
<br/>
<p>
I am an editor of <a HREF="https://www.springer.com/journal/10208"> Foundations of Computational Mathematics</a>, the <a HREF="https://www.springer.com/journal/41468">Journal of Applied and Computational Topology</a>, and the <a HREF="https://epubs.siam.org/journal/sjaabq">SIAM Journal on Applied Algebra and Geometry</a>.
I am a core member of the <a href="https://www.mdsi.tum.de">MDSI (Munich Data Science Institute)</a> and a principal investigator of the <a href="https://www.mcml.ai">MCML (Munich Center for Machine Learning)</a>
I serve on the executive board of the DFG Collaborative Research Center <a HREF="https://www.discretization.de">Discretization in Geometry & Dynamics</a>, and on the advisory board of the EPSRC <a HREF="https://www.maths.ox.ac.uk/groups/topological-data-analysis">Centre for Topological Data Analysis</a>.
</p>
<br/>
<p>
I obtained my PhD with Max Wardetzky in the research group <a href="http://ddg.math.uni-goettingen.de/">
Discrete Differential Geometry</a> at the University of Göttingen, and worked a postdoc in <a href="http://pub.ist.ac.at/~edels/">
Herbert Edelsbrunner's</a> research group at <a HREF="http://www.ist.ac.at">IST Austria</a>.
</p>
<br/>
<p>
I am currently advising and mentoring the graduate students and postdocs
<a HREF="https://bfluhr.com"><i>Benedikt Fluhr</i></a>,
<a HREF="https://github.com/davidhien"><i>David Hien</i></a> (jointly with <a HREF="https://www.professoren.tum.de/junge-oliver">Oliver Junge</a>),
<a HREF="https://geo.ma.tum.de/de/personen/fabian-roll.html"><i>Fabian Roll</i></a>,
<a HREF="https://alexanderrolle.github.io"><i>Alexander Rolle</i></a>,
<a HREF="https://twitter.com/SkarbyJ"><i>Jacob Skarby</i></a>,
<a HREF="http://www.geometrie.tugraz.at/soels/"><i>Matthias Söls</i></a>,
and
<a HREF="https://de.linkedin.com/in/nico-stucki-8aa594168"><i>Nico Stucki</i></a>.
<br/>
My former students and postdocs include
<a HREF="http://www.geometrie.tugraz.at/bjerkevik/"><i>Håvard B. Bjerkevik</i></a>,
<a HREF="https://research.vu.nl/en/persons/magnus-botnan"><i>Magnus B. Botnan</i></a>,
<a HREF="https://geo.ma.tum.de/de/personen/fabian-lenzen.html"><i>Fabian Lenzen</i></a>,
<a HREF="https://sites.google.com/site/fpatqub/"><i>Florian Pausinger</i></a>,
<a HREF="https://erikaroldan.net"><i>Érika Roldán Roa</i></a>,
<a HREF="https://geo.ma.tum.de/de/personen/abhishek-rathod.html"><i>Abhishek Rathod</i></a>,
and
<a HREF="https://www.mathi.uni-heidelberg.de/people/personeninfo.html?uid=mschmahl"><i>Maximilian Schmahl</i></a>.
</p>
<br><br>
<!--
<strong>Research interests:</strong><br>
<p class="text">
Discrete/Computational Geometry/Topology, Algorithms, Combinatorics.
</p>
<br><br>
-->
<strong>Contact:</strong><br>
<table border="0" cellpadding="0" cellspacing="0">
<tbody>
<tr>
<td valign="top" align="center"> <br></td>
<td valign="middle" width="300">
Prof. Dr. Ulrich Bauer<br>
Applied and Computational Topology<br>
Department of Mathematics<br>
Technical University of Munich<br>
Boltzmannstraße 3<br>
D-85747 Garching bei München<br>
</td>
<td valign="middle" width="300">
<strong>Vox</strong>: +49 89 289 18361<br>
<strong>Net</strong>: mail (at) ulrich-bauer.org
</td>
</tr>
</tbody>
</table>
<br><br>
<!-- +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ -->
<!-- +++++++++++++++++ JOURNAL ARTICLES ++++++++++++++++++++++++ -->
<!-- +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ -->
<!--
<span>
<b>Preprints</b>
</span>
<table border="0" cellpadding="2" cellspacing="15" width="700">
<colgroup>
<col width="135">
<col>
<col>
</colgroup>
<tbody>
<!-- new entry ->
<tr>
<td>
<div align="center">
<img src="img/persistent-betti-teaser.svg" width="128" alt="kolmogorov" style="text-align: center; border: 0px solid;">
</div></td>
<td><strong>Persistent Betti numbers of random Čech complexes
</strong><br>
Ulrich Bauer and Florian Pausinger.
<br>
<small>
<b>Abstract:</b>
We study the persistent homology of random Čech complexes. Generalizing a method of
Penrose for studying random geometric graphs, we first describe an appropriate theoretical
framework in which we can state and address our main questions. Then we define the kth
persistent Betti number of a random Čechcomplex and determine its asymptotic order in
the subcritical regime. This extends a result of Kahle on the asymptotic order of the ordinary
kth Betti number of such complexes to the persistent setting.
<br>
<a target="_blank" href="http://arxiv.org/abs/1801.08376">[arXiv]</a>
</small>
<br>
</td>
</tr>
<!-- new entry ->
<tr>
<td>
<div align="center">
<img src="img/persistent-map-teaser.svg" width="128" alt="kolmogorov" style="text-align: center; border: 0px solid;">
</div></td>
<td><strong>Persistence in sampled dynamical systems faster
</strong><br>
Ulrich Bauer, Herbert Edelsbrunner, Grzegorz Jablonski, and Marian Mrozek.
<br>
<small>
<b>Abstract:</b>
We call a continuous self-map that reveals itself through a discrete set of point-value pairs a
sampled dynamical system. Capturing the available information with chain maps on
Delaunay complexes, we use persistent homology to quantify the evidence of recurrent
behavior, and to recover the eigenspaces of the endomorphism on homology induced by the
self-map. The chain maps are constructed using discrete Morse theory for Cech and
Delaunay complexes, representing the requisite discrete gradient field implicitly in order to
get fast algorithms.
<br>
<a target="_blank" href="http://arxiv.org/abs/1709.04068">[arXiv]</a>
</small>
<br>
</td>
</tr>
</table>
<br><br>
<!-- end preprints -->
<span>
<b>Software</b>
</span>
<table border="0" cellpadding="2" cellspacing="15" width="700">
<colgroup>
<col width="135">
<col>
<col>
</colgroup>
<tbody>
<!-- new entry -->
<tr>
<td>
<div align="center">
<img src="img/ripser-teaser.svg" width="128" alt="delaunay" style="text-align: center; border: 0px solid;">
</div></td>
<td><strong>Ripser: a lean C++ code for the computation of Vietoris–Rips persistence barcodes
</strong><br>
Ulrich Bauer (2015–2021). Licensed under MIT license.
<br>
<small>
<b>Description:</b>
Ripser is a lean C++ code for the computation of Vietoris–Rips persistence barcodes. It can do just this one thing, but does it extremely well.
<p>
The implementation is based on an implicit algorithmic representation of the coboundary operator and of the filtration order, avoiding the explicit construction of the filtration boundary matrix.
Our software shows significant improvements over existing software both in time and memory usage.
<p>
The source code consists of around 1000 lines of C++ code.
It supports for coefficients in prime finite fields and sparse distance matrices for computing the Vietoris–Rips persistence barcodes only up to a specified threshold.
No external dependencies are required.
<p>
To see a live demo of Ripser's capabilities, go to <a href="http://live.ripser.org" rel="nofollow"><small>live.ripser.org</small></a>. The computation happens inside the browser (using <a href="https://www.chromium.org/nativeclient/pnacl/" rel="nofollow"><small>PNaCl</small></a> on Chrome and JavaScript via <a href="http://emscripten.org" rel="nofollow"><small>Emscripten</small></a> on other browsers).
<br>
<a target="_blank" href="http://live.ripser.org">[live]</a>
<a target="_blank" href="http://ripser.org">[github]</a>
</small>
<br>
</td>
</tr>
<!-- new entry -->
<tr>
<td>
<div align="center">
<img src="img/persistence_diagram_scaled_teaser.svg" width="128" alt="delaunay" style="text-align: center; border: 0px solid;">
</div></td>
<td><strong>PHAT (Persistent Homology Algorithm Toolbox)</strong><br>
Ulrich Bauer, Michael Kerber, Jan Reininghaus.
Copyright IST Austria (2013–2017). Licensed under LGPL.
<br>
<small>
<b>Description:</b>
PHAT is an open-source C++ library for the computation of persistent homology by matrix reduction, targeted towards developers of software for topological data analysis. We aim for a simple generic design that decouples algorithms from data structures without sacrificing efficiency or user-friendliness. PHAT provides numerous different reduction strategies as well as data types to store and manipulate the boundary matrix.<br>
<a target="_blank" href="https://bitbucket.org/phat-code/phat/">[bitbucket]</a>
</small>
<br>
</td>
</tr>
</table>
<br><br>
<span>
<b>Selected Publications</b> <a target="_blank" href="https://scholar.google.de/citations?hl=de&user=cMGWaM8AAAAJ&sortby=pubdate">[all publications]</a>
</span>
<table border="0" cellpadding="2" cellspacing="15" width="700">
<colgroup>
<col width="135">
<col>
<col>
</colgroup>
<tbody>
<!-- new entry -->
<tr>
<td>
<div align="center">
<img src="img/reeb-universal-teaser.svg" width="128" alt="kolmogorov" style="text-align: center; border: 0px solid;">
</div></td>
<td><strong>The Reeb Graph Edit Distance is Universal
</strong><br>
Ulrich Bauer, Claudia Landi, and Facundo Mémoli.
Foundations of Computational Mathematics 21 (2021), 1441–1464.
<br>
<small>
<b>Abstract:</b>
We consider the setting of Reeb graphs of piecewise linear functions and study distances
between them that are stable, meaning that functions which are similar in the supremum
norm ought to have similar Reeb graphs. We define an edit distance for Reeb graphs and
prove that it is stable and universal, meaning that it provides an upper bound to any other
stable distance. In contrast, via a specific construction, we show that the interleaving
distance and the functional distortion distance on Reeb graphs are not universal.
<br>
<a target="_blank" href="http://arxiv.org/abs/1801.01866">[arXiv]</a>
</small>
<br>
</td>
</tr>
<!-- new entry -->
<tr>
<td>
<div align="center">
<img src="img/ripser-teaser.svg" width="128" alt="delaunay" style="text-align: center; border: 0px solid;">
</div></td>
<td><strong>Ripser: a lean C++ code for the computation of Vietoris–Rips persistence barcodes
</strong><br>
Ulrich Bauer.
Journal of Applied and Computational Topology 5 (2021), 391–423.
<br>
<small>
<b>Abstract:</b>
We present an algorithm for the computation of Vietoris–Rips persistence barcodes and describe its implementation in the software Ripser. The method relies on implicit representations of the coboundary operator and the filtration order of the simplices, avoiding the explicit construction and storage of the filtration coboundary matrix. Moreover, it makes use of apparent pairs, a simple but powerful method for constructing a discrete gradient field from a total order on the simplices of a simplicial complex, which is also of independent interest. Our implementation shows substantial improvements over previous software both in time and memory usage.<br>
<a target="_blank" href="http://doi.org/10.1007/s41468-021-00071-5">[doi]</a>
<a target="_blank" href="https://arxiv.org/abs/1908.02518">[arxiv]</a>
</small>
<br>
</td>
</tr>
<!-- new entry -->
<tr>
<td>
<div align="center">
<img src="img/clusters.svg" width="128" alt="matching" style="text-align: center; border: 0px solid;">
</div></td>
<td><strong>Cotorsion torsion triples and the representation theory of filtered hierarchical clustering
</strong><br>
Ulrich Bauer, Magnus B Botnan, Steffen Oppermann, Johan Steen.
Advances in Mathematics 369 (2020), 67–96.
<br>
<small>
<b>Abstract:</b>
We give a full classification of representation types of the subcategories of representations of an m×n rectangular grid with monomorphisms (dually, epimorphisms) in one or both directions, which appear naturally in the context of clustering as two-parameter persistent homology in degree zero. We show that these subcategories are equivalent to the category of all representations of a smaller grid, modulo a finite number of indecomposables. This equivalence is constructed from a certain cotorsion torsion triple, which is obtained from a tilting subcategory generated by said indecomposables.
<br>
<a target="_blank" href="http://doi.org/10.1016/j.aim.2020.107171">[doi]</a>
<a target="_blank" href="https://arxiv.org/abs/1904.07322">[arXiv]</a>
</small>
<br>
</td>
</tr>
<!-- new entry -->
<tr>
<td>
<div align="center">
<img src="img/matching-teaser.svg" width="128" alt="matching" style="text-align: center; border: 0px solid;">
</div></td>
<td><strong>Persistence Diagrams as Diagrams: A Categorification of the Stability Theorem
</strong><br>
Ulrich Bauer and Michael Lesnick.
Topological Data Analysis. Abel Symposia, vol 15. Springer (2020), 67–96.
<br>
<small>
<b>Abstract:</b>
Persistent homology, a central tool of topological data analysis, provides invariants of data
called barcodes (also known as persistence diagrams). A barcode is simply a multiset of real
intervals. Recent work of Edelsbrunner, Jablonski, and Mrozek suggests an equivalent
description of barcodes as functors R-> Mch, where R is the poset category of real numbers
and Mch is the category whose objects are sets and whose morphisms are matchings (ie,
partial injective functions). Such functors form a category Mch^ R whose morphisms are the
natural transformations. Thus, this interpretation of barcodes gives us a hitherto unstudied
categorical structure on barcodes. The aim of this note is to show that this categorical
structure leads to surprisingly simple reformulations of both the well-known stability theorem
for persistent homology and a recent generalization called the induced matching theorem.
<br>
<a target="_blank" href="http://arxiv.org/abs/1610.10085">[arXiv]</a>
</small>
<br>
</td>
</tr>
<!-- new entry -->
<tr>
<td>
<div align="center">
<img src="img/morse-approx-teaser.crop.svg" width="128" alt="kolmogorov" style="text-align: center; border: 0px solid;">
</div></td>
<td><strong>Hardness of Approximation for Morse Matching
</strong><br>
Ulrich Bauer and Abhishek Rathod.
SODA '19: Proceedings of the 30th ACM-SIAM Symposium on Discrete Algorithms (2019), 2663-2774.
<br>
<small>
<b>Abstract:</b>
We consider the approximability of maximization and minimization variants of the Morse
matching problem, posed as open problems by Joswig and Pfetsch. We establish hardness
results for Max-Morse matching and Min-Morse matching. In particular, we show that, for a
simplicial complex with n simplices and dimension $ d\leq 3$, it is NP-hard to approximate
Min-Morse matching within a factor of $ O (n^{1-\epsilon}) $, for any $\epsilon> 0$.
Moreover, using an L-reduction from Degree 3 Max-Acyclic Subgraph to Max-Morse
matching, we show that it is both NP-hard and UGC-hard to approximate Max-Morse
matching for simplicial complexes of dimension $ d\leq 2$ within certain explicit constant
factors.
<br>
<a target="_blank" href="http://doi.org/10.1137/1.9781611975482.165">[doi]</a>
<a target="_blank" href="http://arxiv.org/abs/1801.08380">[arXiv]</a>
</small>
<br>
</td>
</tr>
<!-- new entry -->
<tr>
<td>
<div align="center">
<img src="img/alphashape1.svg" width="128" alt="delaunay" style="text-align: center; border: 0px solid;">
</div></td>
<td><strong>The Morse theory of Čech and Delaunay complexes
</strong><br>
Ulrich Bauer and Herbert Edelsbrunner.
Transactions of the American Mathematical Society 369:5 (2017), 3741–3762.
<small>
<br>
Conference version: The Morse theory of Čech and Delaunay filtrations,
SoCG '14 Proceedings of the twenty-ninth annual symposium on Computational geometry (2014), 484–490.
<a href="http://dl.acm.org/authorize?6907461"><small>[pdf]</small></a>
<a target="_blank" href="http://dx.doi.org/10.1145/2582112.2582167"><small>[doi]</small></a>
<br>
<b>Abstract:</b>
Given a finite set of points in ℝⁿ and a positive radius, we consider the Čech, Delaunay–Čech, alpha, and wrap complexes as examples of a generalized discrete Morse theory. We prove that the latter three are simple-homotopy equivalent, and the same is true for their weighted versions. Our results have applications in topological data analysis and in the reconstruction of shapes from sampled data.
<br>
<a target="_blank" href="https://doi.org/10.1090/tran/6991">[doi]</a>
<a target="_blank" href="http://arxiv.org/abs/1312.1231">[arXiv]</a>
</small>
<br>
</td>
</tr>
<!-- new entry -->
<tr>
<td>
<div align="center">
<img src="img/kolmogorov-teaser.svg" width="128" alt="kolmogorov" style="text-align: center; border: 0px solid;">
</div></td>
<td><strong>Persistence Barcodes Versus Kolmogorov Signatures: Detecting Modes of One-Dimensional Signals
</strong><br>
Ulrich Bauer, Axel Munk, Hannes Sieling, and Max Wardetzky.
Foundations of Computational Mathematics 17:1 (2017), 1–33.
<br>
<small>
<b>Abstract:</b>
We investigate the problem of estimating the number of modes (i.e., local maxima)—a well-known question in statistical inference—and we show how to do so without presmoothing the data. To this end, we modify the ideas of persistence barcodes by first relating persistence values in dimension one to distances (with respect to the supremum norm) to the sets of functions with a given number of modes, and subsequently working with norms different from the supremum norm. As a particular case, we investigate the Kolmogorov norm. We argue that this modification has certain statistical advantages. We offer confidence bands for the attendant Kolmogorov signatures, thereby allowing for the selection of relevant signatures with a statistically controllable error. As a result of independent interest, we show that taut strings minimize the number of critical points for a very general class of functions. We illustrate our results by several numerical examples.
<br>
<a target="_blank" href="http://doi.org/10.1007/s10208-015-9281-9">[doi]</a>
<a target="_blank" href="http://arxiv.org/abs/1404.1214">[arXiv]</a>
</small>
<br>
</td>
</tr>
<!-- new entry -->
<tr>
<td>
<div align="center">
<img src="img/persistence_diagram_scaled_teaser.svg" width="128" alt="delaunay" style="text-align: center; border: 0px solid;">
</div></td>
<td><strong>PHAT–Persistent homology algorithms toolbox
</strong><br>
Ulrich Bauer, Michael Kerber, Jan Reininghaus, Hubert Wagner.
Journal of Symbolic Computation 78 (2017), 76–90.
<small>
<br>
Conference version: ICMS 2014: Mathematical Software – ICMS 2014, 137–143.
<a target="_blank" href="https://doi.org/10.1007/978-3-662-44199-2_24"><small>[doi]</small></a>
<br>
<b>Abstract:</b>
Phat is an open-source C++ library for the computation of persistent homology by matrix reduction, targeted towards developers of software for topological data analysis. We aim for a simple generic design that decouples algorithms from data structures without sacrificing efficiency or user-friendliness. We provide numerous different reduction strategies as well as data types to store and manipulate the boundary matrix. We compare the different combinations through extensive experimental evaluation and identify optimization techniques that work well in practical situations. We also compare our software with various other publicly available libraries for persistent homology.
<br>
<a target="_blank" href="http://doi.org/10.1016/j.jsc.2016.03.008">[doi]</a>
</small>
<br>
</td>
</tr>
<!-- new entry ->
<tr>
<td>
<div align="center">
<img src="img/reeb-edit-teaser.svg" width="128" alt="induced-matchings" style="text-align: center; border: 0px solid;">
</div></td>
<td><strong>An Edit Distance For Reeb Graphs
</strong><br>
Ulrich Bauer, Barbara Di Fabio, and Claudia Landi.
3DOR '16 Proceedings of the Eurographics 2016 Workshop on 3D Object Retrieval (2016), 27–34
<small>
<br>
<b>Abstract:</b>
We consider the problem of assessing the similarity of 3D shapes using Reeb graphs from the standpoint of robustness under perturbations. For this purpose, 3D objects are viewed as spaces endowed with real-valued functions, while the similarity between the resulting Reeb graphs is addressed through a graph edit distance. The cases of smooth functions on manifolds and piecewise linear functions on polyhedra stand out as the most interesting ones. The main contribution of this paper is the introduction of a general edit distance suitable for comparing Reeb graphs in these settings. This edit distance promises to be useful for applications in 3D object retrieval because of its stability properties in the presence of noise.
<br>
<a target="_blank" href="https://doi.org/10.2312/3dor.20161084">[doi]</a>
</small>
<br>
</td>
</tr>
<!-- -->
<!-- new entry -->
<tr>
<td>
<div align="center">
<img src="img/matching-barcodes-teaser.svg" width="128" alt="induced-matchings" style="text-align: center; border: 0px solid;">
</div></td>
<td><strong>Induced Matchings and the Algebraic Stability of Persistence Barcodes
</strong><br>
Ulrich Bauer and Michael Lesnick.
Journal of Computational Geometry 6:2 (2015), 162–191
(Invited to special issue for best papers of SoCG '14).
<a href="http://dl.acm.org/authorize?6907413">[pdf]</a>
<a target="_blank" href="http://dx.doi.org/10.1145/2582112.2582168">[doi]</a>
<small>
<br>
Conference version: Induced Matchings of Barcodes and the Algebraic Stability of Persistence,
SoCG '14 Proceedings of the twenty-ninth annual symposium on Computational geometry (2014), 355–364.
<br>
<b>Abstract:</b>
We define a simple, explicit map sending a morphism f: M → N of pointwise finite dimensional persistence modules to a matching between the barcodes of M and N. Our main result is that, in a precise sense, the quality of this matching is tightly controlled by the lengths of the longest intervals in the barcodes of ker f and coker f.
As an immediate corollary, we obtain a new proof of the algebraic stability of persistence, a fundamental result in the theory of persistent homology. In contrast to previous proofs, ours shows explicitly how a δ-interleaving morphism between two persistence modules induces a δ-matching between the barcodes of the two modules. Our main result also specializes to a structure theorem for submodules and quotients of persistence modules.
<br>
<a target="_blank" href="http://dx.doi.org/10.20382/jocg.v6i2a9">[doi]</a>
<a target="_blank" href="http://arxiv.org/abs/1311.3681">[arXiv]</a>
</small>
<br>
</td>
</tr>
<!-- new entry ->
<tr>
<td>
<div align="center">
<img src="img/medical-example.png" width="128" style="text-align: center; border: 0px solid;">
</div></td>
<td><strong>Statistical topological data analysis-a kernel perspective</strong><br>
Roland Kwitt, Stefan Huber, Marc Niethammer, Weili Lin, and Ulrich Bauer. NIPS'15 Advances in neural information processing systems (2015), 3070–3078.
<br>
<small>
<b>Abstract:</b>
Topological data analysis offers a rich source of valuable information to study vision
problems. Yet, so far we lack a theoretically sound connection to popular kernelbased
learning techniques, such as kernel SVMs or kernel PCA. In this work, we establish such a
connection by designing a multi-scale kernel for persistence diagrams, a stable summary
representation of topological features in data. We show that this kernel is positive definite
and prove its stability with respect to the 1-Wasserstein distance. Experiments on two
benchmark datasets for 3D shape classification/retrieval and texture recognition show
considerable performance gains of the proposed method compared to an alternative
approach that is based on the recently introduced persistence landscapes.
<br>
<a href="http://openaccess.thecvf.com/content_cvpr_2015/papers/Reininghaus_A_Stable_Multi-Scale_2015_CVPR_paper.pdf">[pdf]</a>
</small>
<br>
</td>
</tr>
<!-- -->
<!-- new entry ->
<tr>
<td>
<div align="center">
<img src="img/SmoothingReebGraph-Example.svg" width="128" alt="reeb-graph" style="text-align: center; border: 0px solid;">
</div></td>
<td><strong>Strong equivalence of the interleaving and functional distortion metrics for Reeb graphs</strong><br>
Ulrich Bauer, Elizabeth Munch, and Yusu Wang. SoCG '15 Proceedings of the 31st International Symposium on Computational Geometry (2015), 461–475.
<br>
<small>
<b>Abstract:</b>
The Reeb graph is a construction that studies a topological space through the lens of a real valued function. It has widely been used in applications, however its use on real data means that it is desirable and increasingly necessary to have methods for comparison of Reeb graphs. Recently, several methods to define metrics on the space of Reeb graphs have been presented. In this paper, we focus on two: the functional distortion distance and the interleaving distance. The former is based on the Gromov– Hausdorff distance, while the latter utilizes the equivalence between Reeb graphs and a particular class of cosheaves. However, both are defined by constructing a near-isomorphism between the two graphs of study. In this paper, we show that the two metrics are strongly equivalent on the space of Reeb graphs. In particular, this gives an immediate proof of bottleneck stability for persistence diagrams in terms of the Reeb graph interleaving distance.
<br>
<a href="http://dl.acm.org/authorize?6907469">[pdf]</a>
<a target="_blank" href="http://doi.org/10.4230/LIPIcs.SOCG.2015.461">[doi]</a>
<a target="_blank" href="https://arxiv.org/abs/1412.6646">[arXiv]</a>
</small>
<br>
</td>
</tr>
<!-- -->
<!-- new entry -->
<tr>
<td>
<div align="center">
<img src="img/pss-kernel-teaser.svg" width="128" style="text-align: center; border: 0px solid;">
</div></td>
<td><strong>A stable multi-scale kernel for topological machine learning</strong><br>
Jan Reininghaus, Stefan Huber, Ulrich Bauer, and Roland Kwitt. CVPR'15 Proceedings of the IEEE conference on computer vision and pattern recognition (2015), 4741-4748.
<br>
<small>
<b>Abstract:</b>
Topological data analysis offers a rich source of valuable information to study vision
problems. Yet, so far we lack a theoretically sound connection to popular kernelbased
learning techniques, such as kernel SVMs or kernel PCA. In this work, we establish such a
connection by designing a multi-scale kernel for persistence diagrams, a stable summary
representation of topological features in data. We show that this kernel is positive definite
and prove its stability with respect to the 1-Wasserstein distance. Experiments on two
benchmark datasets for 3D shape classification/retrieval and texture recognition show
considerable performance gains of the proposed method compared to an alternative
approach that is based on the recently introduced persistence landscapes.
<br>
<a href="http://openaccess.thecvf.com/content_cvpr_2015/papers/Reininghaus_A_Stable_Multi-Scale_2015_CVPR_paper.pdf">[pdf]</a>
</small>
<br>
</td>
</tr>
<!-- new entry -->
<tr>
<td>
<div align="center">
<img src="img/reeb-teaser.svg" width="128" alt="reeb-graph" style="text-align: center; border: 0px solid;">
</div></td>
<td><strong>Measuring Distance between Reeb Graphs</strong><br>
Ulrich Bauer, Xiaoyin Ge, and Yusu Wang. SoCG '14 Proceedings of the twenty-ninth annual symposium on Computational geometry (2014), 464–473.
<br>
<small>
<b>Abstract:</b>
We propose a metric for Reeb graphs, called the functional distortion distance. Under this distance measure, the Reeb graph is stable against small changes of input functions. At the same time, it remains discriminative at differentiating input functions. In particular, the main result is that the functional distortion distance between two Reeb graphs is bounded from below by (and thus more discriminative than) the bottleneck distance between both the ordinary and extended persistence diagrams for appropriate dimensions.
<br>
As an application of our results, we analyze a natural simplification scheme for Reeb graphs, and show that persistent features in Reeb graph remains persistent under simplification. Understanding the stability of important features of the Reeb graph under simplification is an interesting problem on its own right, and critical to the practical usage of Reeb graphs.
<br>
<a href="http://dl.acm.org/authorize?6907469">[pdf]</a>
<a target="_blank" href="http://dx.doi.org/10.1145/2582112.2582169">[doi]</a>
<a target="_blank" href="http://arxiv.org/abs/1307.2839">[arXiv]</a>
</small>
<br>
</td>
</tr>
<!-- new entry -->
<tr>
<td>
<div align="center">
<img src="img/chunk-teaser.svg" width="128" alt="chunks" style="text-align: center; border: 0px solid;">
</div></td>
<td><strong>Clear and Compress: Computing Persistent Homology in Chunks</strong><br>
Ulrich Bauer, Michael Kerber, and Jan Reininghaus,
Topological Methods in Data Analysis and Visualization III
Mathematics and Visualization 2014, 103–117.
<br>
<small>
<b>Abstract:</b>
We present a parallelizable algorithm for computing the persistent homology of a filtered chain complex. Our approach differs from the commonly used reduction algorithm by first computing persistence pairs within local chunks, then simplifying the unpaired columns, and finally applying standard reduction on the simplified matrix. The approach generalizes a technique by Günther et al., which uses discrete Morse Theory to compute persistence; we derive the same worst-case complexity bound in a more general context. The algorithm employs several practical optimization techniques which are of independent interest. Our sequential implementation of the algorithm is competitive with state-of-the-art methods, and we improve the performance through parallelized computation.
<br>
<a target="_blank" href="http://dx.doi.org/10.1007/978-3-319-04099-8_7">[doi]</a>
<a target="_blank" href="http://arxiv.org/abs/1303.0477">[arXiv]</a>
</small>
<br>
</td>
</tr>
<!-- new entry -->
<tr>
<td>
<div align="center">
<img src="img/distributed-persistence-teaser.svg" width="128" alt="distributed-persistence" style="text-align: center; border: 0px solid;">
</div></td>
<td><strong>Distributed computation of persistent homology</strong><br>
Ulrich Bauer, Michael Kerber, and Jan Reininghaus. Proceedings of the Sixteenth Workshop on Algorithm Engineering and Experiments (ALENEX14), 31–38.
<br>
<small>
<b>Abstract:</b>
Persistent homology is a popular and powerful tool for capturing topological features of data. Advances in algorithms for computing persistent homology have reduced the computation time drastically – as long as the algorithm does not exhaust the available memory. Following up on a recently presented parallel method for persistence computation on shared memory systems, we demonstrate that a simple adaption of the standard reduction algorithm leads to a variant for distributed systems. Our algorithmic design ensures that the data is distributed over the nodes without redundancy; this permits the computation of much larger instances than on a single machine. Moreover, we observe that the parallelism at least compensates for the overhead caused by communication between nodes, and often even speeds up the computation compared to sequential and even parallel shared memory algorithms. In our experiments, we were able to compute the persistent homology of filtrations with more than a billion (10⁹) elements within seconds on a cluster with 32 nodes using less than 10GB of memory per node.<br>
<a target="_blank" href="http://epubs.siam.org/doi/pdf/10.1137/1.9781611973198.4">[pdf]</a>
<a target="_blank" href="http://dx.doi.org/10.1137/1.9781611973198.4">[doi]</a>
</small>
<br>
</td>
</tr>
<!-- new entry -->
<tr>
<td>
<div align="center">
<img src="img/tentacle-transp-new.svg" width="128" alt="tentacles" style="text-align: center; border: 0px solid;">
</div>
</td>
<td><strong>Homological reconstruction and simplification in R³</strong><br>
Dominique Attali, Ulrich Bauer, Olivier Devillers, Marc Glisse, and André Lieutier.
Computational Geometry 48:8 (2015), 606–621
(Invited to special issue for best papers of SoCG '13).
<small>
<br>
Conference version:
SoCG '13 Proceedings of the twenty-ninth annual symposium on Computational geometry (2013), 117–126.
<a target="_blank" href="http://dl.acm.org/authorize?6822801"><small>[pdf]</small></a>
<a target="_blank" href="http://dx.doi.org/10.1145/2493132.2462373"><small>[doi]</small></a>
<br>
<br>
<b>Abstract:</b>
We consider the problem of deciding whether the persistent homology group of a simplicial pair (K,L) can be realized as the homology H<sub>*</sub>(X) of some complex X with L ⊂ X ⊂ K. We show that this problem is NP-complete even if K is embedded in R³. As a consequence, we show that it is NP-hard to simplify level and sublevel sets of scalar functions on S³ within a given tolerance constraint. This problem has relevance to the visualization of medical images by isosurfaces. We also show an implication to the theory of well groups of scalar functions: not every well group can be realized by some level set, and deciding whether a well group can be realized is NP-hard.
<br>
<a href="pub/bauer-homologicalReconstruction.pdf">[pdf]</a>
<a target="_blank" href="https://doi.org/10.1016/j.comgeo.2014.08.010">[doi]</a>
</small>
<br>
</td>
</tr>
<!-- new entry -->
<tr>
<td>
<div align="center">
<img src="img/morse_teaser.svg" width="128" alt="contours" style="text-align: center; border: 0px solid;">
</div>
</td>
<td><strong>Optimal topological simplification of discrete functions on surfaces</strong><br>
Ulrich Bauer, Carsten Lange, and Max Wardetzky. Discrete and Computational Geometry 47:2 (2012), 347–377.
<br>
<small>
<b>Abstract:</b>
Given a function f on a surface and a tolerance δ > 0, we construct a function f<sub>δ</sub> subject to ‖f<sub>δ</sub> - f‖<sub>∞</sub> ≤ δ such that f<sub>δ</sub> has a minimum number of critical points. Our construction relies on a connection between discrete Morse theory and persistent homology and completely removes homological noise with persistence ≤ 2δ from the input function f. The number of critical points of the resulting simplified function f<sub>δ</sub> achieves the lower bound dictated by the stability theorem of persistent homology. We show that the simplified function can be computed in linear time after persistence pairs have been computed.
<!--
We present an efficient algorithm for computing a function that minimizes the number of critical points among all functions within a prescribed distance δ from a given input function. The result is achieved by establishing a connection between discrete Morse theory and persistent homology. Our method completely removes homological noise with persistence less than 2δ, constructively proving that the lower bound on the number of critical points given by the stability theorem of persistent homology is tight in dimension two for any input function.
-->
<br>
<a target="_blank" href="http://link.springer.com/content/pdf/10.1007%2Fs00454-011-9350-z.pdf">[pdf]</a>
<a target="_blank" href="http://dx.doi.org/10.1007/s00454-011-9350-z">[doi]</a>
</small>
<br>
</td>
</tr>
<!-- new entry -->
<tr>
<td>
<div align="center">
<img src="img/thesis_teaser.png" width="128" alt="contours" style="text-align: center; border: 0px solid;">
</div>
</td>
<td><strong>Persistence in discrete Morse Theory</strong><br>
PhD thesis, University of Göttingen, 2011.
<br>
<small>
<b>Abstract:</b>
The goal of this thesis is to bring together two different theories about critical points of a scalar function and their relation to topology: Discrete Morse theory and Persistent homology. While the goals and fundamental techniques are different, there are certain themes appearing in both theories that closely resemble each other. In certain cases, the two threads can be joined, leading to new insights beyond the classical realm of one particular theory.
<p>
Discrete Morse theory provides combinatorial equivalents of several core concepts of classical Morse theory, such as discrete Morse functions, discrete gradient vector fields, critical points, and a cancelation theorem for the elimination of critical points of a vector field. Because of its simplicity, it not only maintains the intuition of the classical theory but allows to surpass it in a certain sense by providing explicit and canonical constructions that would become quite complicated in the smooth setting.
<p>
Persistent homology quantifies topological features of a function. It defines the birth and death of homology classes at critical points, identifies pairs of these (persistence pairs), and provides a quantitative notion of their stability (persistence).
<p>
Whereas (discrete) Morse theory makes statements about the homotopy type of the sublevel sets of a function, persistence is concerned with their homology. While homology is an invariant of homotopy equivalences, the converse is not true: not every map inducing an isomorphism in homology is a homotopy equivalence. In this thesis we establish a connection between both theories and use this combination to solve problems that are not easily accessibly by any single theory alone. In particular, we solve the problem of minimizing the number of critical points of a function on a surface within a certain tolerance from a given input function.
<br>
<a target="_blank" href="http://webdoc.sub.gwdg.de/diss/2011/bauer_u/bauer_u.pdf">[pdf]</a>
<a target="_blank" href="http://hdl.handle.net/11858/00-1735-0000-0006-B3E6-C">[hdl]</a>
</small>
<br>
</td>
</tr>
<!-- new entry ->
<tr>
<td>
<div align="center">
<img src="img/tv-teaser.svg" width="128" alt="Persistence" style="text-align: center; border: 0px solid;">
</div>
</td>
<td><strong>Total Variation Meets Topological Persistence: A First Encounter</strong><br>
Ulrich Bauer, Carola-Bibiane Schönlieb, and Max Wardetzky.
Proceedings of ICNAAM 2010, 1022–1026.<br>
<small>
<b>Abstract:</b> We present first insights into the relation between two popular yet apparently dissimilar approaches to denoising
of one dimensional signals, based on (i) total variation (TV) minimization and (ii) ideas from topological persistence. While a
close relation between (i) and (ii) might phenomenologically not be unexpected, our work appears to be the first to make this
connection precise for one dimensional signals. We provide a link between (i) and (ii) that builds on the equivalence between
TV-L2 regularization and taut strings and leads to a novel and efficient denoising algorithm that is contrast preserving and
operates in <em>O</em>(<em>n</em>log<em>n</em>) time, where <em>n</em> is the size of the input.
<br>
<a target="_blank" href="http://ddg.math.uni-goettingen.de/pub/tv_persistence.pdf">[pdf]</a>
<a target="_blank" href="http://dx.doi.org/10.1063/1.3497795">[doi]</a>
</small>
<br>
</td>
</tr>
<!-- new entry -->
<tr>
<td>
<div align="center">
<img src="img/star_coarse.svg" alt="curvature lines" width="128" style="text-align: center; border: 0px solid;">
</div></td>
<td><strong>Uniform Convergence of Discrete Curvatures from Nets of Curvature Lines</strong><br>
Ulrich Bauer, Konrad Polthier, Max Wardetzky, Discrete and Computational Geometry 43:4 (2010), 798–823.
<br>
<small>
<b>Abstract:</b> We study “Steiner-type” discrete curvatures computed from
nets of curvature lines on a given smooth surface, and prove their uniform pointwise convergence
to smooth principal curvatures. We provide explicit error bounds, with
constants depending only on the limit surface and the shape regularity of the
discrete net.
<br>
<a target="_blank" href="http://link.springer.com/content/pdf/10.1007%2Fs00454-009-9237-4.pdf">[pdf]</a>
<a target="_blank" href="http://dx.doi.org/10.1007/s00454-009-9237-4">[doi]</a>
</small>
<br>
</td>
</tr>
<!-- new entry -->
<tr>
<td>
<div align="center">
<img src="img/tubescan-teaser.png" width="128" alt="tubes" style="text-align: center; border: 0px solid;" >
</div></td>
<td><strong>Generating Parametric Models of Tubes from Laser Scans</strong><br>
Ulrich Bauer, Konrad Polthier,
Computer-Aided Design 41 (2009), 719–729.
<small>
<br>
Conference version: Parametric Reconstruction of Bent Tube Surfaces,
Proceedings NASAGEM/Cyberworlds 2007, 465–474. <a target="_blank" href="pub/bauer-ParametricReconstruction.pdf"><small>[pdf]</small></a> <a target="_blank" href="http://dx.doi.org/10.1109/CW.2007.59"><small>[doi]</small></a>
<br>
<b>Abstract:</b> We present a method for parametric reconstruction of a piecewise defined pipe surface, consisting of cylinder and torus segments, from an unorganized point set. Our main contributions are reconstruction of the spine curve of a pipe surface from surface samples, and approximation of the spine curve by <i>G¹</i> continuous circular arcs and line segments. Our algorithm accurately outputs the parametric data required for bending machines to create the reconstructed tube.
<br>
<a target="_blank" href="pub/bauer-Tubes.pdf">[pdf]</a>
<a target="_blank" href="http://dx.doi.org/10.1016/j.cad.2009.01.002">[doi]</a>
</small>
<br>
</td>
</tr>
<!-- new entry -->
<tr>
<td>
<div align="center">
<img src="img/tallent_teaser.png" alt="plane detection" width="128" style="text-align: center; border: 0px solid;" >
</div></td>
<td><strong>Detection of Planar Regions in Volume Data for Topology Optimization</strong><br>
Ulrich Bauer, Konrad Polthier,
Proceedings of Geometry Modelling and Processing 2008, Lecture Notes in Computer Science vol. 4975 (2008), 119–126.<br>
<small>
<b>Abstract:</b> We propose a method to identify planar regions in volume
data using a specialized version of the discrete Radon transform operating
on a structured or unstructured grid. The algorithm uses an efficient
discretization scheme for the parameter space to obtain a running time
of <i>O</i>(<i>N</i>(<i>T</i> log <i>T</i>)), where <i>T</i> is the number of cells and <i>N</i> is the number
of plane normals in the discretized parameter space.
We apply our algorithm in an industrial setting and perform experiments
with real-world data generated by topology optimization algorithms,
where the planar regions represent portions of a mechanical part
that can be built using steel plate.
<br>
<a target="_blank" href="http://ddg.math.uni-goettingen.de/pub/bauer-PlanarRegions.pdf">[pdf]</a>
<a target="_blank" href="http://dx.doi.org/10.1007/978-3-540-79246-8_9">[doi]</a>
</small>
<br>
</td>
</tr>
<!-- new entry -->
<!--
<tr>
<td>
<div align="center">
<img src="http://ddg.math.uni-goettingen.de/img/tubescan-teaser-tiny.jpg" alt="tubes" style="text-align: center; border: 0px solid;" >
</div></td>
<td><strong>Parametric Reconstruction of Bent Tube Surfaces</strong><br>
Ulrich Bauer, Konrad Polthier,
Proceedings of the 2007 International Conference on Cyberworlds, pp. 465-474.<br>
<small>
<b>Abstract:</b> We present a method for parametric reconstruction of a piecewise defined pipe surface, consisting of cylinder and torus segments, from an unorganized point set. Our main contributions are reconstruction of the spine curve of a pipe surface from surface samples, and approximation of the spine curve by G1 continuous circular arcs and line segments. Our algorithm accurately outputs the parametric data required for bending machines to create the reconstructed tube.
<br>
<a target="_blank" href="http://ddg.math.uni-goettingen.de/pub/bauer-ParametricReconstruction.pdf">[pdf]</a>
</small>
<br>
</td>
</tr>
-->
</tbody>
</table>
<!-- +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ -->
<!-- +++++++++++++++++++++++++++ THESES ++++++++++++++++++++++++ -->
<!-- +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ -->
<br><br>
<span>
<b>Undergraduate projects</b>
</span>
<br><br>
<table border="0" cellpadding="2" cellspacing="15" width="700">
<colgroup>
<col width="135">
<col>
<col>
</colgroup>
<tbody>
<!-- new entry -- >
<tr>
<td>
<div align="center">
<img src="img/assignment-teaser.png" width="128" alt="assignment" style="text-align: center; border: 0px solid;" >
</div></td>
<td><strong>Assignment Problem with Constraints</strong><br>
Diploma Thesis – ETH Zürich (10/2004 – 03/2005)<br>
<small>
<b>Abstract:</b> Combinatorial optimisation plays an important role in logistics, and many of the basic problems and algorithms find a direct application in this area or even originate from it. For instance, the assignment problem asks for a cost-optimal assignment of workers to tasks or products to warehouse locations.
<br>
Additional constraints on the solutions, such as an equal distribution of products to warehouses, are however often required in real-world settings. An algorithm to solve this problem is developed based on Bertsekas' well-known auction algorithm.
<br>
Advisors: Andreas Weissl and Prof. Angelika Steger, ETH Zürich
<br>
<a target="_blank" href="pub/ConstrainedAssignment.pdf">[pdf]</a>
</small>
<br>
</td>
</tr>
<!-- new entry -- >
<tr>
<td>
<div align="center">
<img src="img/cdk-logo.png" alt="cdk" style="text-align: center; border: 0px solid;" >
</div></td>
<td><strong>Minimum Cycle Bases Algorithms for the Chemistry Development Kit</strong><br>
<p>Interdisciplinary project – TU München (04/2004 – 09/2004)</p>
<small>
The cycles of a graph (the subgraphs whose vertices have even degree) span a matroid; addition on this matroid is defined as the symmetric difference of the edges. A cycle basis is a maximal set of linearly independent cycles; a minimum cycle basis is a cycle basis with minimum edge count (or minimum total edge weight in the case of weighted graphs).
<br>
The Smallest Set of Smallest Rings (SSSR), the chemical equivalent
to a minimum cycle basis, plays an important role in computational
chemistry. However, an efficient and exact algorithm for computing an
SSSR was missing from the <a href="http://cdk.sourceforge.net/"><small>Chemistry Development Toolkit (CDK)</small></a>, a comprehensive
library for computational chemistry which is used in several
projects such as <a href="http://jmol.sourceforge.net/"><small>JMol</small></a> and <a href="http://jchempaint.sourceforge.net/"><small>JChemPaint</small></a>.