# Tagged Questions

The tag has no usage guidance.

74 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$ ...
84 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-...
177 views

70 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 ...
244 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 ...
671 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 ...
516 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-...
649 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 ...
80 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 ...
480 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 ...
171 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 ...
571 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 ...
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_{...