Fast parallel approximations of the maximum weighted cut problem through derandomization

dc.contributor.author	Πάντζιου, Γραμματή Ε.	el
dc.contributor.author	Σπυράκης, Παύλος	el
dc.contributor.author	Ζαρολιάγκης, Χρήστος	el
dc.date.accessioned	2015-05-29T20:07:00Z
dc.date.issued	2015-05-29
dc.identifier.uri	http://hdl.handle.net/11400/11916
dc.rights	Αναφορά Δημιουργού-Μη Εμπορική Χρήση-Όχι Παράγωγα Έργα 3.0 Ηνωμένες Πολιτείες	*
dc.rights.uri	http://creativecommons.org/licenses/by-nc-nd/3.0/us/	*
dc.source	http://link.springer.com/chapter/10.1007%2F3-540-52048-1_29	en
dc.subject	αλγόριθμοι
dc.subject	ποσοστό των κοψιμάτων ακμής
dc.subject	μέθοδοι
dc.subject	τεχνικές
dc.subject	βάρος
dc.subject	algorithms
dc.subject	proportion of edge cuts
dc.subject	methods
dc.subject	techniques
dc.subject	Weight
dc.title	Fast parallel approximations of the maximum weighted cut problem through derandomization	en
heal.type	conferenceItem
heal.classification	Επιστήμες
heal.classification	Πληροφορική
heal.classification	Science
heal.classification	Computer science
heal.classificationURI	N/A-Επιστήμες
heal.classificationURI	N/A-Πληροφορική
heal.classificationURI	http://skos.um.es/unescothes/C03532
heal.classificationURI	http://skos.um.es/unescothes/C00750
heal.keywordURI	http://id.loc.gov/authorities/subjects/sh2002006552
heal.identifier.secondary	DOI: 10.1007/3-540-52048-1_29
heal.dateAvailable	10000-01-01
heal.language	en
heal.access	forever
heal.recordProvider	Τεχνολογικό Εκπαιδευτικό Ίδρυμα Αθήνας. Σχολή Τεχνολογικών Εφαρμογών. Τμήμα Μηχανικών Πληροφορικής Τ.Ε.	el
heal.publicationDate	1989-12-19
heal.bibliographicCitation	Pantziou, G., Spirakis, P. and Zaroliagis, C. (1989) Fast parallel approximations of the maximum weighted cut problem through derandomization. Proceedings of the Ninth Conference. 405, pp.20-29. Bangalore, India: Springer Berlin Heidelberg	en
heal.abstract	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
heal.publisher	Springer Berlin Heidelberg	en
heal.fullTextAvailability	true
heal.conferenceName	Proceedings of the Ninth Conference	en
heal.conferenceItemType	full paper