MINIMUM BLOCK-ANGULAR CONVEX PROGRAMMING

Next: Algebra and Number Theory Up: Mathematical Programming Previous: NEAREST LATTICE VECTOR Index

INSTANCE: K disjoint convex compact sets called blocks, M nonnegative continuous convex functions $f^k_m: B^k\rightarrow R$ .
SOLUTION: A positive number $\lambda$ such that

$\begin{displaymath} \sum_{k=1}^K f^k_m(x^k)\le\lambda \mbox{ for }1\le m\le M, \mbox{ and }x^k\in B^k\mbox{ for }1\le k\le K. \end{displaymath}$
MEASURE: $\lambda$ .
Good News: Admits an FPTAS [206].

Viggo Kann
2000-03-20