MPI-INF Logo
Campus Event Calendar

Event Entry

What and Who

An efficient data structure for finding Pareto-optimal points (Bachelor thesis)

Julian Dörfler
Max-Planck-Institut für Informatik - D1
AG1 Mittagsseminar (own work)
AG 1  
AG Audience
English

Date, Time and Location

Thursday, 22 February 2018
13:00
30 Minutes
E1 4
024
Saarbrücken

Abstract

We present a new data structure for maintaining a set of n d-dimensional points with insertion and deletion in time O(lg^{d-1}(n) lg lg(n)) and querying for the set of Pareto-maximal points in time O(k^{floor(d/2)} lg^{d-1}(n) lg lg(n)) where k denotes the number of Pareto-maximal points. We also present another version with update time O(n) and query time O(k).

Contact

Karl Bringmann
--email hidden
passcode not visible
logged in users only

Karl Bringmann, 02/08/2018 14:18
Karl Bringmann, 02/01/2018 18:30 -- Created document.