Convex Separation from Optimization via Heuristics

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

Let $K$ be a full-dimensional convex subset of $\mathbb{R}^n$. We describe a new polynomial-time Turing reduction from the weak separation problem for $K$ to the weak optimization problem for $K$ that is based on a geometric heuristic. We compare our reduction, which relies on analytic centers, with the standard, more general reduction.

Keywords

Data Structures and Algorithms, Optimization and Control

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/109832

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/cs/0603089
 http://arxiv.org/abs/cs/0603089

Collections

arXiv