Approximation Algorithms for Perfect Fair-Triangle Packing

Abstract

In this paper, we study the {\em perfect fair-triangle packing} problem (abbreviated as PFTP), which incorporates the fairness criterion from {\em fair clustering} into the {\em maximum-weight triangle packing} problem. Specifically, the input is an edge-weighted complete graph $G = (V, E)$ with $|V| = 3n$, where each vertex is colored red or blue. A {\em fair triangle} is a triangle containing vertices of both colors. PFTP asks for a partition of $V$ into $n$ fair triangles such that the total edge weight is maximized. To the best of our knowledge, this is the first paper to study PFTP. PFTP is NP-hard. Our main contributions are a deterministic $\frac 13$-approximation algorithm running in $O(n^3)$ time and an improved randomized $(\frac {16}{47}-\epsilon)$-approximation algorithm running in $O(n^4)$ time, where $\epsilon>0$ is a fixed small constant. The deterministic algorithm is matching-based whereas the randomized algorithm employs several additional techniques, including maximum-weight $[1, 2]$-factor, a random cycle-breaking procedure, and maximum-weight matchings. Keywords: Triangle packing; fairness; approximation algorithms; randomized algorithms