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
1 vote
0 answers
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 ...
user avatar
  • 143
1 vote
0 answers
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 ...
user avatar
  • 163
-1 votes
0 answers
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 ...
user avatar
1 vote
1 answer
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$ ...
user avatar
  • 13
18 votes
5 answers
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 ...
user avatar
0 votes
1 answer
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?...
user avatar
  • 101
1 vote
1 answer
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)=\...
user avatar
0 votes
0 answers
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 ...
user avatar
  • 157
3 votes
2 answers
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 ...
user avatar
0 votes
0 answers
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 ...
user avatar
1 vote
0 answers
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 ...
user avatar
4 votes
1 answer
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 ...
user avatar
  • 177
0 votes
0 answers
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 ...
user avatar
  • 435
1 vote
1 answer
26 views

Similar problem to Subset Sum?

I've been trying to search for a problem which I think could be similar to Subset Sum. The definition of the problem would be as follows: Given k $\in$ $\mathbb{Z}$ and S = {$s_1$,...,$s_n$} s.t. $s_i ...
user avatar
  • 23
1 vote
0 answers
69 views

Is it known whether PARTITION is NP-complete via first order reductions?

The PARTITION decision problem is defined as follows (taken from COMPUTERS AND INTRACTABILITY from Garey and Johnson): Instance: A finite set $A$ and a size $s(a) \in \mathbb{Z}^{+}$ for each $a \in A$...
user avatar
1 vote
0 answers
381 views

Split the given array into K subsets such that maximum sum of all subsets is minimum

Given an array of $N$ elements, $A$, and a number $K$. ($1 \leq K \leq N$) . Partition the given array into $K$ subsets (they must cover all the elements but can be noncontiguous too). The maximum ...
user avatar
1 vote
0 answers
22 views

Computational Hardness of the $k$-Partition Problem with identical numbers/objects?

The $k$-Partition Problem is NP hard. I want to know if some slight modification of this problem makes it polynomially solvable. Now consider the set $S=\{a_1,\ldots,a_n\}$ of IDENTICAL numbers/...
user avatar
0 votes
0 answers
23 views

Partition a graph into subgraphs such that a partition contains up to X number of a particular node type

I have a DAG graph which contains two types of nodes, A and B. I am looking for a graph partitioning algorithm that can partition a graph in sub-graphs such that each sub-graph contains up to X number ...
user avatar
2 votes
0 answers
33 views

Partition columns into m groups to maximize absolute value sums

The Task You are given $n$ columns each of length $m$. All values are either $-1$ or $1$. Find an assignment $s$ of each of columns to 1 of $m$ groups in order to maximize the sum of all the absolute ...
user avatar
  • 21
3 votes
1 answer
76 views

Subset sum with only two item types

Suppose we have $r$ copies of the integer $a$ and $t$ copies of the integer $b$, and a capacity $C$. We would like to find the maximum sum of the given integers, that is at most $C$. This is a special ...
user avatar
1 vote
1 answer
90 views

Partition a set of n integers into m subsets in a way that the maximum subset sum is minimized

Let's say we have a set of n integers. I'm trying to find a way to partition this set into m subsets (empty subsets are not ...
user avatar
2 votes
1 answer
49 views

Upper-bounding the out-going degree of a graph

Given a graph $G=(V,E)$, I'm looking for a way to orient its edges in a way that will bound its out degree. For example, I can bound the graph's out-degree by $\approx 2\cdot a(G)$, where $a(G)$ is $G$...
user avatar
0 votes
0 answers
24 views

Finding all k-partitions with additional constraints

The partition problem is a very well known one. To partition an integer array into k equal sum partitions. My problem is I want to partition them in such a way that the sum of their partitions equals ...
user avatar
1 vote
0 answers
67 views

Does an FPTAS exist for the multiple subset sum problem when m is fixed and c is not a variable?

From Wikipedia Multiple subset sum: The multiple subset sum problem (MSSP) is a generalization of the subset sum problem (SSP): given a multiset $S$ of $n$ integers, and an integer $m$, the goal is to ...
user avatar
0 votes
0 answers
116 views

A Variant to "Boats to Save People"

This question is a variant of LeetCode 881. Boats to Save People by removing the restriction of "each boat carries at most two people at the same time" from the original question. Problem ...
user avatar
  • 1,071
1 vote
1 answer
151 views

SUBSET SUM reduction to PARTITION

This is the PARTITION problem: Given a multiset S of positive integers, decide if it can be partitioned into two equal-sum subsets. This is the SUBSET SUM problem: Given a multiset S of integers ...
user avatar
4 votes
0 answers
54 views

How to sample a perfect partition uniformly at random?

I would like to sample $n$ integers (of some fixed length, say $k$ bits) uniformly at random, and have them partitioned into two sets of equal sum. Since finding such a perfect partition (even if it ...
user avatar
3 votes
1 answer
142 views

Partition of a $k$-partite graph to minimal number of connected sets

Let $G$ be a $k$-partite directed acyclic graph where the edges are only between two adjacent sets of vertices. I'm trying to partition the graph to the minimal number of connected sets. Sets $A_0, ...
user avatar
0 votes
0 answers
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 ...
user avatar
  • 33
2 votes
1 answer
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 ...
user avatar
0 votes
1 answer
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 ...
user avatar
1 vote
1 answer
48 views

Bounds on graph partitioning

I am trying to find some generic upper bounds on the "standard" graph partitioning problem. Say I have a graph with $|V|$ vertices and $|E|$ edges I want to partition it into two equal $N/...
user avatar
2 votes
2 answers
100 views

Path graph partitioning, minimizing cut while minimizing maximum total node weight in each part

Suppose there is a path (linear) graph $G = (V, E)$ where $V = \{0, \ldots, n - 1\}$ and $E=\{(0, 1), (1, 2), \ldots, (n - 2, n - 1)\}$, with edge weights $w_e : E \to \mathbb{N}$ and vertex weights $...
user avatar
  • 364
1 vote
2 answers
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 ...
user avatar
3 votes
1 answer
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 ...
user avatar
2 votes
2 answers
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 ...
user avatar
  • 71
0 votes
2 answers
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$ ...
user avatar
  • 11
0 votes
0 answers
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 ...
user avatar
0 votes
0 answers
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 ...
user avatar
  • 1
3 votes
0 answers
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 ...
user avatar
2 votes
0 answers
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 ...
user avatar
2 votes
1 answer
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 ...
user avatar
  • 21
0 votes
1 answer
83 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 = {...
user avatar
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 ...
user avatar
  • 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} = \...
user avatar
1 vote
1 answer
409 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 ...
user avatar
  • 13
2 votes
1 answer
36 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,\...
user avatar
  • 21
1 vote
1 answer
52 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 ...
user avatar
  • 23
1 vote
2 answers
148 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 ...
user avatar
  • 11
2 votes
1 answer
94 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$? ...
user avatar