An Improved Analysis for a Greedy Remote-Clique Algorithm using Factor-Revealing LPs

Authors

Benjamin E. Birnbaum, Washington University in St Louis
Kenneth J. Goldman, Washington University in St Louis

Document Type

Technical Report

Department

Computer Science and Engineering

Publication Date

2006-01-01

Filename

wucse-2006-3.pdf

Technical Report Number

WUCSE-2006-3

Abstract

Given a complete graph with nonnegative edge weights satisfying the triangle inequality and a positive integer p, the remote-clique problem is to find a subset of p vertices having a maximum-weight induced subgraph. A simple greedy algorithm for the problem has been shown to have an approximation ratio of 4, but a tight example has not been provided. In this paper, we use the technique of factor revealing linear programs to prove that this algorithm actually achieves an approximation ratio of 2, matching the best-known ratio for the problem. The greedy algorithm's running time of O(pn) makes it the fastest known 2-approximation for the remote-clique problem.

Comments

Permanent URL: http://dx.doi.org/10.7936/K7XP7346

Recommended Citation

Birnbaum, Benjamin E. and Goldman, Kenneth J., "An Improved Analysis for a Greedy Remote-Clique Algorithm using Factor-Revealing LPs" Report Number: WUCSE-2006-3 (2006). All Computer Science and Engineering Research.
https://openscholarship.wustl.edu/cse_research/180