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
0answers
26 views

Reduction from 3-partition to ABC-partition

The ABC-partition problem is a variant of 3-partition in which, instead of a single set $S$ with $3 m$ positive integers, there are three sets $A, B, C$ with $m$ positive integers in each. The goal is ...
2
votes
0answers
70 views

3-partition problem without the restriction to triplets

In the standard 3-partition problem, there are $3 m$ integers, their sum is $m T$, and they have to be partitioned into $m$ subsets of sum $T$ and size $3$. Consider the variant without the ...
2
votes
1answer
54 views

Minimum cardinality graph partition that removes specific edges

I have a computational problem that I want to solve. I'm not sure if it has already been studied in literature, or if so under what name. I'd appreciate any pointers to literature or suggestions for ...
0
votes
1answer
16 views

Multi-dimensional Knapsack with Minimum Value constraints for Dimensions

In MDK, we have a vector $W = \{W_1, W_2, ..., W_d\}$ where each element corresponds to the maximum weight for the respective dimension in the knapsack. I want to add a conditional constraint: $V = {...
2
votes
1answer
49 views

Finding all partitions of a grid into k connected components

I am working on floor planing on small orthogonal grids. I want to partition a given $m \times n$ grid into $k$ (where $k \leq nm$, but usually $k \ll nm$) connected components in all possible ways so ...
1
vote
1answer
62 views

Polynomial-Time reduction from Partition to MakeSpan

Partition Problem: Input: $A:=$ {$a_{1}, ..., a_{n} $}. $a_{i} \in \mathbb{N}$ $\forall i \in$ $\{1, \ldots, n\}$. Question: Exists a subset $A_{1} \subset A$ with: $\sum_{a_{i} \in A_{1}} a_{i} = \...
1
vote
1answer
66 views

How can I improve my algorithm for finding optimally balanced P-way partitioning of array

I have an array of $N$ weights $w_i$, say $w_i=\{4, 5, 12, 16, 3, 10, 1\}$, and I need to divide this array into $P$ partitions such that partitions are optimally balanced, i.e. that maximum sum of ...
2
votes
1answer
21 views

Partitioning tuples

Given are tuples $(a_{11},\dots,a_{1k}), (a_{21},\dots,a_{2k}), \dots, (a_{n1},\dots,a_{nk})$. We want to know if there is a partition of the tuples into two parts, so that for every coordinate $i=1,\...
1
vote
1answer
47 views

For which values of $m$ is $m$-partition hard?

Consider the following reduction: $m$-colouring to $m$-partition. Define an $m$-partition as: Given an undirected graph $G = (V, E)$ and an integer $j$. Does there exist a partition of the vertices ...
1
vote
2answers
21 views

Number partitioning targeting ratio of subset sums and equal size

I've seen a number of questions and answers related to the partitioning problem of dividing a set into 2 subsets of equal size and sum that use greedy or dynamic programming solutions to get ...
0
votes
0answers
20 views

Quicksort with lomuto partition - how many repeating elements are too many?

I know that quicksort with Lomuto's partition method faces worst case run-time $\Theta(n^2)$ when there are many repeating elements in the array. However, I'm trying to figure out - how many ...
1
vote
1answer
25 views

Computing the partition function

Are there in any relatively efficient known algorithms to compute the partition function $P(n)$ for a given $n$? What's known about the complexity class of this problem as a function of $n$? ...
2
votes
1answer
53 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
101 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
73 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
54 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
21 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 ...
6
votes
1answer
89 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
30 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
130 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
31 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
90 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
23 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
57 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
71 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
90 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
71 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
71 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
68 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
16 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
65 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$,...
4
votes
1answer
51 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
33 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
363 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
103 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
18 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
146 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
858 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
37 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
110 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
61 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
385 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
222 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
91 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
155 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
178 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 ...