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{1}{3}$-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