Questions tagged [partitions]

A partition or partitioning of a set A is a collection of disjoint sets whose union yields A.

Filter by
Sorted by
Tagged with
2
votes
1answer
63 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
832 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 ...
1
vote
1answer
294 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
95 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)$ Output: YES ...
1
vote
1answer
172 views

Is this an $NP$-complete problem: Product-2-Partition

I want to prove the NP-hardness of some problem P in scheduling theory. I was trying with Partition, 3-Partition and Subset product, But neither was successful. Now, I can reduce a problem, say ...
2
votes
1answer
213 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
70 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
860 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
76 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
48 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
532 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
121 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 an ...
1
vote
0answers
91 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
599 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
75 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
99 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
138 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
99 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
75 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
131 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
308 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
2answers
739 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
139 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
66 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
402 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
554 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 ...
3
votes
1answer
878 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
37 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
422 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
207 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
175 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
512 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
30 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
350 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
243 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
2k 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
2k 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
216 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 ...
-2
votes
1answer
498 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 ...
6
votes
1answer
117 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
188 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
78 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 $\...
2
votes
1answer
6k views

What exactly (and precisely) is “offset”?

Just like my previous question concerning 'hash'; what exactly is an (or the) "offset?" Is it a value or data type? Or is it an address location? I have heard it used in different contexts within the ...
2
votes
0answers
173 views

Reducing partition to a partition where sum(partition1) = 3 times sum(partition2)

Given the following NP-complete problem: PARTITION Input: A list of positive integers $a_1, a_2, \dots, a_n$. Question: Can the list be partitioned into $2$ parts, $A_1$ and $A_2$, such ...
2
votes
1answer
198 views

3-partition problem: why $b/4 < x_i < b/2$?

Why does the definition of the 3-partition problem contain the condition $$\frac{B}{4}<x_i<\frac{B}{2}?$$ I don't understand why leaving out this condition changes the 3-partition problem.
2
votes
0answers
141 views

min cut for multiple partitions

So I am familiar with the standard minimum cut problem in which the goal is to find the smallest possible set of edges in a graph such that, upon their removal, we have two nonempty, disjoint ...
1
vote
0answers
183 views

Non-standard partition problem

I've been writing codes to solve a standard partition problem. I've investigated brute force, greedy, Karmarkar-Karp and complete Karmarkar-Karp algorithms. Standard partition problem: divding a ...
0
votes
0answers
166 views

Reduction from 3-Partition to a cutting problem

My problem is the following: Input: a set of $m$ non-negative integers $\{b_1,...,b_m\}$ and a parameter $n$ with $n<m$. Output: $n$ sets of 3 numbers Task: Cut the $b_i$'s into $3n$ integers such ...
1
vote
0answers
89 views

DISTINCT 3-PARTITION with all integers between $B/4$ and $B/2$

In the definition of 3-PARTITION of Garey&Johnson, the instance is a set of $3m$ integers such that the sum of all these integers is $mB$ and such that each integer is strictly between $B/4$ and $...