Αποδοτικοί προσεγγιστικοί αλγόριθμοι για στοχαστική βελτιστοποίηση και μάθηση σε αβέβαια περιβάλλοντα

Abstract

Σε αυτή την διπλωματική μελετάμε πόσο αποδοτικά μπορούμε να λύσουμε προβλήματα όπως το Σακίδιο ή το Συντομότερο μονοπάτι , στην στοχαστική τους μορφή . Μελετάμε δύο τύπους αυτών τον προβλημάτων. Indyk et al, μελέτησαν το πρόβλημα του στοχαστικού σακιδίου με διάφορες παραλλαγές και έπειτα η Nikolova μελέτησε το στοχαστικό Σύντομο μονοπάτι. Και οι δυο δείξαν ότι όταν τα βάρη ακολουθούν bernoulli κατανομή τότε υπάρχει ένας QPTAS . Εμείς σε αντίθεση δείχνουμε πως μπορείς να επεκτείνεις τον αλγόριθμο και να βελτιώσεις τα αποτελέσματα σε εναν EPTAS.Κι επίσης είδαμε πιο γενικές παραλλαγές όπως χωρίς να έχεις υπόθεση για είδος κατανομής. Στην συνέχεια μελετήσαμε την δουλειά του Gupta et al όπου δίνουν αλγόριθμους που μαθαίνουν την βέλτιστη λύση σε συνδυαστικά προβλήματα σε αβέβαιο περιβάλλον και χρησιμοποιούμε τους αλγόριθμους τους στο συντομότερο μονοπάτι για πιο γενικές συναρτήσεις κόστους.