About: On the complexity of cake cutting

Facets (new session)
Description
Metadata
Settings
- owl:sameAs
- Inference Rule:

About: On the complexity of cake cutting Goto Sponge NotDistinct Permalink

An Entity of Type : http://linked.opendata.cz/ontology/domain/vavai/Vysledek, within Data Space : linked.opendata.cz associated with source document(s)

Attributes	Values
rdf:type	skos:Concept http://linked.opendata.cz/ontology/domain/vavai/Vysledek
Description	In the cake cutting problem, n>2 players want to cut a cake into n pieces so that every player gets a ´fair´ 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 In the cake cutting problem, n>2 players want to cut a cake into n pieces so that every player gets a ´fair´ 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) Článek prezentuje dolní odhad na počet řezů při dělení zdrojů (cs)
Title	On the complexity of cake cutting O složitosti dělení zdrojů (cs) On the complexity of cake cutting (en)
skos:prefLabel	On the complexity of cake cutting O složitosti dělení zdrojů (cs) On the complexity of cake cutting (en)
skos:notation	RIV/67985840:_____/07:00096351!RIV08-AV0-67985840
http://linked.open.../vavai/riv/strany	213;220
http://linked.open...avai/riv/aktivita	P Z
http://linked.open...avai/riv/aktivity	P(1M0545), P(IAA1019401), Z(AV0Z10190503)
http://linked.open...iv/cisloPeriodika	2
http://linked.open...vai/riv/dodaniDat	2008
http://linked.open...aciTvurceVysledku	Sgall, Jiří
http://linked.open.../riv/druhVysledku	J - Článek v odborném periodiku
http://linked.open...iv/duvernostUdaju	S - Úplné a pravdivé údaje nepodléhající ochraně podle zvláštních právních předpisů
http://linked.open...titaPredkladatele	Matematický ústav AV ČR, v. v. i.
http://linked.open...dnocenehoVysledku	439332
http://linked.open...ai/riv/idVysledku	RIV/67985840:_____/07:00096351
http://linked.open...riv/jazykVysledku	eng - angličtina
http://linked.open.../riv/klicovaSlova	fair division; complexity (en)
http://linked.open.../riv/klicoveSlovo	complexity fair division
http://linked.open...odStatuVydavatele	NL - Nizozemsko
http://linked.open...ontrolniKodProRIV	[933CF68E905B]
http://linked.open...i/riv/nazevZdroje	Discrete Optimization
http://linked.open...in/vavai/riv/obor	BA
http://linked.open...ichTvurcuVysledku	1 (xsd:int)
http://linked.open...cetTvurcuVysledku	2 (xsd:int)
http://linked.open...vavai/riv/projekt	Institute for Theoretical Computer Science Theories, proofs and computational complexity
http://linked.open...UplatneniVysledku	2007
http://linked.open...v/svazekPeriodika	4
http://linked.open...iv/tvurceVysledku	Sgall, Jiří Woeginger, G. J.
http://linked.open...n/vavai/riv/zamer	Rozvoj a prohloubení obecných matematických poznatků a jejich užití v dalších vědních oborech a v praxi
issn	1572-5286
number of pages	8 (xsd:int)

Faceted Search & Find service v1.16.118 as of Jun 21 2024

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3240 as of Jun 21 2024, on Linux (x86_64-pc-linux-gnu), Single-Server Edition (126 GB total memory, 9 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software