Skip to main content
Commonmark migration
Source Link

I think this one fits the profile, since it computational in nature, understandable by an undergrad student and still an open problem:

The envy-free cake-cutting: the problem of cutting a heterogeneous "cake" that satisfies the envy-free criterion, namely, that every partner feels that their allocated share is at least as good as any other share, according to their own subjective valuation.

 

How many queries are required for cutting this cake into $n$ slices?

Whether it is "not too famous" might be disputable. Please take it with a grain of salt (I have never heard of it until a while ago, but I am not a mathematician). According to wikipedia and this other question:

The continuous "moving knife" algorithms for envy free cake cutting into connected pieces is only mentioned for up to 4 players. The general case is still an open problem.

I think this one fits the profile, since it computational in nature, understandable by an undergrad student and still an open problem:

The envy-free cake-cutting: the problem of cutting a heterogeneous "cake" that satisfies the envy-free criterion, namely, that every partner feels that their allocated share is at least as good as any other share, according to their own subjective valuation.

 

How many queries are required for cutting this cake into $n$ slices?

Whether it is "not too famous" might be disputable. Please take it with a grain of salt (I have never heard of it until a while ago, but I am not a mathematician). According to wikipedia and this other question:

The continuous "moving knife" algorithms for envy free cake cutting into connected pieces is only mentioned for up to 4 players. The general case is still an open problem.

I think this one fits the profile, since it computational in nature, understandable by an undergrad student and still an open problem:

The envy-free cake-cutting: the problem of cutting a heterogeneous "cake" that satisfies the envy-free criterion, namely, that every partner feels that their allocated share is at least as good as any other share, according to their own subjective valuation.

How many queries are required for cutting this cake into $n$ slices?

Whether it is "not too famous" might be disputable. Please take it with a grain of salt (I have never heard of it until a while ago, but I am not a mathematician). According to wikipedia and this other question:

The continuous "moving knife" algorithms for envy free cake cutting into connected pieces is only mentioned for up to 4 players. The general case is still an open problem.

Source Link
polfosol
  • 573
  • 5
  • 29

I think this one fits the profile, since it computational in nature, understandable by an undergrad student and still an open problem:

The envy-free cake-cutting: the problem of cutting a heterogeneous "cake" that satisfies the envy-free criterion, namely, that every partner feels that their allocated share is at least as good as any other share, according to their own subjective valuation.

How many queries are required for cutting this cake into $n$ slices?

Whether it is "not too famous" might be disputable. Please take it with a grain of salt (I have never heard of it until a while ago, but I am not a mathematician). According to wikipedia and this other question:

The continuous "moving knife" algorithms for envy free cake cutting into connected pieces is only mentioned for up to 4 players. The general case is still an open problem.

Post Made Community Wiki by polfosol