Combinatorial Christmas 2022

As my research takes a final pivot over into the land of combinatorial optimisation with a colleague I figured it might be a nice idea to do an advent calendar of blog posts about combinatorial optimisation An idea which I’m of course shamelessly cribbing from the https://adventofcode.com/ .

Since I have deadlines to hit, I will have to do this economically so I’m counting this announcement and creating the outline and initial research as the first day. My currently planned rough structure is as follows:

• on day 2 and 3 we will give a quick intro into optimisation and what makes it combinatorial (day 2) as well as do a quick tour of the history (day 2), drawing mainly on Prof. Schrijvers scholarship on this topic
• days 4 and 5 will be devoted to introducing linear programs, convex programs and constraints in a bit more detail, since we’ll be using these notions a lot
• days 6, 7 and 8 will be devoted to a journey from the original transportation problem to modern optimal transport theory, mainly for the historical continuity
• day 9 will be an introduction of graphs and sets and an overview on problems defined on them, setting the stage for the next X days
• day 10,11 and 12 will be devoted to the Traveling Sales Person, Minimum Vertex Cover and Max independent set problems
• day 13, 14 and 15 will be an interlude on complexity theory, approximation theory and parametrized complexity
• on days 16 to 20 will talk about graph coloring, steiner trees, knapsacks, scheduling,partitioning and max-cut problems
• finally, days 20 to 23 we will talk about integer linear programming (ILP), mixed integer linear programming (MILPs), SAT and SMT problems.
• and for Christmas Eve,Aðfangadagskvöld,Jolaften,Wigilia and of course, the birthday of Pan Mickiewicz, we will talk about how neural networks and my research ties into all of this

You can see place holder posts below if reading before 2022-12-24 and can directly dive into the calendar if you are from the future - I hope the Ukraine war is over by then.

Слава Україні! And Happy Holidays!

Edit from the future: I got covid on day 4 of writing this, which means I will move the schedule to “as soon as done”.

Day 4: Linear Programs

Authors: Nauka

Day 3: History and fields

Authors: Nauka

Day 2: Concepts and Language

Authors: Nauka

Day 1: Combinatorial Christmas 2022