Você deve depender de java-runtime-headless (>= 1.6) (que é preenchido por openjdk-7-jre-headless e permite que qualquer JRE 1.6 ou mais recente que o usuário tenha instalado funcione).
Isso permite muito mais flexibilidade. Por exemplo, eu corro oracle-java8-jdk no meu sistema; isso fornece default-jre-headless 1.8 (assim como java7-runtime-headless , java6-runtime-headless e java5-runtime-headless ), mas qualquer dependência de openjdk provavelmente resultaria em não instalar seu programa porque não tenho desejo de instalar um JRE antigo .