# Questions tagged [partition-problem]

The tag has no usage guidance.

58 questions
Filter by
Sorted by
Tagged with
898 views

### K-Clustering of a Graph maximizing intra-cluster weights?

I would like to know if the following problem has already been studied, and if so how is it called. In particular I'm interested in approximability results. Input: A complete graph G with non-...
1k views

### Graph building with weighted nodes

I have a set of nodes which can be connected together through arcs. Every node has an associated value, reflecting the "fitness" that this particular node has in the graph. I have to find the best ...
81 views

### Partitioning based on distribution

Having a set of numbers $S={s_i}$, I want to assign them to bins, $b_i$, such that the sum of items on bins follow a specific distribution. For two bins and uniform distribution, this problem is ...
657 views

### Approximation results for 3-partition

The 3-partition as defined here is a strongly NP-complete decision problem. Consider one optimization problem of 3-partition where the $m$ subsets each have at most three elements and a sum of not ...
189 views

### Set partitioning algorithm

I'm a working software engineer and I'm trying to develop some planning software. I have faced the following problem. I have some finite set $U$ of some distinct elements $e_i \in U$. I have ...
747 views

### Is this minimization problem NP-Complete?

We are given an $n \times (n + k)$ matrix $A$, with entries in GF(2), of the form $A =[I_n\ B]$, where $I_n$ is the $n \times n$ identity matrix, and $B$ has no "zero" rows or columns. The problem is ...
Bounded Post Correspondence Problem is defined as follows: given list of pairs of words $(x_1,y_1), \ldots, (x_n, y_n)$ and $K$ find sequence of indexes $i_1, \ldots, i_k$, $k \leq K$ so that \$x_{...