Questions tagged [partitions]
A partition or partitioning of a set A is a collection of disjoint sets whose union yields A.
108
questions
0
votes
1answer
11 views
Weighted graph clustering with maximum size constraint
I'm currently trying to solve a clustering problem. I need to cluster/partition an undirected weighted graph into groups that are restricted to size n.
I have ...
2
votes
1answer
42 views
Divide grid so that each box has only one object
Is there an efficient algorithm to divide a 2D space, which contains several different sized rectangles, such that each partition has only a single object. Please see the attached image.
I have come ...
0
votes
0answers
33 views
Directed Acyclic Graph partition into minimum subgraphs with a constraint
I have this problem, not sure there is a name for it, wherein a Directed Acyclic Graph has different colored nodes. The idea is to partition it into minimum number of subgraphs with the following 2 ...
1
vote
1answer
24 views
Sequential subsequence removal with arbitrary predicate
I want to extract sub-sequences from a sequence of float values.
The "scale" and range of these values is arbitrary (as I can manipulate it at will) but the "shape" is consistent.
For a visual ...
0
votes
0answers
9 views
Evaluating clustering/partitioning quality
I'm wondering what are the most common/recognized methods to assess the quality of a clustering.
That is because I have developed a tool that can cluster/partition a network (in this case, a public ...
5
votes
1answer
53 views
NP-hardness even with perturbations
Consider the following problem, which can be called "2-SET-PARTITION":
Given two sets of positive numbers, $a_1,\ldots,a_n$ and $b_1,\ldots,b_n$, where $\sum_{i\in[n]}a_i = \sum_{i\in[n]}b_i = 2 S$,...
0
votes
0answers
22 views
Forming groups of people such that no group has two people that dislike each other
I had an assignment for the graph theory unit of my data structures course. The problem was given as follows:
Every person in a class has at least one other person that they dislike and will not ...
4
votes
1answer
39 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 ...
1
vote
0answers
14 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
27 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
48 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
508 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
33 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
127 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
355 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
105 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
205 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
64 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
60 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
70 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
60 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
56 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
486 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
56 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
860 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
36 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
320 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
87 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
63 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 ...
4
votes
0answers
269 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
57 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
79 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
71 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
73 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
67 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
83 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
209 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
332 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
118 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
38 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
173 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
364 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
363 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
201 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
159 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 ...
