Παρακαλώ χρησιμοποιήστε αυτό το αναγνωριστικό για να παραπέμψετε ή να δημιουργήσετε σύνδεσμο προς αυτό το τεκμήριο: http://artemis.cslab.ece.ntua.gr:8080/jspui/handle/123456789/19399
Τίτλος: Approximating Almost-Sparse Instances of the Fair Densest Subgraph in Sub-Exponential Time
Συγγραφείς: Δορκοφίκης, Ιωάννης
Φωτάκης Δημήτριος
Λέξεις κλειδιά: approximation
προσέγγιση
exhaustive sampling
εξαντλητική δειγματοληψία
randomized rounding
randomized rounding
linear programming
γραμμικός προγραμματισμός
fairness
δικαιοσύνη
sub-exponential time
υποεκθετικός χρόνος
Ημερομηνία έκδοσης: 29-Οκτ-2024
Περίληψη: This thesis studies the approach introduced in (Arora, Karger, Karpinski, JCSS 99) to approximate dense instances of many important NP-hard problems, including maximum cut, maximum k-satisfiability and densest k-subgraph, and presents some of its extensions. By dense instances we mean those where the number of constraints (edges) is large relative to the number variables (vertices). The technique is based on the idea of exhaustive sampling: Select a small subset of vertices at random, “guess” their placement in the optimal solution by trying every possible placement and using this information determine where the rest of the vertices should be placed. By applying linear programming techniques in addition to randomized rounding, they develop a PTAS for approximating integer programs where the objective function and the constraints are “dense”, smooth, constant-degree polynomials. The framework is extended in (Fotakis, Lampis, Paschos, STACS 2016), where they use sub-exponential time to provide an (1−ε)-approximation for such polynomial integer programs while relaxing the denseness requirement. They show that increasing the size of the random sample and therefore the running time of the algorithm allows it to handle instances that are a lot less dense, while maintaining an approximation guarantee of (1 − ε). In this work, we show that this extension can be applied to give a sub-exponential (1 − ε)-approximation algorithm for “almost sparse” instances of the fair densest subgraph problem, where we have additional fairness constraints, thus demonstrating the flexibility of this technique.
URI: http://artemis.cslab.ece.ntua.gr:8080/jspui/handle/123456789/19399
Εμφανίζεται στις συλλογές:Διπλωματικές Εργασίες - Theses

Αρχεία σε αυτό το τεκμήριο:
Αρχείο Περιγραφή ΜέγεθοςΜορφότυπος 
fair_densest_subgraph.pdf694.26 kBAdobe PDFΕμφάνιση/Άνοιγμα


Όλα τα τεκμήρια του δικτυακού τόπου προστατεύονται από πνευματικά δικαιώματα.