Questions tagged [partitions]
A partition or partitioning of a set A is a collection of disjoint sets whose union yields A.
122
questions
2
votes
1answer
38 views
How to prove the NP-completeness of MOD-PARTITION
MOD-PARTITION: Given a set of integers $A={a_1,...,a_n}$, their weights $w = \{w_1, w_2, \dots, w_n\}$ and the number $k$, does there exist a subset $X$ of $A$ such that: $(\sum_{x \in X} w(x) * x) \...
1
vote
0answers
88 views
Prove Product Partition is NP-complete in the strong sense
I am trying to understand how to prove that the Product Partition problem is NP-complete in the strong sense. The problem is similar to the normal Partition problem, except in this case the product of ...
2
votes
1answer
60 views
Schedule X Classes In N Classrooms
I would really appreciate any thought on this, or under which category does this problem fall (Interval scheduling, Interval partitioning,...)
I am really out of thoughts
I have X number of classes ...
1
vote
1answer
38 views
Amount of k-partitions of a number
I'm stuck on writing an algorithm for getting the amount of distinct partitions for a number $n$ with the partition being size $k$. It's important that there isn't any repetition in the partitions.
...
0
votes
1answer
41 views
Does Kernighan-Lin algorithm guarantee its partitions to be a connected graph?
Currently I am experimenting with Kernighan-Lin algorithm to produce coarse representation of navigation mesh for hierarchical pathfinding.
Based on the use case, my requirement is that partitions ...
0
votes
0answers
20 views
Find the max partition of unique elements where each element corresponds to the set pool containing that element
Given a list of sets:
a b c -> _
c d -> d
b d -> b
a c -> a
a c -> c
The objective is to find the max partition of unique elements with ...
3
votes
1answer
47 views
Partitioning bag of sets such that each set in a group has a unique element
Suppose I have a bag (or multiset) of sets $S = \{s_1, s_2, \dots, s_n\}$ and $\emptyset\notin S$. I wish to partition $S$ into groups of sets such that within each group each set has at least one ...
3
votes
1answer
22 views
Smoothed analysis of the Partition problem
I am studying smoothed analysis and trying to apply it to the Partition decision problem: given $n$ real numbers with a sum of $2 S$, decide whether there exists a subset with a sum of exactly $S$.
...
2
votes
1answer
87 views
Conditions under which the 3-partition problem is not strongly NP-complete?
I'm a bit confused about the 3-partition problem. More specifically I'm confused about this from the Wikipedia article:
Let B denote the (desired) sum of each subset Si, or equivalently, let the ...
3
votes
1answer
27 views
Computing minimum partition of poset of $N$ intervals into chains in $o(N^{2.5})$ time?
Consider a set $P$ of $N$ intervals $\{I_i = (l_i, r_i)\}$ partially ordered according the standard interval order: $I_i < I_j$ iff $r_i \le l_j$.
I want to find a minimum cardinality partition of ...
4
votes
2answers
78 views
Equal partition up to one integer
In the partition problem, the task is to partition $n$ given integers into two subsets $A$ and $B$ with equal sum. This problem is known to be NP-hard, but it becomes easy if the "equal sum" ...
2
votes
0answers
22 views
Seeking an algorithm for finding the partition of data on an interval that maximizes the minimum fitness among the blocks
In the paper "An algorithm for optimal partitioning of data on an interval" (link) the authors describe an algorithm for partitioning data on an interval to maximize a fitness function. The fitness ...
0
votes
2answers
50 views
How to partition disagreeable people into compatible groups
We have a number of people that must be partitioned into groups, but there may be people that dislike other individuals. Partition the people into the minimum number of groups such that no person is ...
3
votes
1answer
49 views
Finding partition with maximum number of edges between sets
Given a graph (say in adjacency list form), is there an algorithm to find a partition of vertices such that the number of edges between the two sets of the partition is the maximum possible?
For ...
0
votes
1answer
64 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
69 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
60 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
2answers
53 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
14 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
63 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
35 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
48 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
15 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
30 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
322 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
49 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
1k 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
91 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
135 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
653 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
35 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
107 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
56 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
364 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
150 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
72 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
137 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
138 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 ...
2
votes
1answer
68 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
772 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
64 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 ...
2
votes
0answers
1k 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
41 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
426 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
111 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
80 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
443 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
67 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
94 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 $...
