Henry Fleischmann - DIMACS REU

Week 1. What is the Steiner tree problem?

June – August 2022 Complexity Theory and Discrete Geometry

Week 2. Hardness of Approximating Euclidean Steiner trees.

June – August 2022 Complexity Theory and Discrete Geometry

Week 3. Studying Regular Simplices.

June – August 2022 Complexity Theory and Discrete Geometry

Week 4. Structural Results.

June – August 2022 Complexity Theory and Discrete Geometry

Week 5. "Starrifying" graphs.

June – August 2022 Complexity Theory and Discrete Geometry

Week 6. The Hamming Steiner Tree Problem Revisited.

June – August 2022 Complexity Theory and Discrete Geometry

Week 7. Better Inapproximability Bounds for Hamming Steiner Trees.

June – August 2022 Complexity Theory and Discrete Geometry

Week 8. Structural Correspondence between Hamming Steiner Trees and Vertex Cover.

June – August 2022 Complexity Theory and Discrete Geometry

Week 9-10. Visiting Charles University in Prague.

June – August 2022 Complexity Theory and Discrete Geometry

Week 1. What is the Steiner tree problem?

June 1-5 Complexity Theory

We introduce the optimal Steiner tree problem.

Week 2. Hardness of Approximating Steiner Trees.

June 6-13

We discuss known results on hardness of approximating Steiner trees and our initial work.

Week 3. Studying Regular Simplices.

June 14-19

A brief discussion of the broad ideas related to regular simplices considered during this week.

Week 4. Structural Results.

June 20-26

A general progress update, including thoughts on the simplex conjecture.

Week 5. "Starrifying" graphs.

June 27–July 4

A general progress update from a coding intensive week.

Week 6. The Hamming Steiner Tree Problem Revisited.

July 5—July 11

In this week, I revisited inapproximability of the Hamming Steiner tree problem, proving far improved inapproximability bounds.

Week 7. Better Inapproximability Bounds for Hamming Steiner Trees.

July 12—July 16

Last week, my inapproximability bounds required the graphs to be triangle-free, worsening the achievable bounds. This week I managed to instead use the regularity of the graphs to achieve improved bounds.

Week 8. Structural Correspondence between Hamming Steiner Trees and Vertex Cover.

July 17–24

This week I showed a structural correspondence between Vertex Covers of 4-regular graphs and Hamming Steiner Trees.

Week 9-10. Visiting Charles University in Prague.

July 25-August 5

For the last two weeks of the program, I visited DIMATIA at Charles University in Prague. I gave a seminar talk there on my summer research.