4
\$\begingroup\$

Introduction

Large meetings waste working time. Our aim is to split a large meeting into a number of smaller meetings, so the average number topics that a person discusses is minimized but every person has to be in every meeting they are interested in.

Input

Given is a function from a set of topics \$T\$ to a set of persons \$P\$ that are interested in this topic $$f:T \rightarrow 2^P$$ and maximum partition size \$m\$.

This is encoded as an array of arrays, where element \$f(i)\$ contains the topics of person \$i\$.

Test Case

m = 3
f = [
[9,7],
[3,7,6,4],
[3,1,2],
[7,5,4,2],
[6,2,8,1,4],
[3,7,2,9,8],
[4,3,2],
[3,4,6],
[1,9,5,3],
[6,4,1,2],
[9,7,3,1],
[1,7,4],
[5,1,7,2],
[5,2,7],
[4,2,6,9],
[6,4,1],
[6,5,9,8],
[9,1],
[9,1,5,6],
[1,2,4,8,7]                                                                     
]

Output

Find a partition of \$T\$ (a split into subsets that are disjoint and that cover the whole set) into $$X = {T_1, T_2, \ldots, T_n}$$ where \$n\le m\$, so that the following term is minimized: $$r = \sum_{T' \in X}{(|(\bigcup_{t \in T'} f(t))|\times |T'|)} $$

To help understand \$r\$, if each topic takes an hour to discuss, then \$r\$ is the total amount of person hours required for the meetings.

If there are multiple partition sizes with the same \$r\$, \$n\$ should be minimized as well.

The output should contain the partition \$X\$ as a two-dimensional array, such as: $$X = [[0,1,2,3],[4,5,6],[7,8,9]] $$

Winning Condition

I am looking for the fastest algorithm that finds the absolute minimum \$r\$ and \$n\$.

If that is not possible in polynomial time, then I am also looking for an polynomial algorithm that has the lowest upper bound on \$r\$ in relation to the absolute minimum \$r\$ (e.g. double).

\$\endgroup\$
  • 1
    \$\begingroup\$ @KevinCruijssen Sorry, I should have stated that more clearly, I will edit the answer. The problem is that I don't know the complexity class of the problem and depending on it, it is either one of those. I will add the other tag and hope that is OK. \$\endgroup\$ – Konrad Höffner Oct 10 '18 at 13:56
  • 2
    \$\begingroup\$ @KonradHöffner Are we allowed to assume that the input list of interesting topics is sorted l to g? (aka treat it as a set in code as well as equation) \$\endgroup\$ – moonheart08 Oct 10 '18 at 16:56
  • 2
    \$\begingroup\$ I'd like a description of the term r in words. You don't really describe what it is or means. \$\endgroup\$ – mbomb007 Oct 11 '18 at 0:00
  • 1
    \$\begingroup\$ @mbomb007: r is the sum of topics that all persons must discuss. If each topic takes an hour to discuss, then it is the total amount of person hours required for the meetings. \$\endgroup\$ – Konrad Höffner Oct 11 '18 at 7:07
  • 1
    \$\begingroup\$ @Konrad - that description ("total amount of person hours") is really helpful - you should add that into the question. \$\endgroup\$ – Toby Speight Oct 11 '18 at 8:49
1
+50
\$\begingroup\$

R with lpSolve

Turn the problem into an integer linear programming problem with \$2^t\$ variables and \$t+1\$ constraints, where \$t\$ is the number of topics. The cost function is modified by multiplying it with \$m\$ and adding the size of the partition. This makes the size of the partition a secondary optimization goal.

require("lpSolve")

decode <- function(n) {
  res <- c()
  i <- 1
  while (n>0){
    if (n %% 2 == 1)
      res <- c(res,i)
    i <- i+1
    n <- n %/% 2
  }
  res
}

opt <- function(m,p) {
  nr_pers <- length(p)
  nr_topics <- max(unlist(p))
  x <- array(0,c(nr_topics,nr_pers))
  for (i in 1:nr_pers)
    for (j in 1:length(p[[i]]))
      x[p[[i]][[j]],i] <- 1
  l <- array(0,c(2^nr_topics,nr_pers))
  cb <- rep(0,2^nr_topics)
  w <- rep(1,2^nr_topics)
  mt <- matrix(0,nr_topics+1,2^nr_topics)
  mt[nr_topics+1,1] <- 1
  len <- 1
  for (i in 1:nr_topics) {
    for(j in 1:len) {
      j1 <- len+j
      l[j1,] <- l[j,]+x[i,]
      cb[j1] <- cb[j] + 1
      w[j1] <- m*sum(l[j1,] != 0)*cb[j1]+1
      mt[,j1] <- mt[,j]
      mt[nr_topics+1-i,j1] <- 1
    }
    len <- 2*len
  }
  dir <- c(rep("=",nr_topics),"<=")
  rhs <- c(rep(1,nr_topics),m)
  sol <- lp("min",w,mt,dir,rhs,all.bin=TRUE)$solution
  res <- list()
  j <- 1
  for (i in 1:length(sol))
    if (sol[i]==1) {
      res[[j]] <- decode(i-1)
      j <- j+1
    }
  res
}

# test case
f <- list(
       c(9,7),
       c(3,7,6,4),
       c(3,1,2),
       c(7,5,4,2),
       c(6,2,8,1,4),
       c(3,7,2,9,8),
       c(4,3,2),
       c(3,4,6),
       c(1,9,5,3),
       c(6,4,1,2),
       c(9,7,3,1),
       c(1,7,4),
       c(5,1,7,2),
       c(5,2,7),
       c(4,2,6,9),
       c(6,4,1),
       c(6,5,9,8),
       c(9,1),
       c(9,1,5,6),
       c(1,2,4,8,7))

On debian, this needs the package r-cran-lpsolve. The code assumes that the topics start with 1 and that each topic number up to the maximum is used. Input and output is as list of vectors, which is not too nice. The test case example is defined in the code, but the list can of course also be entered directly.

To use it, start R and then source the code file and use the function like this:

> source("opt.r")
Loading required package: lpSolve
> opt(3,f)
[[1]]
[1] 1 2 3 4

[[2]]
[1] 6 8

[[3]]
[1] 5 7 9

> 

So [[1,2,3,4],[6,8],[5,7,9]] is an optimal partition for the test case.

\$\endgroup\$
  • \$\begingroup\$ Wow thanks, I didn't think about ILP at all! What is the complexity of that approach? How long did it run? I can only test it later but accepted it already as the bounty is running out. \$\endgroup\$ – Konrad Höffner Dec 12 '18 at 9:29
  • 1
    \$\begingroup\$ I think you can and should handle the bounty and acceptance separately. The preparation step is exponential in the number of topics, linear in the number of persons and independent from m. The example test case takes less than a second. \$\endgroup\$ – Christian Sievers Dec 12 '18 at 11:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.