Questions tagged [partitions]
A partition or partitioning of a set A is a collection of disjoint sets whose union yields A.
3
votes
1answer
21 views
Partitioning a set so both parts have sum at least $c$ times the total sum
Let $c\in(0,1/2]$ be a constant. Given a set of positive integers with sum $S$, is there a partition into two subsets such that both subsets have sum at least $cS$?
If $c=1/2$, this is the famous ...
0
votes
0answers
12 views
Balanced $\epsilon$-separated partitioning by a hyperplane
Suppose we have $m$ points in $R^n$ and $\epsilon>0$ is a given constant. How can we find a hyperplane that the number of points that are $\epsilon$-close to it is minimum, with the constraint that ...
2
votes
1answer
22 views
Partitioning a graph with specific constraints
We have an exercise where we need to find the partitions G[V1] and G[V2] of a graph G=(V,E), that fulfill the following constraints. We also know that there exists at least one partition that fulfills ...
3
votes
2answers
38 views
Is finding Kth largest element using selection algorithm taking O(n) only if K is fixed?
Wikipedia here https://en.m.wikipedia.org/wiki/Selection_algorithm shows an algorithm using sort of quicksort.. in order to find Kth largest or smallest element taking O(n) time only on average. The ...
1
vote
1answer
47 views
Partitioning a boolean circuit for automatic parallelization
tl;dr: I have a problem where I have a Boolean circuit and need to implement it with very specific single-thread primitives, such that SIMD computation is significantly cheaper after a threshold. I'm ...
0
votes
1answer
209 views
Partition array into k subsets
We are given an array and a number K. Partition array into K subsets such that
let MaxSum be the maximum sum of among subsets.
We have to minimize summation =$$\sum_{i=1}^{k}MaxSum-sum(i) $$
Is ...
3
votes
0answers
31 views
Split a graph into 2 components with known distribution?
I'm trying to find a method to randomly split a connected planar graph $G$ into two connected components, such that the sum of the weights of vertices in each component are relatively close. (If there ...
2
votes
0answers
17 views
Is there a more commonly-used term for “multi-pivoting”?
Consider the following computational problem (or rather, task):
Given:
An array of $A$ of (not necessarily distinct) elements from a fully-ordered finite domain
An ordered sequence pivot ...
6
votes
1answer
126 views
Optimal partitioning of n-tuples
Motivation
Recently I was trying to optimize some API calls and reduced the problem to optimization of a cumulative number of identifiers across all the requests. I put some considerable effort into ...
2
votes
1answer
316 views
Solve PARTITION-INTO-THREE-SETS in pseudo-polynomial time
Let PARTITION-INTO-THREE-SETS be defined as following:
Input: Positive integers $a_1, ..., a_n$
Problem: Are there three pairwise disjoint sets $I, J, K \subseteq \{1, ..., n\}$ with $I \cup J \cup ...
1
vote
0answers
19 views
Partitioning the columns of a matrix
I thought about this problem for a while now and am not able to find a solution for it, be it a direct algorithm or a reduction to a known problem, so I'm asking here:
Suppose you have a matrix $A\in\...
1
vote
2answers
104 views
How to generate an instance for an NP_hard proof, where each element has two inputs?
I want to prove the NP-hardness of an scheduling problem. The problem seems to be NP-hard in the ordinary sense, so I am trying with the Partition Problem, precisely the Equal Cardinality Partition (...
2
votes
1answer
48 views
finding separating words (Nerode)
i have found the equivalence classes of given $R_L$ and i need to find the separating words between the equivalence classes(which i don't know how to do). would appreciate if you could explain to me ...
1
vote
1answer
174 views
Array subset division with equal sums
Today I stumbled upon a problem which looked like the partition problem but certainly is different.
Given array of positive integers, guaranteed to not be divisible into two continious subsets of ...
0
votes
1answer
57 views
Complexity of a set partition derived problem
I am stuck at the complexity of the following problem:
Given a multiset $S = \{x_1,..., x_n\}$ of $n$ integers and a natural number $k$. Can $S$ be partitioned into multisets $S_1,... S_j$ such that ...
1
vote
1answer
58 views
Karp hardness of directed monochromatic triangle problem
Monochromatic problem is a classic NP-complete problem.
Does the complexity stay NP-complete if we use directed graph?
DIRECTED MONOCHROMATIC TRIANGLE problem:
Input: A digraph $G(V,A)$
...
1
vote
1answer
69 views
Is this an $NP$-complete problem: Product-2-Partition
I want to prove the NP-hardness of my problem P in scheduling. I was trying with Partition, 3-Partition and Subset product, But neither was successful.
Now, I can reduce a problem, say PRODUCT-2-...
0
votes
1answer
58 views
Can interval partition solve by sort by different approach
The interval partitioning problem is described as follows: Given a set
{1, 2, …, n} of n requests, where ith request starts at time s(i) and
finishes at time f(i), find the minimum number of ...
1
vote
1answer
53 views
Dijkstra Partitioning Algorithm : Special Case
I have been exploring Dikstra partitioning Algorithm. Below are my given:
R = Red
W = White
B = Blue
I have this unpartitioned array.
...
0
votes
1answer
371 views
Divide an array into two sub arrays such that their sums are equal and possibly maximum
Given an array A, we should partition A into two subarrays whose sums are equal, and that maximizes this sum. We are free to omit items from the subarrays.
For example, ...
3
votes
1answer
52 views
Proving that an equal partition does not exist
We are given a set of $n$ numbers and want to know whether it can be partitioned to two sets with an equal sum.
To prove that an equal partition exists, it is sufficient to show a partition.
What is ...
1
vote
0answers
804 views
k-way set partition problem--dynamic programming solution
I was reading up on the set partition problem on this site of Wikipedia: https://en.m.wikipedia.org/wiki/Partition_problem
Among other things, they present a DP approach to solving the equal subset ...
3
votes
1answer
33 views
Is there an efficient algorithm for WEAK-PARTITION?
Suppose that we are given a list of non-zero integers $(a_1,...,a_n)$ and we want to decide whether there exist $(x_1,...,x_n)$ such that
$x_1a_1 + x_2a_2 + ... + x_na_n = 0$,
$x_i$ $\in$ $\{-1,0,1\}...
0
votes
2answers
281 views
Question regarding Hoare's partitioning scheme and a slight modification to it
This is the pseudocode on wikipedia for Hoare's partitioning scheme:
...
0
votes
2answers
78 views
Determine if an array is divisible in pairs of equal sum
I'm currently studying the time complexity of the solution provided by my teacher to this problem, and I can't understand the logic:
Let A be an unordered array of positive natural numbers. Write ...
1
vote
0answers
49 views
Polygon decomposition into minimum star-shaped polygons
As the title suggests, I'm trying to implement an algorithm to decompose a polygon into the minimum number of star-shaped polygons. I've been searching for quite some time but I can't find any ...
3
votes
0answers
217 views
Even distribution algorithm
Right now I am working on a distributed system that sends messages from single source to many nodes. It is necessary that certain messages are sent to the same node to ensure order of processing. ...
0
votes
1answer
56 views
sub-optimal but fast partition generation
I have a set of N integers that I want to partition into m subsets. I want these subsets to be well-balanced wrt some criterion say that minimize the max difference between the size of all subsets. ...
1
vote
0answers
70 views
How to enumerate all partitioning of a set to k-subsets of size at most b
I'm looking for an algorithm to generate/enumerate all possibilities for partitioning a set of size $n$ to $k$ non-empty subsets, each with size at most $b$.
More specifically, given a set $V$ where $...
2
votes
1answer
68 views
An algorithm for k-way array partitioning
I am trying to implement samplesort in MPI. The first step of samplesort is to partition the array with $n - 1$ splitters $s_1, s_2, \cdots, s_{n-1}$ into $n$ subsequences, where subsequence $i$ all ...
0
votes
0answers
64 views
$k$-partitioning problem via brute force
Given a set of non-negative integers $A = \{a_1,a_2,\dots,a_N \}$, the $k$-partitioning problem is to partition the numbers into $k$ sets $\{A_1,A_2,\dots, A_k\} $ such that the deviation:
$$ \...
4
votes
2answers
66 views
Finding the number of ways to partition $\{1,…,N\}$ into $P_1$ and $P_2$ such that $sum(P_1) = sum(P_2)$ for a given $N$
I am trying to think of how to optimize the following problem:
Let $S = \{1,2,...,N\}$. How many ways can $S$ be partitioned into non-empty subsets $P_1$ and $P_2$ such that $sum(P_1) = sum(P_2)$? I ...
2
votes
1answer
77 views
Set partition refinement with subtrees
In trying to design an algorithm, I needed a datastructure to implement a restricted kind of set partition refinement, where the sets $X$ to split on are subtrees. Specifically, given an arbitrary ...
2
votes
1answer
194 views
How to partition a tree on a fixed budget of edge cuts?
Suppose I have a tree $T=(V,E,w)$ with vertex weights $w(v)\ge 0$ for all $v\in V$. I want to partition this tree into $k+1$ trees by cutting $k$ edges such that the deviation from the mean of the ...
0
votes
1answer
315 views
Will a Greedy algorithm give a correct result for minimum partition?
Will a greedy method of picking the item that causes the largest difference each time lead to the optimal result in the minimum partition problem?
Let's say I have a set $\{a_1,a_2,a_3,...a_n\}$, now ...
2
votes
1answer
113 views
Given N sets of disjoint subsets, find a set of disjoint subsets such that it satisfies a criteria
Given a collection of sets $S_i$ of disjoint subsets $sub_i$ of a set $X$,
find a set $A$ of disjoint subsets $asub$ such that each one of these subsets is subset or equal to at most one subset in ...
0
votes
0answers
34 views
Is a minimal deviation version of set partition problem NP-Hard?
I want to know if a specific version (and what´s its name?) of the Set Partitioning Problem is NP-Complete, and if, is NP-Hard?
Problem:
Given a set of elements $e_i$ where $i={1,...,n}$, each with ...
3
votes
2answers
160 views
How to prove the NP-completeness of 15-Partition Problem
I would like to have a proof of the NP-completeness for 15-Partition Problem.
It is analogous to the well-known 3-Partition Problem. The problem is to decide whether a given multiset of integers can ...
1
vote
0answers
319 views
Exact algorithm for the partition problem
The partition problem is: given a set of numbers, find a partition to two subsets in which the difference between the sums in each subset is minimized. This optimization problem is NP-hard. The simple ...
2
votes
1answer
311 views
Algorithm for computing partitions of a set of n elements into subsets of size m
I need an algorithm that can compute all the different partitions of a set of n elements into subsets of size m.
For example for $n=4$ for the set $\{a,b,c,d\}$ and $m=2$ the output should be
$\{\{\{...
0
votes
1answer
33 views
Generating cyclical dependency graphs from k-way partitions of DAGs representing boolean networks
My question stems from something mentioned in the following paper*:
Acyclic Multi-Way Partitioning of Boolean Networks by Jason Cong, Zheng Li, and Rajive Bagrodia
Given a DAG representing a Boolean ...
2
votes
2answers
181 views
Enumerate partitions of a set with blocks of equal size
Given a set $\{1,\ldots,ck\}$, is there a known algorithm to efficiently list all partitions in with $c$ blocks of cardinality $k$?
In The art of computer programming (Fascicle 3B) by Knuth, there's ...
2
votes
1answer
148 views
A problem similar to the Bin packing problem?
I'm working on a problem that is very similar to the bin packing problem, but for me, the objective is to minimize the maximum weight given m bins. The problem statement is:
Given n items, each with ...
1
vote
0answers
122 views
Computational Geometry: what is the key of the BST in the algorithm “ Partitioning a polygon in y-monotone pieces”
The algorithm to partition a polygon into y-monotone pieces is as follows:
...
1
vote
1answer
356 views
Subset partition problem variant
Given a set S of integers, the task is to partition the set into subsets such that:
Total number of partitions is maximized
Each partition has sum at least K
This looks like a variant of bin-packing ...
1
vote
1answer
27 views
Sampling among constrained partitions
I'm working on a clustering problem and want to sample partitions (possible clustering solutions) among a set of constrained ones.
Here is the problem: I have a set of objects $O=\{o_1,\ldots,o_n\}$ ...
1
vote
1answer
183 views
Algorithm to split $n$ distinct items into $k$ nonempty unlabelled subsets
The number of ways to split $n$ items into $k$ nonempty unlabelled subsets ($k<n$) is a Stirling number of the second kind.(https://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind)
Is ...
4
votes
0answers
177 views
Graph optimization problem with multiple objectives/constraints
Let's assume that we have a directed acyclic graph $G = (V, E)$, non-negative vertex weight functions $w_a(v)$ and $w_b(v)$, and a non-negative edge weight function $t(u,v)$. We want to divide ...
1
vote
1answer
668 views
Reduction from PARTITION to 3PARTITION
I'm considering the problem (a variant of 3-PARTITION, see here) with description
Instance: Set of positive integers $A={w_{1},...,w_{n}}$ with $S(A)=\sum\limits_{i=1}^{n}w_{i} = 3m$.
...
1
vote
1answer
1k views
Approximation algorithm for the partition problem
In the partition problem we want to partition a set $S$ of positive integers into two sets $S_{1}$ and $S_{2}$ such that the sum of the integers in the two sets is the same.
The optimization version ...
