Questions tagged [partitions]
A partition or partitioning of a set A is a collection of disjoint sets whose union yields A.
171
questions
1
vote
0
answers
27
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
20
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
votes
0
answers
38
views
proof $$ L = \{ a^ib^j : i+j\equiv 4\ (mod \ 5) \} $$ is regualr using Myhill–Nerode theorem
proof that the language
$$ L = \{ a^ib^j : i+j\equiv 4\ (mod \ 5) \} $$
is regualr using Myhill–Nerode theorem.
at the begining i thought that there are all of the reminders of 5, {0,1,2,3,4}
and ...
- 115
1
vote
1
answer
43
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
18
votes
5
answers
3k
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 ...
- 317
0
votes
1
answer
26
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?...
- 101
1
vote
1
answer
39
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
0
votes
0
answers
18
views
What makes Spectral kmeans clustering better than only Kmeans clustering?
I know that Kmeans clustering is the final step of Spectral clustering. But why is it that the previous steps involved in Spectral clustering make it a more convenient clustering approach?
moreover ...
- 157
3
votes
2
answers
95
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,664
0
votes
0
answers
20
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
22
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
138
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
18
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 ...
- 435
1
vote
1
answer
26
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
1
vote
0
answers
69
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$...
- 11
1
vote
0
answers
381
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 ...
- 128
1
vote
0
answers
22
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
23
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
33
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
76
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,664
1
vote
1
answer
90
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 ...
- 43
2
votes
1
answer
49
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$...
0
votes
0
answers
24
views
Finding all k-partitions with additional constraints
The partition problem is a very well known one. To partition an integer array into k equal sum partitions.
My problem is I want to partition them in such a way that the sum of their partitions equals ...
user144038
1
vote
0
answers
67
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 ...
0
votes
0
answers
116
views
A Variant to "Boats to Save People"
This question is a variant of LeetCode 881. Boats to Save People by removing the restriction of "each boat carries at most two people at the same time" from the original question.
Problem ...
- 1,071
1
vote
1
answer
151
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 ...
- 13
4
votes
0
answers
54
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,664
3
votes
1
answer
142
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
107
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 ...
0
votes
1
answer
123
views
Find the minimum sum of distances between sets of points to a straight line in a plane
Given $n$ dots on a plane, such as: n couples ($x_i$,$y_i$)
I would like to find a line parallel to y-axis ( $x=b$ ), such that the sum of all of the point's distances from that line will be minimal
...
- 29
1
vote
1
answer
48
views
Bounds on graph partitioning
I am trying to find some generic upper bounds on the "standard" graph partitioning problem. Say I have a graph with $|V|$ vertices and $|E|$ edges I want to partition it into two equal $N/...
2
votes
2
answers
100
views
Path graph partitioning, minimizing cut while minimizing maximum total node weight in each part
Suppose there is a path (linear) graph $G = (V, E)$ where $V = \{0, \ldots, n - 1\}$ and $E=\{(0, 1), (1, 2), \ldots, (n - 2, n - 1)\}$, with edge weights $w_e : E \to \mathbb{N}$ and vertex weights $...
- 364
1
vote
2
answers
71
views
Maximise the value of the minimum weight intra edge
I've been doing review problems for a midterm and I came across this one
problem that I haven't been able to solve. The problem essentially says
that given a complete graph $G=(V,E)$ partition the ...
3
votes
1
answer
116
views
If a solution to Partition is known to exist, can it be found in polynomial time?
In the Partition problem, there is a set of integers, and the goal is to decide whether it can be partitioned into two sets of equal sum. This problem is known to be NP-complete.
Suppose we are given ...
- 5,664
2
votes
2
answers
701
views
Partitioning a graph into subgraphs with overlapping nodes
I'd like to partition a graph into subgraphs with overlapping nodes.
To do a simple partition into two, I could use kernighan_lin_bisection algorithm available in ...
- 71
0
votes
2
answers
209
views
How to reduce the original partition problem to one of its variation?
Here's a statement of the set partition problem:
The set partition problem takes as input a set $S = \{ a_1, a_2, ..., a_n \}$(all positive integers). Can $S$ be partitioned into two sets $A$ and $B$ ...
- 11
0
votes
0
answers
40
views
Optimal partitioning of n-arrays
You're given N integer arrays. Each array can have different size and contains unique values. However same integers can be found in different arrays.
The goal is to partition those arrays into K ...
0
votes
0
answers
28
views
Partition graph in a way that minimizes inter-partition edges
I have a graph in which certain vertices are labeled. I need to assign labels to all of the other vertices in a way that minimizes the number of edges between different-label vertices.
How can I do ...
- 1
3
votes
0
answers
159
views
Reduction from 3-partition to ABC-partition
The ABC-partition problem is a variant of 3-partition in which, instead of a single set $S$ with $3 m$ positive integers, there are three sets $A, B, C$ with $m$ positive integers in each. The goal is ...
- 5,664
2
votes
0
answers
101
views
3-partition problem without the restriction to triplets [closed]
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 ...
- 5,664
2
votes
1
answer
69
views
Minimum cardinality graph partition that removes specific edges
I have a computational problem that I want to solve. I'm not sure if it has already been studied in literature, or if so under what name. I'd appreciate any pointers to literature or suggestions for ...
- 21
0
votes
1
answer
83
views
Multi-dimensional Knapsack with Minimum Value constraints for Dimensions
In MDK, we have a vector $W = \{W_1, W_2, ..., W_d\}$ where each element corresponds to the maximum weight for the respective dimension in the knapsack.
I want to add a conditional constraint: $V = {...
2
votes
1
answer
347
views
Finding all partitions of a grid into k connected components
I am working on floor planing on small orthogonal grids. I want to partition a given $m \times n$ grid into $k$ (where $k \leq nm$, but usually $k \ll nm$) connected components in all possible ways so ...
- 175
1
vote
1
answer
399
views
Polynomial-Time reduction from Partition to MakeSpan
Partition Problem:
Input: $A:=$ {$a_{1}, ..., a_{n} $}. $a_{i} \in \mathbb{N}$ $\forall i \in$ $\{1, \ldots, n\}$.
Question: Exists a subset $A_{1} \subset A$ with: $\sum_{a_{i} \in A_{1}} a_{i} = \...
- 11
1
vote
1
answer
409
views
How can I improve my algorithm for finding optimally balanced P-way partitioning of array
I have an array of $N$ weights $w_i$, say $w_i=\{4, 5, 12, 16, 3, 10, 1\}$, and I need to divide this array into $P$ partitions such that partitions are optimally balanced, i.e. that maximum sum of ...
- 13
2
votes
1
answer
36
views
Partitioning tuples
Given are tuples $(a_{11},\dots,a_{1k}), (a_{21},\dots,a_{2k}), \dots, (a_{n1},\dots,a_{nk})$. We want to know if there is a partition of the tuples into two parts, so that for every coordinate $i=1,\...
- 21
1
vote
1
answer
52
views
For which values of $m$ is $m$-partition hard?
Consider the following reduction: $m$-colouring to $m$-partition.
Define an $m$-partition as: Given an undirected graph $G = (V, E)$ and an integer $j$. Does there exist a partition of the vertices ...
- 23
1
vote
2
answers
148
views
Number partitioning targeting ratio of subset sums and equal size
I've seen a number of questions and answers related to the partitioning problem of dividing a set into 2 subsets of equal size and sum that use greedy or dynamic programming solutions to get ...
- 11
2
votes
1
answer
94
views
Computing the partition function
Are there in any relatively efficient known algorithms to compute the partition function $P(n)$ for a given $n$? What's known about the complexity class of this problem as a function of $n$?
...
