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
0 votes
1 answer
58 views

$k$-way number contiguous partitioning

Given a set $S$ of $n$ positive integers $S=\{a_1,\ldots,a_n\}$, can we partition $S$ into $k$ subsets of equal sum such that each subset has contiguous elements from $S$? Here, a contiguous subset is ...
zebda's user avatar
  • 97
1 vote
0 answers
29 views

Algorithm for grouping set items into ordered buckets without crossing boundaries between same set items

I'm trying to order some data in real-time (in an API call) where my item count is on the order of a few million. I'm using Go, so my pseudo code may resemble that. My input items look like this: <...
contrapsych's user avatar
1 vote
0 answers
25 views

Graph partitioning in 2 clusters minimizing between cluster edges

I've been looking for an algorithm which divides an undirected graph into 2 subgraphs. However, unlike most existing work on graph partitioning out there (like METIS), I don't intend to obtain ...
koch_kir's user avatar
0 votes
0 answers
31 views

List of weakly NP-HARD problems

I need a list of at least 10 weakly NP-HARD problems. I already know the Knapsack problem, partition problem and subset sum problem. Please introduce other weakly NP-hard problems to me.
Soroush Vahidi's user avatar
0 votes
0 answers
38 views

Hoare's partition original method

So I was reading the Hoare's partition part of the Quicksort wiki and it says: "With respect to this original description, implementations often make minor but important variations. Notably, the ...
Reggie Hurley's user avatar
2 votes
1 answer
156 views

Partition of two sets for multi-line fitting, NP-hard?

Given two sets of nonnegative numbers $X=\{x_1,...,x_n\}$ and $Y=\{y_1,...,y_n\}$, my problems consists in finding the partition $S \subseteq \{1,...,n\}$ and $\bar{S}=\{1,...,n\}\backslash S$ ...
T. Pmp's user avatar
  • 43
0 votes
0 answers
20 views

reduction from partition to N3DM or balanced 3 partition problem

I want to know how can I reduce Subset Sum or Partition problem to N3DM problem in which each set has exactly 3 elements and same sum. N3DM Problem: https://en.wikipedia.org/wiki/Numerical_3-...
user's user avatar
  • 1
3 votes
1 answer
57 views

Partition a graph into connected subgraphs of 3 vertices each

We need to partition a graph into subgraphs of 3 vertices each, such that every subgraph has at least 2 edges. The problem is similar to the partition into triangles problem (which is NP-complete) but ...
Chaya's user avatar
  • 71
4 votes
1 answer
322 views

Partitioning a graph into connected pairs and triplets

We need to partition an undirected graph into connected subgraphs of size between $2$ and $k$, where $k$ is an integer. When $k=2$, the problem is equivalent to the perfect matching problem which is ...
Chaya's user avatar
  • 71
2 votes
2 answers
90 views

Does there exist an algorithm / software that finds optimal graph partition while enforcing contiguity on a subgraph?

I am interested in the traditional graph partitioning problem, which roughly speaking seeks to obtain a partition of a graph into a number of components, in which each component has about the same ...
Ike348's user avatar
  • 121
0 votes
1 answer
38 views

Partitioning a set based on a non-equivalence relation

I have a set of $n$ elements, and a binary relation between these elements. However, this is not guaranteed to be an equivalence relation. (Specifically, the elements are line segments in a plane, and ...
Draconis's user avatar
  • 7,038
1 vote
1 answer
42 views

Is deciding whether a graph admits two vertex-disjoint spanning trees of bounded size difference NP-hard?

I'd like to decide whether, given a connected graph $G = (V, E)$ and an integer $k$ as input, $G$ admits two vertex-disjoint subgraphs $T_1 = (V_1, E_1)$ and $T_2 = (V_2, E_2)$ such that $T_1$ and $...
J. Schmidt's user avatar
0 votes
0 answers
24 views

Is there any upper bound for the number of ways we can partition a multiset, where each part/segment in the partition has distinct elements?

A question is asked in the below link, which asks for the number of cases we can partition a multiset, where each part/segment in the partition has distinct elements. https://math.stackexchange.com/...
Amir's user avatar
  • 1
1 vote
1 answer
32 views

Reduction from $2$-Partitioning to (simple) pairwise $2$-Partitioning

I'm currently stuck showing $NP$-hardness of a problem of mine. An instance of my problem (I call it (simple) pairwise $2$-Partitioning) is given by the following: Given a set of tupels $B=\{(b_1,1),\...
Felix's user avatar
  • 161
0 votes
0 answers
84 views

Reduction from Partition problem to the same problem with the input replicated multiple times

In a variant of the Partition Problem given a multiset $S = \{a_1,\dots,a_n\}$ of positive integer with the total sum $\sum_{i=1}^n a_i = m\,T$, we want to find out if exists a partition $S_1,\dots,...
Roβ's user avatar
  • 1
1 vote
1 answer
32 views

Minimum number of bits to codify arrays with bounded sums

I have a very big set of non-empty arrays of possibly repeated numbers sorted in a weakly-decreasing order where each number belongs to the interval $[1, 55]$ and the sum of the elements of each array ...
ABu's user avatar
  • 457
0 votes
1 answer
51 views

Maximal Profit of 'legal' cutting of a board

I'm facing this problem for some time now, I've tried a greedy approach yet I result to trying a DP-ish approach, only to get stuck at a standstill. Given a board of length $n$, and an increasing ...
Aishgadol's user avatar
  • 315
3 votes
1 answer
728 views

Is it possible to randomly allocate items to bins such that each distinct allocation has equal probability?

I'm trying to randomly allocate N indistinguishable items over B indistinguishable bins with unlimited capacity. Each allocation should occur with equal probability. An allocation identifies the ...
programonkey's user avatar
1 vote
1 answer
131 views

The modularity difference in Louvain algorithm for community detection in graphs

I am interested in the formula of modularity difference between two partitions considered in the Louvain algorithm for community detection in graphs. I give a formal expression of this question below. ...
Matthieu Latapy's user avatar
1 vote
0 answers
41 views

Minimize sum of products of partition [closed]

I have a set of positive integer numbers $A = \{a_1,...,a_N\}$ and I need to find a partition of $A$ into two sets, such that the sum of their products is minimal, i.e., $$ \min_{X,Y : X \cup Y = A} \...
DrDizzy's user avatar
  • 11
4 votes
1 answer
143 views

Can almost equal partition problem be solved in polynomial time?

Given a list of positive integers with sum $s$, decide if there is a subset with sum $0.5s$. This is the well-known PARTITION problem, which is NP-hard. What about the following: Given a list of ...
user355066's user avatar
0 votes
1 answer
83 views

Complexity of the partition problem with additional constraint

The "classical" partition problem asks whether a given multiset $S$ of positive integers can be partitioned into two subsets $S_1$ and $S_2$ such that the sum of the numbers in $S_1$ equals ...
NoteMyQuestion's user avatar
1 vote
1 answer
32 views

Set partitions into singletons or pairs

I am trying to build an algorithm to compute the partition of a set into singletons or pairs for a set of cardinality 16. I am doing it in MATLAB and came up with codes that either run forever or ...
Cesare's user avatar
  • 113
1 vote
0 answers
45 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 ...
Jon Nir's user avatar
  • 143
1 vote
0 answers
22 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 ...
Katie's user avatar
  • 163
1 vote
1 answer
404 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$ ...
szx's user avatar
  • 13
19 votes
5 answers
4k 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 ...
fearless_fool's user avatar
0 votes
1 answer
40 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?...
Cesare's user avatar
  • 113
1 vote
1 answer
51 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)=\...
h_axlrose's user avatar
3 votes
2 answers
473 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 ...
Erel Segal-Halevi's user avatar
0 votes
0 answers
27 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 ...
user023049's user avatar
1 vote
0 answers
39 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 ...
yellowcard123's user avatar
4 votes
1 answer
298 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 ...
Voyager's user avatar
  • 177
0 votes
0 answers
23 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 ...
user7060's user avatar
  • 465
1 vote
1 answer
36 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 ...
Maitgon's user avatar
  • 23
2 votes
0 answers
157 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$...
Paúl Risco's user avatar
1 vote
0 answers
1k 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 ...
Ashkan Khademian's user avatar
1 vote
0 answers
32 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/...
NoteMyQuestion's user avatar
0 votes
0 answers
79 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 ...
user145024's user avatar
2 votes
0 answers
35 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 ...
k-0348's user avatar
  • 21
3 votes
1 answer
101 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 ...
Erel Segal-Halevi's user avatar
1 vote
1 answer
510 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 ...
Fish_n_Chips's user avatar
2 votes
1 answer
54 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$...
TheEmeritus's user avatar
1 vote
0 answers
148 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 ...
Samuel Bismuth's user avatar
1 vote
1 answer
646 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 ...
Legend123's user avatar
  • 113
4 votes
0 answers
80 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 ...
Erel Segal-Halevi's user avatar
3 votes
1 answer
168 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, ...
Philip L's 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 ...
Mathguy's user avatar
  • 33
2 votes
1 answer
177 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 ...
Samuel Bismuth's user avatar
0 votes
1 answer
203 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 ...
Omri Braha's user avatar