Questions tagged [partition-problem]
The partition-problem tag has no usage guidance.
82
questions
0
votes
1
answer
55
views
Is this edge-partitioning NP-Hard?
Let $G = (V,E)$ be an undirected graph with $m = |E|$ edges (assume that $m = 3t$ for some $t \in \mathbb{N}$).
Problem: Partition $E$ to $q = \frac{m}{3}$ sets $S_1,S_2,\ldots, S_q \subseteq E$ sets ...
- 113
0
votes
1
answer
98
views
Complexity and Algorithm for specific Vertex Separator Problem
Given a graph $\Gamma=(V,E)$ with vertex set $V$ and edge set $E$ a $\textit{three partition}$ is decomposition of $V$ into a triple $(V_1, S, V_2)$ such that vertices of $V_1$ are only incident to ...
5
votes
0
answers
77
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,046
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 ...
- 113
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 ...
1
vote
1
answer
122
views
3 Matroid Intersection, a Special Case
It is well known that finding a maximum cardinality (or weight) common independent set in the intersection of 3 matroids is APX-Hard.
Question: Does this problem remain NP-Hard if one of the matroids ...
- 113
2
votes
0
answers
62
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
56
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
1
vote
1
answer
201
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
2
votes
0
answers
104
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
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
2
votes
0
answers
79
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
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
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,703
0
votes
0
answers
54
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,046
0
votes
0
answers
40
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
8
votes
1
answer
229
views
Finding vertex separator such that the induced subgraph has minimal number of edges
My problem is related to edge and vertex cuts with a little twist.
Given a graph $G$ and two vertexes $u$ and $v$. I want to find a set of vertexes $S \subset V$ that disconnects $u$ and $v$ such that ...
- 183
3
votes
0
answers
90
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
4
votes
0
answers
47
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
1
vote
2
answers
288
views
Two valued variant of subset sum problem
I'm interested in the complexity of the following problem: Given a multiset $S$ containing only two positive integers $a$ and $b$, find a $k$-partition of $S$ that maximizes the sum of part with ...
- 25
1
vote
2
answers
126
views
Name of this graph partitioning problem? (related to coloring)
Given a graph $G=(V,E)$ and an integer $k$, find a partition $P_1, P_2, \dots, P_k$ of $V$ into $k$ parts that minimize the total number of edges between two vertices in the same part, i.e. $\sum_i |(...
- 693
2
votes
2
answers
275
views
Partitioning a connected polygon into connected pieces of equal area
Armaselu and Daescu (TCS, 2015) present algorithms that, given a convex polygon $P$ and an integer $m$ (which must be a power of $2$), return a partition of $P$ into $m$ convex polygons with the same ...
- 2,046
0
votes
1
answer
323
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,046
0
votes
0
answers
188
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,046
2
votes
0
answers
113
views
a direct polynomial reduction from 3EQU-SUM to EQU-SUM problem [closed]
Given a multiset of integers $S$, in the Equ-Sum problem we want to check
whether
or not $S$ can be divided into two disjoint subsets, say $X_1$, $X_2$ such that $\sum_{x_i \in X_1}x_i = \sum_{x_j \...
2
votes
1
answer
106
views
Can the Banach-Tarski paradox be "realized" by floating-point round-off?
The Banach-Tarski paradox says that
a ball in $\mathbb{R}^3$ can be partitioned into a finite number of pieces, whose rearrangement has a larger volume than the original.
It occurred to me that it ...
- 3,713
2
votes
1
answer
111
views
NP hard proving: separate graph into a set of the same size disjoint parts by maximizing the shared neighbours of each part
Given a graph $G=\{V,E\}$ where $V$ denotes the nodes and $E$ denotes edges. The size of the node $|V| = nk$. The target is to separte the graph into $n$ disjoint parts $P=\{V_i\}_{i=1}^n$ and the ...
- 51
6
votes
1
answer
243
views
Uniformly sampling or counting connected graph partitions with any number of blocks
Question: Is it possible to uniformly sample in polynomial time from the set of all connected partitions of a graph? Or is there a JVV type argument that proves this to be NP-hard?
To clarify: By a ...
- 1,439
3
votes
1
answer
112
views
Meet of integer partitions
An integer partition of $n$, $A$, is a multiset of positive integers such that $\sum_{a \in A} a= n$. We say that $B \leq A$, if there exists a map $\phi: |B| \to |A|$, such that for $a \in A$, we ...
- 583
6
votes
2
answers
164
views
$NP$-Completeness of $\epsilon$-balanced graph partitioning for fixed $\epsilon$
Consider this graph partitioning problem: Let $G = (V, E)$ be a simple undirected graph and $0 \leq \epsilon \leq 1, M \geq 0$ be constants. Are there disjoint subsets $V_1, V_2$ with $V = V_1 \cup ...
- 71
8
votes
1
answer
325
views
A partition problem with order constraints
In the OrderedPartition problem, the input is two sequences of $n$ positive integers, $(a_i)_{i\in [n]}$ and $(b_i)_{i\in [n]}$.
The output is a partition of the ...
- 2,046
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
8
votes
3
answers
918
views
A partition problem in which some numbers may be cut
In the standard partition problem, we are given some numbers whose sum is $2s$ and have to decide whether they can be partitioned into two subset whose sum is $s$. It is known to be NP-hard.
However,...
- 2,046
6
votes
2
answers
914
views
Is this partition problem strongly NP-complete?
Some computational problems have variants that appear to be harder. For instance, Graph Automorphism (GA) problem has quasi-polynomial time algorithm ( by Babai's Graph Isomorphism result) while the ...
- 20.8k
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
1
answer
248
views
Optimal partition according to partition cardinality
Given $N$ sets of integers $S_1, \ldots,S_N$ with $|S_i| \le K$.
We want to partition those sets such that the union of all sets in any given partition doesn't contain more than $K$ elements.
Can ...
user30584
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
112
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
1
vote
2
answers
251
views
Complexity of a variant of partition problem
Motivated by this post, Strongly NP-complete variants of subset sum or partition problem, I am interested in this variant of partition:
Given a solution to balanced partition problem (both parts have ...
- 20.8k
3
votes
2
answers
1k
views
Strongly NP-complete variants of subset sum or partition problem
Some problems have variants that appear to be harder. For instance, Graph Automorphism (GA) problem has quasi-polynomial time algorithm ( by Babai's GI result). However, the fixed-point free GA ...
- 20.8k
0
votes
1
answer
174
views
Is pooling-aware bin packing NP-Hard?
I am unable to prove whether the following problem is NP-Hard. It seems like a bin-packing or a partition problem, without being close enough to either of them (at least I do not see the reduction to ...
- 81
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
4
votes
1
answer
486
views
Proof that the graph optimization problem is NP-hard
I'm trying to prove that the following optimization problem is NP-hard:
Given a graph $G=(V,E)$, non-negative vertex weight functions $w(v)$ and $s(v)$, and a non-negative edge weight function $t(u,v)...
- 239
2
votes
1
answer
381
views
Partition refinement in transition state systems (bisimulation contraction)
I am trying to understand bisimulation contraction of Kripke models.
I have read these lecture slides and this Wikipedia page, but I still don't fully understand it.
I can understand that the two ...
- 129
1
vote
1
answer
273
views
Maximal Clique partition of vertices with smallest number of cut edges
I am given a simple undirected graph $G(V, E)$. I want to partition $V$ into $b$ Maximal cliques: $\{C_1, C_2, ..., C_b\}$ such that the number of edges that cut across two cliques is the minimum. $b$ ...
- 21
2
votes
1
answer
1k
views
Max-sum graph-partition for maximizing intra-edge weights?
I would like to know if the following problem has already been studied, and if so how is it called. In particular I'm interested in approximability results.
Input: A graph G with negative or non-...
- 21
3
votes
1
answer
426
views
Variant of Subset Sum Problem with Changing Bound
Given a sequence of decreasing integers, i.e., $a_1 \geq a_2 \geq \cdots \geq a_T $ and a positive real $k\geq 1$, find a subset $S$ such that
$$\max_{S\subseteq \{1,\ldots,T\}} \sum_{i\in S} a_i$$
$$...
- 41
3
votes
0
answers
666
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
1
vote
0
answers
92
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