Instance Optimality in Adaptive Analysis by Moria Nachmany
Explore the concept of instance optimality in adaptive analysis presented by Moria Nachmany at Tel Aviv University in 2023. Learn about the goals, problems, and methodologies discussed in the session for maximizing point sets and complexity analysis.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
From Adaptive Analysis to Instance Optimality Presented by: Moria Nachmany 2023, Tel Aviv University
Agenda Agenda
Agenda Agenda
The goal The goal
Agenda Agenda
Maxima Maxima Sets Sets
Maximal: point in S that none of the other points in S dominates it in every coordinate.
The problem The problem - - Formal Formal
Agenda Agenda
Jarvis March Jarvis March
Jarvis March Jarvis March - - complexity complexity
Agenda Agenda
Grahams scan Graham s scan Sort the n points by their x-value.
Graham Graham s scan s scan Sort the n points by their x-value. The first point of this list is the point with the maximum x- value and necessarily a maximal point.
Grahams scan Graham s scan Sort the n points by their x-value. The first point of this list is the point with the maximum x-value and necessarily a maximal point. Scan each point and if it s y-value is greater than the y-value of the last point in the output it s a maximal point, otherwise it can be removed.
y x
Grahams scan Graham s scan - - complexity complexity
Comparison-Based Lower Bound Theorem - Proof Suppose we have a set of 5 points (7,2) (8,1) (5,4) (6,3) (4,5)
(4,5) (5,4) (6,3) In order to find the maximal points, we will have to sort the points according to both axis. So that in fact it is a sorting problem that takes ? ?log? time. (7,2) (8,1) time. (7,2) (6,3) (8,1) (5,4)
Graham Graham s scan vs. Jarvis March s scan vs. Jarvis March
Agenda Agenda
Marriage Before Conquest Marriage Before Conquest
Algorithm Marriage Before Conquest: Algorithm Marriage Before Conquest:
y x
Algorithm Marriage Before Conquest: Algorithm Marriage Before Conquest:
y ?? ?? x
Algorithm Marriage Before Conquest: Algorithm Marriage Before Conquest:
y ?? ?? x
Algorithm Marriage Before Conquest: Algorithm Marriage Before Conquest:
y ?? ?? x
y ?? ?? x
y ?? ?? x
Algorithm Marriage Before Conquest: Algorithm Marriage Before Conquest:
y x
Marriage Before Conquest Marriage Before Conquest - - complexity complexity
Proof Sketch Proof Sketch - - the balance case the balance case n points, h candidate points ? 2 points, 2 candidate points ? 2 points, 2 candidate points log? ? 4 points, 4 candidate points ? 4 points, 4 candidate points ? 4 points, 4 candidate points ? 4 points, 4 candidate points => O(n log h) => O(n log h)
Proof Sketch Proof Sketch - - the unbalance case the unbalance case n points, h candidate points ? 2 points, 2 candidate points ? 2 points, 1 candidate points h h ? ? + ? ? ? ? ?+ + ? ? 4 points, 1 candidate points ? 4 points, 4 candidate points = 2? ?=1 => O(n) => O(n) 1 2? = ? ? ?=1
Proof Sketch Proof Sketch in general in general n points, h candidate points ? 2 points, ? 1 candidate points ? 2 points, ? candidate points ? ?,? + ? ? ?, ? 1 => => ? ?,? = ? ? + ? => O(n log h) => O(n log h)
Lower bound - intuition Suppose we have a set of 6 points (5,3) (6,2) (8,1) (4,4) (6,3) (7,1)
(4,4) (6,3) (5,3) Each maximal point dominates the non- maximal points. Therefore, for each point we will only have to compare it against the maximal points. (6,2) (7,1) (8,1) (6,3) (5,3) (4,4) (8,1) (7,1) (6,2)
Agenda Agenda
Finer Finer- -grained parameterizations grained parameterizations
Vertical Entropy Vertical Entropy
y 5 5 2 2 0 0 1 1 x
