Mittagsseminar (in cooperation with J. Lengler, A. Steger, and D. Steurer)

Date and Time: Thursday, August 29, 2024, 01:00 pm

Duration: 30 minutes

Location: OAT S15/S16/S17

Speaker: Linus Stalder

α-Necklace-Splitting in Polynomial Time

Two thieves have stolen a necklace that consists of multiple beads of different types. To divide their loot, they want to split the necklace such that both of them gets half the beads of each type. The well-known Ham-Sandwich Theorem implies that they can do that using n cuts, where n is the number of different types of beads. It is a natural question to ask what happens when the thieves do not want to share the necklace fairly. In particular, assume that they agree that the first thief gets α_i beads of the i-th type of beads. In general, n cuts do not suffice anymore to cut the necklace according to the vector α = (α₁, ..., α_n). However, if the necklace satisfies a condition called n-separability, a generalization of the Ham-Sandwich Theorem, called the α-Ham-Sandwich Theorem, implies that n cuts always suffice. Moreover, for any possible α, the cuts are unique. In this talk, I present a polynomial time algorithm that gets as input an n-separable necklace and a vector α and outputs the unique α-cut. This algorithm was developed during my Master Thesis.

Upcoming talks     |     All previous talks     |     Talks by speaker     |     Upcoming talks in iCal format (beta version!)

Previous talks by year:   2025  2024  2023  2022  2021  2020  2019  2018  2017  2016  2015  2014  2013  2012  2011  2010  2009  2008  2007  2006  2005  2004  2003  2002  2001  2000  1999  1998  1997  1996  

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M   |   admin login