# Questions tagged [partition-problem]

The tag has no usage guidance.

60 questions
Filter by
Sorted by
Tagged with
96 views

### A k-approximation to k-way number partitioning

The $k$-way number partitioning problem accepts as input a multiset $S$ of positive numbers, and returns a partition of $S$ into $k$ subsets such that the subset sums are as nearly-equal as possible, ...
124 views

### Uniformly sampling or counting connected graph partitions with any number of blocks

Question: Is it possible to uniformly sample in polynomial time from the set of all connected partitions of a graph? Or is there a JVV type argument that proves this to be NP-hard? To clarify: By a ...
104 views

### 3-partition problem without the restriction to triplets

In the standard 3-partition problem, there are $3 m$ integers, their sum is $m T$, and they have to be partitioned into $m$ subsets of sum $T$ and size $3$. Consider the variant without the ...
109 views

582 views

### A partition problem in which some numbers may be cut

In the standard partition problem, we are given some numbers whose sum is $2s$ and have to decide whether they can be partitioned into two subset whose sum is $s$. It is known to be NP-hard. However,...
228 views

### A partition problem with order constraints

In the OrderedPartition problem, the input is two sequences of $n$ positive integers, $(a_i)_{i\in [n]}$ and $(b_i)_{i\in [n]}$. The output is a partition of the ...
562 views

### Is this partition problem strongly NP-complete?

Some computational problems have variants that appear to be harder. For instance, Graph Automorphism (GA) problem has quasi-polynomial time algorithm ( by Babai's Graph Isomorphism result) while the ...
66 views

284 views

### Partition refinement in transition state systems (bisimulation contraction)

I am trying to understand bisimulation contraction of Kripke models. I have read these lecture slides and this Wikipedia page, but I still don't fully understand it. I can understand that the two ...
398 views

910 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-...
2k views

### DAG partitioning for parallel computing

Consider a set of processes ($P=\{p_1, p_2,\dots, p_n \}$) and their data dependencies. Each process $p_i$ has an execution runtime which is denoted by $d_i$. We are interested to parallelize these ...
401 views

### Partitioning a matrix into equal-sized regions: finding the maximum

I am facing the following research problem. We are given a matrix $M[1..p,1..p]$ of elements such that: each element has value in the range $[0, \frac 1 j]$, $j <= p$, $j$ is given, the sum of all ...
I think this should be a famous problem but I could not find its name. I have $n$ jobs with size $s_i$ that are offered at time $t_i$ and $k$ machines. How can I assign jobs to machines to minimize ...