Questions tagged [partition-problem]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
7
votes
1answer
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-...
0
votes
1answer
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 ...
0
votes
0answers
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 ...
6
votes
0answers
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 ...
4
votes
1answer
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 ...
8
votes
0answers
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 ...
2
votes
0answers
394 views

Post Correspondence Problem “binary” variant

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_{...
8
votes
2answers
1k views

Faster pseudo-polynomial time algorithms for PARTITION

I want to partition N given numbers (may or may not be equal) into 2 subsets such that the 2 subsets have sum as close as possible and also the cardinality of the sets are equal (if n is even) or ...

1
2