Questions tagged [partitions]

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

34 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
7
votes
1answer
893 views

Fastest known algorithm for $3$-$\mathrm{Partition}$ problem

$3$-$\mathrm{Partition}$ problem is $\mathsf{NP}$-Complete in a strong sense meaning there is no pseudo-polynomial time algorithm for it unless $\mathsf{P=NP}$. I am looking for the fastest known ...
5
votes
0answers
627 views

How to distribute items of varying sizes into bins of varying sizes, such that percent utilization across all bins is minimized?

I have a bunch of databases, each having different access patterns, such that each puts a different amount of load on its database cluster. I would like to distribute them around my set of database ...
4
votes
0answers
597 views

Even distribution algorithm

Right now I am working on a distributed system that sends messages from single source to many nodes. It is necessary that certain messages are sent to the same node to ensure order of processing. ...
4
votes
0answers
243 views

Graph optimization problem with multiple objectives/constraints

Let's assume that we have a directed acyclic graph $G = (V, E)$, non-negative vertex weight functions $w_a(v)$ and $w_b(v)$, and a non-negative edge weight function $t(u,v)$. We want to divide ...
3
votes
0answers
94 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 ...
3
votes
0answers
122 views

Split a graph into 2 components with known distribution?

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 ...
2
votes
1answer
78 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 ...
2
votes
0answers
24 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 ...
2
votes
0answers
18 views

Is there a more commonly-used term for “multi-pivoting”?

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 ...
2
votes
0answers
1k views

k-way set partition problem--dynamic programming solution

I was reading up on the set partition problem on this site of Wikipedia: https://en.m.wikipedia.org/wiki/Partition_problem Among other things, they present a DP approach to solving the equal subset ...
2
votes
0answers
173 views

Reducing partition to a partition where sum(partition1) = 3 times sum(partition2)

Given the following NP-complete problem: PARTITION Input: A list of positive integers $a_1, a_2, \dots, a_n$. Question: Can the list be partitioned into $2$ parts, $A_1$ and $A_2$, such ...
2
votes
0answers
141 views

min cut for multiple partitions

So I am familiar with the standard minimum cut problem in which the goal is to find the smallest possible set of edges in a graph such that, upon their removal, we have two nonempty, disjoint ...
1
vote
0answers
21 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
vote
0answers
113 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 ...
1
vote
0answers
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 ...
1
vote
0answers
37 views

Partitioning the columns of a matrix

I thought about this problem for a while now and am not able to find a solution for it, be it a direct algorithm or a reduction to a known problem, so I'm asking here: Suppose you have a matrix $A\in\...
1
vote
0answers
91 views

Polygon decomposition into minimum star-shaped polygons

As the title suggests, I'm trying to implement an algorithm to decompose a polygon into the minimum number of star-shaped polygons. I've been searching for quite some time but I can't find any ...
1
vote
0answers
99 views

How to enumerate all partitioning of a set to k-subsets of size at most b

I'm looking for an algorithm to generate/enumerate all possibilities for partitioning a set of size $n$ to $k$ non-empty subsets, each with size at most $b$. More specifically, given a set $V$ where $...
1
vote
0answers
554 views

Exact algorithm for the partition problem

The partition problem is: given a set of numbers, find a partition to two subsets in which the difference between the sums in each subset is minimized. This optimization problem is NP-hard. The simple ...
1
vote
0answers
174 views

Computational Geometry: what is the key of the BST in the algorithm “ Partitioning a polygon in y-monotone pieces”

The algorithm to partition a polygon into y-monotone pieces is as follows: ...
1
vote
0answers
183 views

Non-standard partition problem

I've been writing codes to solve a standard partition problem. I've investigated brute force, greedy, Karmarkar-Karp and complete Karmarkar-Karp algorithms. Standard partition problem: divding a ...
1
vote
0answers
89 views

DISTINCT 3-PARTITION with all integers between $B/4$ and $B/2$

In the definition of 3-PARTITION of Garey&Johnson, the instance is a set of $3m$ integers such that the sum of all these integers is $mB$ and such that each integer is strictly between $B/4$ and $...
1
vote
0answers
192 views

Enumerate subtrees of a given size in a graph

Given a graph $G$ with $n$ nodes, is there an algorithm to find $m$ subtrees, each with $\lfloor n/m\rfloor$ or $\lceil n/m\rceil$ nodes, such that every node of $G$ is in exactly one tree? Other ...
1
vote
0answers
48 views

Graph Partition Across Cluster - Minimize Largest Matrix Size

I am writing some code for modeling semi-biologically realistic neural networks, which is to be run/distributed across nodes in a computer cluster. I begin with a very large adjacency matrix (...
0
votes
0answers
32 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
1answer
28 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 = {...
0
votes
0answers
29 views

Quicksort with lomuto partition - how many repeating elements are too many?

I know that quicksort with Lomuto's partition method faces worst case run-time $\Theta(n^2)$ when there are many repeating elements in the array. However, I'm trying to figure out - how many ...
0
votes
0answers
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 ...
0
votes
0answers
75 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 ...
0
votes
0answers
16 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 ...
0
votes
0answers
99 views

$k$-partitioning problem via brute force

Given a set of non-negative integers $A = \{a_1,a_2,\dots,a_N \}$, the $k$-partitioning problem is to partition the numbers into $k$ sets $\{A_1,A_2,\dots, A_k\} $ such that the deviation: $$ \...
0
votes
0answers
66 views

Is a minimal deviation version of set partition problem NP-Hard?

I want to know if a specific version (and what´s its name?) of the Set Partitioning Problem is NP-Complete, and if, is NP-Hard? Problem: Given a set of elements $e_i$ where $i={1,...,n}$, each with ...
0
votes
0answers
166 views

Reduction from 3-Partition to a cutting problem

My problem is the following: Input: a set of $m$ non-negative integers $\{b_1,...,b_m\}$ and a parameter $n$ with $n<m$. Output: $n$ sets of 3 numbers Task: Cut the $b_i$'s into $3n$ integers such ...
-2
votes
1answer
497 views

How to prove this “np-complete” problem?

I have a problem that I need to prove its np-completness: My original question I need to reduce it from some problem, i´m trying to do it from some other than knapsack, that´s why I ask again. I need ...