# Questions tagged [partitions]

A partition or partitioning of a set A is a collection of disjoint sets whose union yields A.

143 questions
Filter by
Sorted by
Tagged with
148 views

### min cut for multiple partitions

So I am familiar with the standard minimum cut problem in which the goal is to find the smallest possible set of edges in a graph such that, upon their removal, we have two nonempty, disjoint ...
185 views

### Non-standard partition problem

I've been writing codes to solve a standard partition problem. I've investigated brute force, greedy, Karmarkar-Karp and complete Karmarkar-Karp algorithms. Standard partition problem: divding a ...
168 views

### Reduction from 3-Partition to a cutting problem

My problem is the following: Input: a set of $m$ non-negative integers $\{b_1,...,b_m\}$ and a parameter $n$ with $n<m$. Output: $n$ sets of 3 numbers Task: Cut the $b_i$'s into $3n$ integers such ...
93 views

726 views

### Dividing a weighted planar graph into $k$ subgraphs with balanced weight

I've been looking for an algorithm which divides an undirected, weighted, planar and simple graph into $k$ disjoint subgraphs. Here, the graph is sparse, $k$ is fixed, and there are no negative edge ...
483 views

### Partition problem with distinct integers

The partition problem is a well-known NP-complete problem. In the definitions I have seen, the input is assumed to be a multiset of integers, and we want to decide the existence of a partition into ...
867 views

### What is a compact way to represent a partition of a set?

There exist efficient data structures for representing set partitions. These data structures have good time complexities for operations like Union and Find, but they are not particularly space-...
913 views

### Fastest known algorithm for $3$-$\mathrm{Partition}$ problem

$3$-$\mathrm{Partition}$ problem is $\mathsf{NP}$-Complete in a strong sense meaning there is no pseudo-polynomial time algorithm for it unless $\mathsf{P=NP}$. I am looking for the fastest known ...
2k views

### reducing subset-sum to partition

Subset-sum: Given a list of numbers, find if a non-empty sublist has sum 0 (there's a variation where we want sum=k instead of 0, but 0 is easier for analysis) Partition: Given a list, can it be ...
644 views

### How to distribute items of varying sizes into bins of varying sizes, such that percent utilization across all bins is minimized?

I have a bunch of databases, each having different access patterns, such that each puts a different amount of load on its database cluster. I would like to distribute them around my set of database ...
2k views

### Showing a partition-like problem is NP-complete

Given a set $A=\{a_{1},a_{2},a_{3},\ldots,a_{n}\}$, then construct a set $P=\{p_{1}, p_{2}, p_{3}, \ldots , p_{n}\}$ such that $|p_{i}|=a_{i}$, and $\sum_{i = 1,}^{n}p_{i} = 0$. This problem is NP-...