# Questions tagged [partitions]

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

171 questions
Filter by
Sorted by
Tagged with
1 vote
27 views

### Split Bipartite Graph

I have a bipartite graph $G=(U=\{U_1, U_2,\cdots\}, V=\{V_1, V_2,\cdots\} , E)$ such that edges don't "skip" the $V$ vertices. Meaning, if edge $(U_i, V_j)$ doesn't exist, neither will edges ...
• 143
1 vote
20 views

### "Icebreaker problem": Dividing set into partitions that maximize pairwise shared memberships?

Suppose I have a set of N*L elements. I wish to generate a sequence of k partitions of size L such that I maximize the number of pairs of elements that share membership of the same partition. What ...
• 163
38 views

### proof $$L = \{ a^ib^j : i+j\equiv 4\ (mod \ 5) \}$$ is regualr using Myhill–Nerode theorem

proof that the language $$L = \{ a^ib^j : i+j\equiv 4\ (mod \ 5) \}$$ is regualr using Myhill–Nerode theorem. at the begining i thought that there are all of the reminders of 5, {0,1,2,3,4} and ...
• 115
1 vote
43 views

### How to partition N numbers into K groups with constraints on the size and sum of each group?

Suppose we are asked to assign $N$ numbers into $K$ mutually exclusive groups. The partition has to satisfy two constraints for each group. The first one is that group $k$ must contain exactly $n_k$ ...
• 13
3k views

### "partial sorting" algorithms (aka "partitioning")

Context: When trying to tame real-world datasets that contain outliers and noise, the interquartile mean is a handy tool: you sort the data, throw away the top and bottom 25% of the data and take the ...
26 views

### Partitions with subsets of limited cardinality

Is there a way to compute the number of partitions such that each set in the partition has a cardinality lower or equal to two? If yes, is there also an efficient algorithm to compute these partitions?...
• 101
1 vote
39 views

### Partition data into two sets of the same size such that the sum of the average distances is maximized

Say I have a set of strings $S=\{s_1, s_2, ..., s_N\}$, and I want to partition $S$ into two sets $S_1$ and $S_2$ equally, i.e., $||S_1|-|S_2||\leq1$. Define the difference of a set as Diff(S_k)=\...
18 views

### What makes Spectral kmeans clustering better than only Kmeans clustering?

I know that Kmeans clustering is the final step of Spectral clustering. But why is it that the previous steps involved in Spectral clustering make it a more convenient clustering approach? moreover ...
• 157
95 views

### Proof that Balanced Partition is NP-complete

In the Balanced Partition problem, there are $2m$ nonnegative integers with sum $2s$. The goal is to decide whether they can be partitioned into two subsets of $m$ integers and sum $s$. The problem is ...
• 5,664
20 views

### Is there an algorithm to efficiently generate all partitions of a set such that no cell contains fewer than k elements of the set?

I am trying to generate partitions of networks to evaluate clustering algorithms. I know that generating all partitions is infeasible (since they grow with Stirling number of the second kind which get ...
1 vote
22 views

### Proof that there isn't a $c$-additive approximation to Partition Problem

Define Partition to consist of all tuples $x_1,\ldots,x_n$ which can be divided to two groups in which the sums of the two groups are equal. Is there a proof that there isn't an additive approximation ...
138 views

### Parition a multiset of numbers into two subsets, how to maximize the sum of their medians?

Given a multiset $S$ of numbers, partition it into two subsets $S_1$ and $S_2$. How to maximize the sum of their medians? For example, the median of {1,2} is ...
• 177
18 views

### Efficient way of partitionning a set into a fixed number of parts

I am looking for a way of efficiently partitionning a set of consecutive integers in to a set where the number $K$ of parts is given. For instance, for the set {1, 2, 3, 4}, I would like the best way ...
• 435
1 vote
26 views

• 23
18 views

### Partition in a tree shaped distributed network

We are given a synchronic undirected tree shaped network, with $n$ indexed nodes. We know that there is at least one node with at least $\log_k n$ neighbors, $k>1000$, and $k$ is given. We need to ...
• 33
107 views

### Is there an FPTAS for 3-way number partitioning?

The maximization problem of the 3-way number partitioning reads as follows: given $n$ positive integers, partition them into 3 subsets such that the smallest sum is as large as possible. It is known ...
123 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 ...
1 vote
48 views

• 364
1 vote
71 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 ...
116 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 ...
• 5,664
701 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 ...
• 71
209 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$ ...
• 11
40 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 ...
28 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 ...
• 1
159 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 ...
• 5,664
101 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 ...
• 5,664
69 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 ...
• 21
83 views

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 1 answer 347 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 ... • 175 1 vote 1 answer 399 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
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 ...