Questions tagged [partitions]
A partition or partitioning of a set A is a collection of disjoint sets whose union yields A.
177
questions
0
votes
1
answer
25
views
Shortest paths in $k$-partite DAG
Let
$D(V, A)$ be a $k$-partite DAG;
$P = \{ p_k : 1 \leqslant k \leqslant |P| \}$ such that $p_k \cap p_l = \emptyset$, $\forall k,l : k \neq l$, and $\bigcup_{1 \leqslant k \leqslant |P|} p_k = V$ ...
2
votes
1
answer
36
views
Optimally partitioning the reciprocals of the first n integers
Do we know anything about the hardness of the optimization version of the multiway number partitioning problem when the set of numbers to partition consists of the reciprocals of the first $n$ ...
2
votes
1
answer
62
views
Covering a graph with M cliques maximizing total edges weight
I am working on a problem that involves distributing a set of N supplements across a predefined number of meals (M) in a way that maximizes the total number of positive interactions and minimizes ...
2
votes
1
answer
46
views
NP-hardness of partitioning into k sets
Given a multiset $S$ of positive integers and a fixed positive integer $k$, can $S$ be partitioned into $k$ parts with equal sum?
For $k = 2$, this is the well-known Partition problem. For general $k$,...
2
votes
0
answers
27
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 ...
0
votes
1
answer
63
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 ...
1
vote
0
answers
38
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:
<...
1
vote
0
answers
37
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 ...
0
votes
0
answers
38
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
64
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
160
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$ ...
0
votes
0
answers
21
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-...
3
votes
1
answer
68
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 ...
4
votes
1
answer
342
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 ...
3
votes
2
answers
107
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 ...
0
votes
1
answer
45
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 ...
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 $...
0
votes
0
answers
25
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
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),\...
1
vote
1
answer
33
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 ...
0
votes
1
answer
57
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 ...
3
votes
1
answer
749
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 ...
1
vote
1
answer
152
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.
...
1
vote
0
answers
45
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} \...
4
votes
1
answer
158
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 ...
0
votes
1
answer
107
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
33
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 ...
1
vote
0
answers
46
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 ...
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 ...
1
vote
1
answer
470
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$ ...
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 ...
0
votes
1
answer
42
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?...
1
vote
1
answer
54
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)=\...
3
votes
2
answers
555
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 ...
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 ...
1
vote
0
answers
45
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
299
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 ...
0
votes
0
answers
27
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 ...
1
vote
1
answer
38
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 ...
2
votes
0
answers
167
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
0
answers
2k
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
0
answers
36
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
103
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 ...
3
votes
1
answer
108
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 ...
1
vote
1
answer
623
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 ...
2
votes
1
answer
55
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$...
1
vote
0
answers
157
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
1
answer
720
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 ...
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 ...