Questions tagged [partition-problem]
The partition-problem tag has no usage guidance.
85
questions
1
vote
1
answer
279
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$ ...
- 550
3
votes
1
answer
435
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$$
$$...
CommunityBot
- 1
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-...
- 6,999
3
votes
0
answers
700
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
99
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
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 ...
CommunityBot
- 1
0
votes
1
answer
286
views
How many edges are cut in a balanced partition of a graph?
Consider a graph on n nodes and e edges that is partitioned into k "balanced" subgraphs in the sense that each block has an equal number of nodes and the number of cut edges is minimized. Is there a ...
13
votes
1
answer
824
views
Intermediate $\mathsf{NP}$-complete problems?
Partition problem is weakly NP-complete since it has polynomial (pseudo-polynomial) time algorithm if input integers are bounded by some polynomial. However, 3-Partition is strongly NP-complete ...
- 20.9k
1
vote
0
answers
153
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
1
answer
471
views
NP-hardness of minimizing sum of weighted product
Consider a total of $d$ items, $\{I_1,I_2,\cdots,I_d\}$, each having a weight $w_i$ (a positive integer), and a total of $m$ bins, $\{B_1,B_2,\cdots,B_m\}$. We would like to distribute the items into ...
- 3,266
7
votes
2
answers
2k
views
Partition planar graph into connected subgraphs of equal size
Work
Jünger, Michael, Gerhard Reinelt, and William R. Pulleyblank. "On partitioning the edges of graphs into connected subgraphs." Journal of graph theory 9.4 (1985): 539-549.
states that for 4-...
- 1,138
0
votes
1
answer
662
views
What is a minimum vertex separator as in this definition?
In a research paper the following definition appears that I'm not able to understand completely.
Let $G=(V,E)$ be an undirected unweighted graph with vertex set $V$ and edge set $E$, no self-loops, ...
- 221
13
votes
1
answer
386
views
Another variant of PARTITION
I've got a reduction of the following partition problem to a certain scheduling problem:
Input: A list $a_1\leqslant\cdots\leqslant a_n$ of positive integers in non-decreasing order.
Question: Does ...
- 3,899
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
9
votes
4
answers
2k
views
Partitioning graphs while minimizing inter-partition edges
I'm working on trying to partition a triangulated graph into connected subgraphs with some guarantees on the number of inter-partition edges. Here's an example of a triangulated graph that has been ...
- 11k
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 ...
- 393
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) ...
- 393
0
votes
0
answers
52
views
partition into unit-interval graphs [duplicate]
I am re-opening this question as i have the following question.
I was going through the paper by Farrugia which was mentioned in an answer in that post. Initially i beleived that the follwoing problem ...
CommunityBot
- 1
13
votes
1
answer
549
views
Partition into interval graphs
Suppose there is a graph $G=(V,E)$. I want to test if $V$ can be partitioned into two disjoint sets $V_1$ and $V_2$ such that the subgraphs induced by $V_1$ and $V_2$ are unit interval graphs.
I know ...
- 2,765
7
votes
2
answers
3k
views
Partition a graph into 2 connected subgraphs
I'm stumped on a sub problem that I'm working on for my thesis. I need to be able to partition a graph into 2 connected subgraphs of almost equal size. So if there are $m$ vertices in $G$, subgraphs $...
CommunityBot
- 1
7
votes
1
answer
1k
views
K-Clustering of a Graph maximizing intra-cluster 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 complete graph G with non-...
- 32.1k
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
1
answer
434
views
Partitioning a matrix into equal-sized regions: finding the maximum
I am facing the following research problem. We are given a matrix $M[1..p,1..p]$ of elements such that:
each element has value in the range $[0, \frac 1 j]$, $j <= p$, $j$ is given,
the sum of all ...
- 21
0
votes
1
answer
197
views
Planning jobs as partition problem
I think this should be a famous problem but I could not find its name.
I have $n$ jobs with size $s_i$ that are offered at time $t_i$ and $k$ machines.
How can I assign jobs to machines to minimize ...
- 199
-3
votes
1
answer
105
views
what problem is this? [closed]
I have this instance:
Let's say I have two (could be more) friends, one weighing 200 pounds and another weighing 100 pounds; I won a box with 30 chocolates in a contest and I want to divide among ...
- 4,831
7
votes
0
answers
1k
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,776
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 ...
- 3,170
0
votes
1
answer
595
views
FPTAS for Number Partition Problem
I've been given a task to implement two algorithms (an exact algorithm and fully polynomial approximation scheme) for number partitioning problem. I found out that I can use some modification of ...
CommunityBot
- 1
1
vote
1
answer
238
views
Expansion vs Sparsest cut
let $G=(V,E)$ and $S\subsetneq V$ then expansion of set $S$ is
$$\alpha(S)=\frac{|E(S,\overline{S})|}{\min\{|S|,|\overline{S}|)\}}$$
where $\bar{S}=V\setminus{S}$ and $E(S,\bar{S})$ are edges ...
- 666
2
votes
1
answer
121
views
partition to min the max number of intersections
Given $n$ items and $m$ customers, each of whom is interested in some subset of the items, partition the set of items among $k$ different stores so that the maximum number of customers visiting any ...
CommunityBot
- 1
7
votes
0
answers
845
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 ...
CommunityBot
- 1
0
votes
1
answer
2k
views
Graph building with weighted nodes
I have a set of nodes which can be connected together through arcs. Every node has an associated value, reflecting the "fitness" that this particular node has in the graph. I have to find the best ...
CommunityBot
- 1
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 ...
CommunityBot
- 1
4
votes
1
answer
192
views
Set partitioning algorithm
I'm a working software engineer and I'm trying to develop some planning software. I have faced the following problem.
I have some finite set $ U $ of some distinct elements $ e_i \in U $.
I have ...
- 6,999
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 ...
CommunityBot
- 1