A Dynamic Programming Framework for Generating Approximately Diverse and
Optimal Solutions
A Dynamic Programming Framework for Generating Approximately Diverse and
Optimal Solutions
We develop a general framework, called approximately-diverse dynamic programming (ADDP) that can be used to generate a collection of $k\ge2$ maximally diverse solutions to various geometric and combinatorial optimization problems. Given an approximation factor $0\le c\le1$, this framework also allows for maximizing diversity in the larger space of $c$-approximate solutions. …