Questions tagged [partition-problem]
The partition-problem tag has no usage guidance.
38
questions with no upvoted or accepted answers
8
votes
0
answers
815
views
Is this minimization problem NP-Complete?
We are given an $n \times (n + k)$ matrix $A$, with entries in GF(2), of the form $A =[I_n\ B]$, where $I_n$ is the $n \times n$ identity matrix, and $B$ has no "zero" rows or columns.
The problem is ...
- 189
7
votes
0
answers
999
views
Partitioning DAG into Paths
What bounds (lower or upper) are known about the complexity of partitioning a Directly Acyclic Graph (DAG) into paths of respective sizes $n_1,\ldots,n_w$, such that to minimize their entropy $n{\cal ...
- 2,733
7
votes
0
answers
832
views
Approximation results for 3-partition
The 3-partition as defined here is a strongly NP-complete decision problem. Consider one optimization problem of 3-partition where the $m$ subsets each have at most three elements and a sum of not ...
- 951
5
votes
0
answers
78
views
A simultaneous FPTAS for both max-min and min-max number partitioning
The multiway number partitioning problem has two optimization variants: in one variant the goal is to minimize the largest bin sum (the "makespan"), and in the other variant the goal is to ...
- 2,078
5
votes
0
answers
122
views
Variation on block design/set cover
Given 3 parameters $s, r$ and $t$, where $r \leq t$, I want to construct $t$ sets such that each integer $\{1, \ldots, s\}$ appears in exactly $r$ of these sets. The question is:
Is it possible to ...
- 51
4
votes
0
answers
138
views
Split a string of positive numbers into substrings with decreasing totals
Suppose we're given a string of $n$ positive numbers and asked to split it into the maximum number of substrings whose totals are decreasing. I have an $O(n)$ time DP algorithm, but is it already ...
- 51
4
votes
0
answers
48
views
Minimal partition covering?
I am working on a problem that arises in the design of experiments. I wonder if it is part of a well-studied class of problems.
The problem is:
Start with a set of points $S$ and a target partition of ...
- 141
3
votes
0
answers
93
views
Number of connected partitions (or labelings) in a grid graph
Let $G$ be a 2D lattice graph (undirected) of size $W\times H$. Each "inner" vertex has $4$ adjacent vertices, whereas "boundary" vertices have $2$ or $3$ adjacent vertices, ...
- 31
3
votes
0
answers
679
views
Graph partition with weighted vertices and edges
I am searching for an algorithm to apply to a specific graph partition problem that I am interested in. It feels like a topic that people from CS may have worked on but it is also different from ...
- 31
3
votes
0
answers
2k
views
DAG partitioning for parallel computing
Consider a set of processes ($P=\{p_1, p_2,\dots, p_n \}$) and their data dependencies. Each process $p_i$ has an execution runtime which is denoted by $d_i$. We are interested to parallelize these ...
- 251
2
votes
0
answers
21
views
Hardness of 3-Partition with Small Target Value
In the 3-partition problem, we are given a set of positive integers $a_1,\ldots,a_n$ and a target value $T$; the goal is to decide if there is a partition of the numbers to triplets such that the sum ...
- 173
2
votes
0
answers
63
views
Partition of a set of integers into subsets where the max. of the subset-sums is minimum
Let $S$ be a set of $n$ positive integers, and $p$ be a partition of $S$ into $m$ mutually disjoint subsets, such that no subset contains more than $k$ elements.
Let $\mathcal{P}$ denote the set of ...
2
votes
0
answers
59
views
hardness of partition of permutation into a minimum number of monotone subsequences
Given a permutation P, a monotone subsequence is a subsequence (i.e. the elements do not have to be consecutive in P) that increases or decreases. This leads naturally to the following optimization ...
- 71
2
votes
0
answers
105
views
Small set expansion and expanders
Given a graph $G=(V,E)$ on $n$ vertices and $0 \leq \delta \leq 1/2$, we can define the expansion of $G$ over small sets:
$$
h(G,\delta)= \min_{\vert S\vert \leq \delta n } \phi(S) \ ,
$$
with
$$\phi(...
- 41
2
votes
0
answers
86
views
Is the following special case of multiway number partitioning NP-hard?
The following problem is a decision problem of multiway number partitioning (wikipedia) (Note that $k$ is also a part of an input in the following problem, while $k$ is a fixed number in wikipedia ...
- 21
2
votes
0
answers
58
views
Complexity of a matrix partition problem in graphs
All graphs in this question are finite, simple, and undirected. Let $H$ be a regular graph on at least five vertices, let $v_1,v_2,\dots,v_n$ be the vertices in $H$, and let $M$ be the adjacency ...
- 1,723
2
votes
0
answers
76
views
Hardness result or reference for a set partition problem
I'm wondering if the following problem is (or has been proven to be) NP-Complete.
Input: integer $n\ge0$, set $S_1,S_2,\ldots,S_{2n}$, set $T_1,T_2,\ldots,T_n$.
Accept iff: there exists $\{a_i,...
- 101
2
votes
0
answers
73
views
Partition into c and 1-c
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 ...
- 21
2
votes
0
answers
53
views
Min cut problem on unbalanced partitions for planar graphs with unit capacity edges
The question is: given a planar graph $G$ with unit capacity edge weights and a fixed positive integer $k$, what is an approximation algorithm for finding the minimum size of a cut $(A,B)$ with $|A|=k$...
- 21
2
votes
0
answers
181
views
Is Non-linear Constrained Optimal Exact Cover NP-Hard?
Playing around I ran into a problem which looks like a Exact Set Covering / Partition Problem, but I am unable to find a reduction to categorize the complexity of the problem, despite it looks NP-Hard....
- 81
2
votes
0
answers
113
views
Unbalanced connected partition
Let $G = (V, E)$ be a connected graph with (possibly negative) vertex weights $w(v)\in\mathbb{Z}$. We want to partition the vertices into two parts such that the induced graphs $G'$ and $G''$ are ...
- 121
2
votes
0
answers
216
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 can divide vertices in ...
- 239
2
votes
0
answers
178
views
Graph partition with objective over intra-partition weights
I have a problem in which I need to find an optimal graph cut that maximizes an objective over weights not on the cut. I have looked at the literature but have not been able to find any similar ...
- 21
2
votes
0
answers
446
views
Post Correspondence Problem "binary" variant
Bounded Post Correspondence Problem is defined as follows:
given list of pairs of words $ (x_1,y_1), \ldots, (x_n, y_n) $ and $K$ find sequence of indexes $i_1, \ldots, i_k$, $k \leq K$ so that $x_{...
- 39
1
vote
0
answers
234
views
Graph partitioning to minimize sum of intra-partition edge weights
I've seen a lot of graph partitioning algorithms w/ the objective of minimizing the weight of inter-partition edges, (e.g. k-way partitioning) but haven't quite found anything on minimizing the total ...
- 11
1
vote
0
answers
55
views
Partition of multisets of polynomials
Problem: Given a multiset S of irreducible polynomials in Z[x], say YES if S can be partitioned into two nonempty multisets A and B such that both the product of all the elements of A and the product ...
- 61
1
vote
0
answers
93
views
Distributing bags of apples equally
Assume you have $N$ bags of apples that you want to equally distribute to $K$ people. Each bag contains $n_i$ apples and you are not allowed to open and divide the bags; you must distribute the bags ...
- 119
1
vote
0
answers
152
views
Array partitioning with limitations on partition size
Consider an array of bytes.
I want to partition the array, such that the following two conditions hold:
The number of bytes within each partition (except perhaps the last one) is between L and U, ...
- 16.5k
1
vote
0
answers
58
views
Repartitioning a binary tree
Suppose I have a binary tree $G = (V, E)$ (with undirected edges) that is partitioned into sets of k vertices, where each set of vertices is a connected subgraph of $G$. Additionally, if there are ...
- 383
1
vote
0
answers
62
views
Partition planar graph of vertices with at most degree 3 into connected subgraphs
I'm currently working on my thesis which deals with pathfinding over a Delaunay triangulated graph. I want to be able to partition my Delaunay triangulation into disjoint (regarding vertices) ...
- 383
0
votes
0
answers
70
views
Is this Knapsack/Subset Sum Variant NP-Hard?
The problem: Let $A_1 = \{a^1_1,\ldots,a^1_n\}, A_2 = \{a^2_1,\ldots,a^2_n\}, \ldots, A_k = \{a^k_1,\ldots,a^k_n\} \subset \mathbb{N}$ be $k$ sets of $n$ integers, and let $U,L \in \mathbb{N}$ be ...
- 173
0
votes
0
answers
56
views
Bin Covering problem with variable bin sizes
I have a decision problem that I cannot seem to map to a standard studied problem, although it seems similar to a few. I am wondering if anyone has come across this problem before, or if someone can ...
0
votes
0
answers
57
views
Using bin-packing algorithms to approximate maximum-makespan
Bin-packing (BP) and maximum-makespan (MM) are dual problems. In both problems, the input can be defined as a set $S$ of positive integers, and the output is a partition of $S$.
In BP, there is a ...
- 2,078
0
votes
0
answers
42
views
Bin Packing And Preemptive Multi-Core Scheduling
I am trying to solve a preemptive multi-core scheduling problem, where the input is the tasks. The number of cores M can be decided after seeing the input tasks. I ...
- 101
0
votes
1
answer
332
views
A k-approximation to k-way number partitioning
The $k$-way number partitioning problem accepts as input a multiset $S$ of positive numbers, and returns a partition of $S$ into $k$ subsets such that the subset sums are as nearly-equal as possible, ...
- 2,078
0
votes
0
answers
195
views
3-partition problem without the restriction to triplets
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,078
0
votes
0
answers
167
views
NP-hardness of minimizing sum of complicated objective function
In our research, we faced the following problem optimization problem:
Input: a list of $k$ pairs of positive integers $(n_1,d_1), \ldots, (n_k,d_k)$;
an integer $m$.
Output: $P$, a partition of the ...
0
votes
0
answers
89
views
Partitioning based on distribution
Having a set of numbers $S={s_i}$, I want to assign them to bins, $b_i$, such that the sum of items on bins follow a specific distribution.
For two bins and uniform distribution, this problem is ...
- 199