Document Type

Technical Report

Department

Computer Science and Engineering

Publication Date

2006-01-01

Filename

wucse-2006-26.pdf

Technical Report Number

WUCSE-2006-26

Abstract

Given a positive integer k and a complete graph with non-negative edge weights that satisfy the triangle inequality, the remote-clique problem is to find a subset of k vertices having a maximum-weight induced subgraph. A greedy algorithm for the problem has been shown to have an approximation ratio of 4, but this analysis was not shown to be tight. In this thesis, we present an algorithm called d-Greedy Augment that generalizes this greedy algorithm (they are equivalent when d = 1). We use the technique of factor-revealing linear programs to prove that d-Greedy Augment, which has a running time of O(kdnd ), achieves an approximation ratio of (2k ? 2)/(k + d ? 2). Thus, when d = 1, d-Greedy Augment achieves an approximation ratio of 2 and runs in time O(kn), making it the fastest known 2-approximation for the remote-clique problem. Beyond proving this worst-case result, we also examine the behavior of d-Greedy Augment in practice. First, we provide some theoretical results regarding the expected case performance of d-Greedy Augment on random graphs, and second, we describe data from some experiments that test the performance of d-Greedy Augment and related heuristics.

Comments

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

Download

Share

COinS