The partition-problem tag has no wiki summary.
2
votes
1answer
49 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 ...
0
votes
1answer
113 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 ...
9
votes
0answers
336 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 ...
5
votes
0answers
131 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 ...
0
votes
1answer
142 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 ...
0
votes
0answers
68 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 ...
4
votes
0answers
277 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 ...
3
votes
1answer
133 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
votes
0answers
372 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 ...
2
votes
0answers
269 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 ...
5
votes
0answers
584 views
Faster pseudo-polynomial time algorithms for PARTITION
I want to partition N given numbers (may or may not be equal) into 2 subsets such that the 2 subsets have sum as close as possible and also the cardinality of the sets are equal (if n is even) or ...
