δείτε την πρωτότυπη σελίδα τεκμηρίου στον ιστότοπο του αποθετηρίου του φορέα για περισσότερες πληροφορίες και για να δείτε όλα τα ψηφιακά αρχεία του τεκμηρίου*
Fast parallel approximations of the maximum weighted cut problem through derandomization
(EN)
Given a graph with positive integer edge weights one may ask whether there exists an edge cut whose weight is bigger than a given number. This problem is NP-Complete. We present here an approximation scheme in NC which provides tight upper bounds to the proportion of edge cuts whose size is bigger than a given number. Our technique is based on the method to convert randomized algorithms into deterinistic ones, introduced by [Luby, 85 and 88]. The basic idea of those methods is to replace an exponentially large sample space by one of polynomial size. Our work examines the statistical distance of random variables of the small sample space to corresponding variables of the exponentially large space, which is the space of all edge cuts taken equiprobably.
(EN)
*Η εύρυθμη και αδιάλειπτη λειτουργία των διαδικτυακών διευθύνσεων των συλλογών (ψηφιακό αρχείο, καρτέλα τεκμηρίου στο αποθετήριο) είναι αποκλειστική ευθύνη των αντίστοιχων Φορέων περιεχομένου.
Βοηθείστε μας να κάνουμε καλύτερο το OpenArchives.gr.
