Questions tagged [partitions]
A partition or partitioning of a set A is a collection of disjoint sets whose union yields A.
174
questions
0
votes
0
answers
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
0
votes
1
answer
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
0
answers
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
0
answers
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
0
votes
0
answers
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.
0
votes
0
answers
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 ...
2
votes
1
answer
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
0
votes
0
answers
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
3
votes
1
answer
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
4
votes
1
answer
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
2
votes
2
answers
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
0
votes
1
answer
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
1
answer
42
views
Is deciding whether a graph admits two vertex-disjoint spanning trees of bounded size difference NP-hard?
I'd like to decide whether, given a connected graph $G = (V, E)$ and an integer $k$ as input, $G$ admits two vertex-disjoint subgraphs $T_1 = (V_1, E_1)$ and $T_2 = (V_2, E_2)$ such that $T_1$ and $...
- 737
0
votes
0
answers
24
views
Is there any upper bound for the number of ways we can partition a multiset, where each part/segment in the partition has distinct elements?
A question is asked in the below link, which asks for the number of cases we can partition a multiset, where each part/segment in the partition has distinct elements.
https://math.stackexchange.com/...
- 1
1
vote
1
answer
33
views
Reduction from $2$-Partitioning to (simple) pairwise $2$-Partitioning
I'm currently stuck showing $NP$-hardness of a problem of mine.
An instance of my problem (I call it (simple) pairwise $2$-Partitioning) is given by the following:
Given a set of tupels $B=\{(b_1,1),\...
- 161
0
votes
0
answers
84
views
Reduction from Partition problem to the same problem with the input replicated multiple times
In a variant of the Partition Problem given a multiset $S = \{a_1,\dots,a_n\}$ of positive integer with the total sum $\sum_{i=1}^n a_i = m\,T$, we want to find out if exists a partition $S_1,\dots,...
- 1
1
vote
1
answer
32
views
Minimum number of bits to codify arrays with bounded sums
I have a very big set of non-empty arrays of possibly repeated numbers sorted in a weakly-decreasing order where each number belongs to the interval $[1, 55]$ and the sum of the elements of each array ...
- 457
0
votes
1
answer
53
views
Maximal Profit of 'legal' cutting of a board
I'm facing this problem for some time now, I've tried a greedy approach yet I result to trying a DP-ish approach, only to get stuck at a standstill.
Given a board of length $n$, and an increasing ...
- 315
3
votes
1
answer
729
views
Is it possible to randomly allocate items to bins such that each distinct allocation has equal probability?
I'm trying to randomly allocate N indistinguishable items over B indistinguishable bins with unlimited capacity. Each allocation should occur with equal probability. An allocation identifies the ...
- 161
1
vote
1
answer
133
views
The modularity difference in Louvain algorithm for community detection in graphs
I am interested in the formula of modularity difference between two partitions considered in the Louvain algorithm for community detection in graphs. I give a formal expression of this question below.
...
- 625
1
vote
0
answers
42
views
Minimize sum of products of partition [closed]
I have a set of positive integer numbers $A = \{a_1,...,a_N\}$ and I need to find a partition of $A$ into two sets, such that the sum of their products is minimal, i.e.,
$$
\min_{X,Y : X \cup Y = A} \...
- 11
4
votes
1
answer
144
views
Can almost equal partition problem be solved in polynomial time?
Given a list of positive integers with sum $s$, decide if there is a subset with sum $0.5s$. This is the well-known PARTITION problem, which is NP-hard.
What about the following: Given a list of ...
- 81
0
votes
1
answer
85
views
Complexity of the partition problem with additional constraint
The "classical" partition problem asks whether a given multiset $S$ of positive integers can be partitioned into two subsets $S_1$ and $S_2$ such that the sum of the numbers in $S_1$ equals ...
1
vote
1
answer
32
views
Set partitions into singletons or pairs
I am trying to build an algorithm to compute the partition of a set into singletons or pairs for a set of cardinality 16. I am doing it in MATLAB and came up with codes that either run forever or ...
- 113
1
vote
0
answers
45
views
Split Bipartite Graph
I have a bipartite graph $G=(U=\{U_1, U_2,\cdots\}, V=\{V_1, V_2,\cdots\} , E)$ such that edges don't "skip" the $V$ vertices. Meaning, if edge $(U_i, V_j)$ doesn't exist, neither will edges ...
- 143
1
vote
0
answers
22
views
"Icebreaker problem": Dividing set into partitions that maximize pairwise shared memberships?
Suppose I have a set of N*L elements. I wish to generate a sequence of k partitions of size L such that I maximize the number of pairs of elements that share membership of the same partition. What ...
- 163
1
vote
1
answer
413
views
How to partition N numbers into K groups with constraints on the size and sum of each group?
Suppose we are asked to assign $N$ numbers into $K$ mutually exclusive groups. The partition has to satisfy two constraints for each group. The first one is that group $k$ must contain exactly $n_k$ ...
- 13
19
votes
5
answers
4k
views
"partial sorting" algorithms (aka "partitioning")
Context:
When trying to tame real-world datasets that contain outliers and noise, the interquartile mean is a handy tool: you sort the data, throw away the top and bottom 25% of the data and take the ...
- 435
0
votes
1
answer
40
views
Partitions with subsets of limited cardinality
Is there a way to compute the number of partitions such that each set in the partition has a cardinality lower or equal to two? If yes, is there also an efficient algorithm to compute these partitions?...
- 113
1
vote
1
answer
51
views
Partition data into two sets of the same size such that the sum of the average distances is maximized
Say I have a set of strings $S=\{s_1, s_2, ..., s_N\}$, and I want to partition $S$ into two sets $S_1$ and $S_2$ equally, i.e., $||S_1|-|S_2||\leq1$.
Define the difference of a set as
$$Diff(S_k)=\...
- 13
3
votes
2
answers
487
views
Proof that Balanced Partition is NP-complete
In the Balanced Partition problem, there are $2m$ nonnegative integers with sum $2s$. The goal is to decide whether they can be partitioned into two subsets of $m$ integers and sum $s$.
The problem is ...
- 5,730
0
votes
0
answers
27
views
Is there an algorithm to efficiently generate all partitions of a set such that no cell contains fewer than k elements of the set?
I am trying to generate partitions of networks to evaluate clustering algorithms. I know that generating all partitions is infeasible (since they grow with Stirling number of the second kind which get ...
- 11
1
vote
0
answers
43
views
Proof that there isn't a $c$-additive approximation to Partition Problem
Define
Partition to consist of all tuples $x_1,\ldots,x_n$ which can be divided to two groups in which the sums of the two groups are equal.
Is there a proof that there isn't an additive approximation ...
4
votes
1
answer
298
views
Parition a multiset of numbers into two subsets, how to maximize the sum of their medians?
Given a multiset $S$ of numbers, partition it into two subsets $S_1 $ and $S_2$.
How to maximize the sum of their medians? For example, the median of {1,2} is ...
- 177
0
votes
0
answers
23
views
Efficient way of partitionning a set into a fixed number of parts
I am looking for a way of efficiently partitionning a set of consecutive integers in to a set where the number $K$ of parts is given.
For instance, for the set {1, 2, 3, 4}, I would like the best way ...
- 465
1
vote
1
answer
36
views
Similar problem to Subset Sum?
I've been trying to search for a problem which I think could be similar to Subset Sum.
The definition of the problem would be as follows:
Given k $\in$ $\mathbb{Z}$ and S = {$s_1$,...,$s_n$} s.t. $s_i ...
- 23
2
votes
0
answers
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$...
- 21
1
vote
0
answers
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 ...
- 250
1
vote
0
answers
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/...
0
votes
0
answers
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 ...
2
votes
0
answers
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
3
votes
1
answer
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
1
answer
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
2
votes
1
answer
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
0
answers
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 ...
- 127
1
vote
1
answer
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
4
votes
0
answers
80
views
How to sample a perfect partition uniformly at random?
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 ...
- 5,730
3
votes
1
answer
169
views
Partition of a $k$-partite graph to minimal number of connected sets
Let $G$ be a $k$-partite directed acyclic graph where the edges are only between two adjacent sets of vertices.
I'm trying to partition the graph to the minimal number of connected sets.
Sets $A_0, ...
- 23
0
votes
0
answers
18
views
Partition in a tree shaped distributed network
We are given a synchronic undirected tree shaped network, with $n$ indexed nodes.
We know that there is at least one node with at least $\log_k n$ neighbors, $k>1000$, and $k$ is given.
We need to ...
- 33
2
votes
1
answer
177
views
Is there an FPTAS for 3-way number partitioning?
The maximization problem of the 3-way number partitioning reads as follows:
given $n$ positive integers, partition them into 3 subsets such that the smallest sum is as large as possible. It is known ...
- 127