Questions tagged [partitions]
A partition or partitioning of a set A is a collection of disjoint sets whose union yields A.
150
questions
-2
votes
0answers
28 views
Can i recover data if i completely wiped the disk? Please help! [closed]
I use windows and ubuntu.
Soo.... I was trying to install ubuntu alongside windows and I lost all the data on the PC. (I know this is dumb but yeah)
Thanks in advance!
1
vote
0answers
40 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 ...
0
votes
0answers
23 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 ...
1
vote
1answer
49 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 ...
4
votes
0answers
48 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 ...
3
votes
1answer
127 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, ...
0
votes
0answers
17 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 ...
2
votes
1answer
87 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 ...
0
votes
1answer
64 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
1answer
45 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/...
2
votes
2answers
89 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 $...
1
vote
2answers
58 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 ...
3
votes
1answer
77 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 ...
2
votes
2answers
352 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 ...
0
votes
2answers
94 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$ ...
0
votes
0answers
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 ...
0
votes
0answers
38 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 ...
0
votes
0answers
25 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 ...
3
votes
0answers
112 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
95 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 ...
2
votes
1answer
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 ...
0
votes
1answer
42 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
196 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
180 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
251 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
33 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
48 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
86 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 ...
1
vote
1answer
56 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
76 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
134 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
89 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
44 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
92 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
23 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
96 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
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$.
...
2
votes
1answer
194 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
41 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
103 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
29 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
176 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
146 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
166 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
77 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
81 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
76 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
20 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
70 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
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 ...
