An O(n log n) version of the Averbakh-Berman algorithm for the robust median of a tree

dc.contributor.author	Brodal, G.	en
dc.contributor.author	Georgiadis, L.	en
dc.contributor.author	Katriel, I.	en
dc.date.accessioned	2015-11-24T17:01:44Z
dc.date.available	2015-11-24T17:01:44Z
dc.identifier.issn	0167-6377	-
dc.identifier.uri	https://olympias.lib.uoi.gr/jspui/handle/123456789/10971
dc.rights	Default Licence	-
dc.subject	minmax regret	en
dc.subject	tree median	en
dc.subject	robust optimization	en
dc.subject	set union	en
dc.subject	location	en
dc.subject	network	en
dc.title	An O(n log n) version of the Averbakh-Berman algorithm for the robust median of a tree	en
heal.abstract	We show that the minmax regret median of a tree can be found in O(n log n) time. This is obtained by a modification of Averbakh and Berman's O(n log(2) n)-time algorithm: we design a dynamic solution to their bottleneck subproblem of finding the middle of every root-leaf path in a tree. (c) 2007 Elsevier B.V. All rights reserved.	en
heal.access	campus	-
heal.fullTextAvailability	TRUE	-
heal.identifier.primary	DOI 10.1016/j.or1.2007.02.012	-
heal.journalName	Operations Research Letters	en
heal.journalType	peer reviewed	-
heal.language	en	-
heal.publicationDate	2008	-
heal.recordProvider	Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής	el
heal.type	journalArticle	-
heal.type.el	Άρθρο Περιοδικού	el
heal.type.en	Journal article	en

Αρχεία

Προβολή: 1 - 1 of 1