# Questions tagged [partitions]

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

174 questions
Filter by
Sorted by
Tagged with
13 views

### How does this partitioning problem map to studied problems?

I have a real-world (see background below) problem wherein a set $S = \{A,B,C,D...\}$ needs to be partitioned into set $P = \{ \{A,B\},\{D\},\{E,F\},\{C,G,H\},...\}$ where $P$ is required to have the ...
• 101
60 views

### $k$-way number contiguous partitioning

Given a set $S$ of $n$ positive integers $S=\{a_1,\ldots,a_n\}$, can we partition $S$ into $k$ subsets of equal sum such that each subset has contiguous elements from $S$? Here, a contiguous subset is ...
• 109
1 vote
31 views

### Algorithm for grouping set items into ordered buckets without crossing boundaries between same set items

I'm trying to order some data in real-time (in an API call) where my item count is on the order of a few million. I'm using Go, so my pseudo code may resemble that. My input items look like this: <...
• 111
1 vote
25 views

### Graph partitioning in 2 clusters minimizing between cluster edges

I've been looking for an algorithm which divides an undirected graph into 2 subgraphs. However, unlike most existing work on graph partitioning out there (like METIS), I don't intend to obtain ...
• 11
32 views

### List of weakly NP-HARD problems

I need a list of at least 10 weakly NP-HARD problems. I already know the Knapsack problem, partition problem and subset sum problem. Please introduce other weakly NP-hard problems to me.
42 views

### Hoare's partition original method

So I was reading the Hoare's partition part of the Quicksort wiki and it says: "With respect to this original description, implementations often make minor but important variations. Notably, the ...
157 views

### Partition of two sets for multi-line fitting, NP-hard?

Given two sets of nonnegative numbers $X=\{x_1,...,x_n\}$ and $Y=\{y_1,...,y_n\}$, my problems consists in finding the partition $S \subseteq \{1,...,n\}$ and $\bar{S}=\{1,...,n\}\backslash S$ ...
• 43
20 views

### reduction from partition to N3DM or balanced 3 partition problem

I want to know how can I reduce Subset Sum or Partition problem to N3DM problem in which each set has exactly 3 elements and same sum. N3DM Problem: https://en.wikipedia.org/wiki/Numerical_3-...
• 1
59 views

### Partition a graph into connected subgraphs of 3 vertices each

We need to partition a graph into subgraphs of 3 vertices each, such that every subgraph has at least 2 edges. The problem is similar to the partition into triangles problem (which is NP-complete) but ...
• 71
326 views

### Partitioning a graph into connected pairs and triplets

We need to partition an undirected graph into connected subgraphs of size between $2$ and $k$, where $k$ is an integer. When $k=2$, the problem is equivalent to the perfect matching problem which is ...
• 71
92 views

### Does there exist an algorithm / software that finds optimal graph partition while enforcing contiguity on a subgraph?

I am interested in the traditional graph partitioning problem, which roughly speaking seeks to obtain a partition of a graph into a number of components, in which each component has about the same ...
• 121
39 views

### Partitioning a set based on a non-equivalence relation

I have a set of $n$ elements, and a binary relation between these elements. However, this is not guaranteed to be an equivalence relation. (Specifically, the elements are line segments in a plane, and ...
• 7,048
1 vote
42 views

• 161
84 views

• 23
159 views

### Is it known whether PARTITION is NP-complete via first order reductions?

The PARTITION decision problem is defined as follows (taken from COMPUTERS AND INTRACTABILITY from Garey and Johnson): Instance: A finite set $A$ and a size $s(a) \in \mathbb{Z}^{+}$ for each $a \in A$...
1 vote
1k views

### Split the given array into K subsets such that maximum sum of all subsets is minimum

Given an array of $N$ elements, $A$, and a number $K$. ($1 \leq K \leq N$) . Partition the given array into $K$ subsets (they must cover all the elements but can be noncontiguous too). The maximum ...
1 vote
32 views

### Computational Hardness of the $k$-Partition Problem with identical numbers/objects?

The $k$-Partition Problem is NP hard. I want to know if some slight modification of this problem makes it polynomially solvable. Now consider the set $S=\{a_1,\ldots,a_n\}$ of IDENTICAL numbers/...
81 views

### Partition a graph into subgraphs such that a partition contains up to X number of a particular node type

I have a DAG graph which contains two types of nodes, A and B. I am looking for a graph partitioning algorithm that can partition a graph in sub-graphs such that each sub-graph contains up to X number ...
35 views

### Partition columns into m groups to maximize absolute value sums

The Task You are given $n$ columns each of length $m$. All values are either $-1$ or $1$. Find an assignment $s$ of each of columns to 1 of $m$ groups in order to maximize the sum of all the absolute ...
• 21
102 views

### Subset sum with only two item types

Suppose we have $r$ copies of the integer $a$ and $t$ copies of the integer $b$, and a capacity $C$. We would like to find the maximum sum of the given integers, that is at most $C$. This is a special ...
• 5,730
1 vote
517 views

### Partition a set of n integers into m subsets in a way that the maximum subset sum is minimized

Let's say we have a set of n integers. I'm trying to find a way to partition this set into m subsets (empty subsets are not ...
• 153
54 views

### Upper-bounding the out-going degree of a graph

Given a graph $G=(V,E)$, I'm looking for a way to orient its edges in a way that will bound its out degree. For example, I can bound the graph's out-degree by $\approx 2\cdot a(G)$, where $a(G)$ is $G$...
• 523
1 vote
148 views

### Does an FPTAS exist for the multiple subset sum problem when m is fixed and c is not a variable?

From Wikipedia Multiple subset sum: The multiple subset sum problem (MSSP) is a generalization of the subset sum problem (SSP): given a multiset $S$ of $n$ integers, and an integer $m$, the goal is to ...
1 vote
680 views

### SUBSET SUM reduction to PARTITION

This is the PARTITION problem: Given a multiset S of positive integers, decide if it can be partitioned into two equal-sum subsets. This is the SUBSET SUM problem: Given a multiset S of integers ...
• 113
I would like to sample $n$ integers (of some fixed length, say $k$ bits) uniformly at random, and have them partitioned into two sets of equal sum. Since finding such a perfect partition (even if it ...