Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size.
Jianer ChenHenning FernauIyad A. KanjGe XiaPublished in: STACS (2005)
Keyphrases
- upper bound
- lower bound
- upper and lower bounds
- worst case
- branch and bound algorithm
- branch and bound
- running times
- lower and upper bounds
- constant factor
- kernel function
- objective function
- np hard
- tight upper and lower bounds
- vc dimension
- cutting plane
- special case
- feature space
- upper bounding
- sample complexity
- sample size
- least squares
- online algorithms
- optimal cost
- optimal solution