Approximating Almost-Sparse Instances of the Fair Densest Subgraph in Sub-Exponential Time

Abstract

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.