Tag Archives: Difficulty 3

Clustering

I feel a little silly I didn’t come up with this one myself.

The problem: Clustering.  This is problem MS9 in the appendix.

The description: Given a complete weighted graph G=(V,E), with a positive weight d(i,j) for each edge eij, and two positive integers K and B.  Can we partition V into K (or less) disjoint sets V1..Vk such that within each Vi, all edges that stay within the partition cost B or less?

Example: Here is a graph:

If K=2, and B=2, we could have the sets {A,C} and {B,D} as a legal cluster.  But if  K=2 and B=1, we will not be able to solve the problem.  For example, we might want to have the edges (A,B) and (A,D) in the same cluster, but that would require us also to consider the edge (B,D), which is larger than 1.

Reduction: Brucker’s paper introduces the problem using a graph, like I did above. (G&J talk about points and distances), His reduction is from Graph Coloring.

Suppose we have a coloring graph G.  We build a new graph G’ such that the weight of an edge in G’ is 1 if it did not appear in G, and its weight is 2 if it did appear in G.  Then we set out K = the K of the coloring problem (3 for 3-coloring), and B = 2.  A partition of the vertices into 3 sets where each set has no weight-2 edges is exactly a legal coloring.

Difficulty: 3.  I do think the graph terminology helps to make the problem more understandable.

Protected: Alternating Hitting Set

This content is password protected. To view it please enter your password below:

Protected: Quantified Boolean Formulas

This content is password protected. To view it please enter your password below:

Protected: Integer Programming

This content is password protected. To view it please enter your password below:

Protected: Three-Way Matching of Integers

This content is password protected. To view it please enter your password below:

Protected: Knapsack

This content is password protected. To view it please enter your password below:

Protected: Sequencing to Minimize Tardy Tasks, Sequencing to Minimize Tardy Task Weight

This content is password protected. To view it please enter your password below:

Protected: Sequencing With Release Times and Deadlines

This content is password protected. To view it please enter your password below:

Protected: Non-Circular Satisfiability

This content is password protected. To view it please enter your password below:

Protected: Conjunctive Boolean Query

This content is password protected. To view it please enter your password below: