Στην άσκηση ζητείται να αναπτύξουμε αλγόριθμο με όσο το δυνατόν καλύτερο λόγο προσέγγισης για το πρόβλημα και να αποδείξουμε την ορθότητα και την πολυπλοκότητά του.
Ζητείται και να αποδείξουμε/βρούμε ακριβώς τον λόγο προσέγγισης και να δώσουμε tight example;
Επειδή ανάλογα με το πόσο καλό λόγο προσέγγισης βρίσκουμε αυξάνεται και η πολυπλοκότητα της απόδειξης.
πχ. ένας άπληστος αλγόριθμος που σκέφτηκα είδα ότι υπάρχει και στην βιβλιογραφία, και οι αποδείξεις tight φράγματος της βιβλιογραφίας για το max και min αντίστοιχα είναι αρκετά μεγάλες.