"O slo\u017Eitosti d\u011Blen\u00ED zdroj\u016F"@cs . "8"^^ . "1"^^ . "On the complexity of cake cutting"@en . . "RIV/67985840:_____/07:00096351" . "Woeginger, G. J." . "Sgall, Ji\u0159\u00ED" . . "213;220" . . "[933CF68E905B]" . "On the complexity of cake cutting" . "439332" . "\u010Cl\u00E1nek prezentuje doln\u00ED odhad na po\u010Det \u0159ez\u016F p\u0159i d\u011Blen\u00ED zdroj\u016F"@cs . "RIV/67985840:_____/07:00096351!RIV08-AV0-67985840" . . "O slo\u017Eitosti d\u011Blen\u00ED zdroj\u016F"@cs . . . "4" . "1572-5286" . "fair division; complexity"@en . "On the complexity of cake cutting"@en . . . "On the complexity of cake cutting" . "In the cake cutting problem, n>2 players want to cut a cake into n pieces so that every player gets a \u00B4fair\u00B4 share of the cake by his/her own measure. We prove that in a certain, natural cake cutting model, every fair cake division protocol for n players must use .OMEGA.(nlogn) cuts and evaluation queries in the worst case. Up to small constant factor, this lower bound matches a corresponding upper bound in the same model obtained by Even and Paz, from 1984" . "P(1M0545), P(IAA1019401), Z(AV0Z10190503)" . . . . . . "NL - Nizozemsko" . "2" . "In the cake cutting problem, n>2 players want to cut a cake into n pieces so that every player gets a \u00B4fair\u00B4 share of the cake by his/her own measure. We prove that in a certain, natural cake cutting model, every fair cake division protocol for n players must use .OMEGA.(nlogn) cuts and evaluation queries in the worst case. Up to small constant factor, this lower bound matches a corresponding upper bound in the same model obtained by Even and Paz, from 1984"@en . . . . . "2"^^ . "Discrete Optimization" .