Questions tagged [partitions]
A partition or partitioning of a set A is a collection of disjoint sets whose union yields A.
0
votes
1answer
72 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
25 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
125 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
251 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
17 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
100 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
44 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
0answers
132 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
53 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
54 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
63 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
55 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
52 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
308 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
48 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
715 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
30 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
247 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
73 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
46 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
181 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
54 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
59 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 $...
3
votes
1answer
62 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
56 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
65 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
73 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 ...
3
votes
1answer
182 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
307 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
108 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
32 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 ...
2
votes
2answers
139 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
279 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
264 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
32 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
163 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
117 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
114 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
311 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 ...
2
votes
1answer
26 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\}$ ...
2
votes
1answer
172 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
158 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
562 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 ...
1
vote
1answer
165 views
What's the purpose of Karger's algorithm?
Suppose I'm given an undirected graph and two nodes: v and u.
If I understand Karger's algorithm correctly, it's used to find a minimum cut of a graph, not the ("the" because there is only one for ...
-3
votes
1answer
209 views
How to prove this “np-complete” problem?
I have a problem that I need to prove its np-completness: My original question
I need to reduce it from some problem, i´m trying to do it from some other than knapsack, that´s why I ask again. I need ...
5
votes
1answer
99 views
Partitioning an undirected, unweighted, square planar graph paths that join certain pairs of nodes
I am trying to find a way to efficiently solve a puzzle that I play a lot by turning it into a graph partitioning problem (which is basically is in its actual form). I know that generally, graph ...
3
votes
1answer
142 views
Bounded bin covering problem
This all seems fairly related to the knapsack problem, bin packing and the subset sum problem, but I can't find the appropriate problem name.
I have a multiset $S$ of $n$ (not necessarily unique) ...
2
votes
1answer
63 views
Compact, reversible mapping from set partitions of length k to integers
Given a set $S$ of length $n$, I'm looking to map all the $k$-length partitions of $S$ onto the set of integers such that these integers are as close to 0 as possible. Ideally the range would be $\...
