# Questions tagged [partitions]

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

143 questions
Filter by
Sorted by
Tagged with
51 views

### Find the minimum sum of distances between sets of points to a straight line in a plane

Given $n$ dots on a plane, such as: n couples ($x_i$,$y_i$) I would like to find a line parallel to y-axis ( $x=b$ ), such that the sum of all of the point's distances from that line will be minimal ...
38 views

### Is this solution for the Partition Problem right?

I've tried to solve the Partition Problem for 2 subsets minimizing the difference in the sum between the two subsets. I've coded the following: ...
35 views

51 views

### Maximise the value of the minimum weight intra edge

I've been doing review problems for a midterm and I came across this one problem that I haven't been able to solve. The problem essentially says that given a complete graph $G=(V,E)$ partition the ...
75 views

### If a solution to Partition is known to exist, can it be found in polynomial time?

In the Partition problem, there is a set of integers, and the goal is to decide whether it can be partitioned into two sets of equal sum. This problem is known to be NP-complete. Suppose we are given ...
221 views

### Partitioning a graph into subgraphs with overlapping nodes

I'd like to partition a graph into subgraphs with overlapping nodes. To do a simple partition into two, I could use kernighan_lin_bisection algorithm available in ...
79 views

### How to reduce the original partition problem to one of its variation?

Here's a statement of the set partition problem: The set partition problem takes as input a set $S = \{ a_1, a_2, ..., a_n \}$(all positive integers). Can $S$ be partitioned into two sets $A$ and $B$ ...
16 views

### Showing that Subset Sum Reduces to 3-Partition [duplicate]

Given a set of integers S (positive and negative, may contain duplicates) can S be divided into three disjoint subsets that all sum to the same value? Prove this problem is NP-complete. This is a ...
35 views

### Optimal partitioning of n-arrays

You're given N integer arrays. Each array can have different size and contains unique values. However same integers can be found in different arrays. The goal is to partition those arrays into K ...
23 views

### Partition graph in a way that minimizes inter-partition edges

I have a graph in which certain vertices are labeled. I need to assign labels to all of the other vertices in a way that minimizes the number of edges between different-label vertices. How can I do ...
102 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 ...
94 views

### 3-partition problem without the restriction to triplets [closed]

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 ...
59 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 ...
32 views

172 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 ...
29 views

123 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 ...
86 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 ...
42 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. ...
76 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 ...
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 ...
94 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 ...
32 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$. ...
179 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 ...
39 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 ...
99 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" ...
25 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 ...
136 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 ...
137 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 ...
141 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 ...
76 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 ...
77 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 ...
74 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 ...
19 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 ...
69 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$,...
54 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 ...
16 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 ...
43 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 ...
508 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 ...
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 ...
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 ...
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 ...
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 ...