All publications

EUCLID / RESEARCH OUTPUT

Book Chapter

The Lagrangian Search Method

Pavlos S. Efraimidis, Paul G. Spirakis

Nonconvex Optimization and Its Applications · 2001

Abstract

In this work, the Lagrangian Search Method (LSM), an algorithmic framework based on lagrangian relaxation, relaxed decision procedures and binary search, is presented. LSM is used to efficiently extend the class of positive linear programs (PLP), a submodel of linear programming that admits very efficient approximations in sequential, parallel and distributed settings. Theoretical guarantees for the efficiency and the approximation ratio of LSM for extended PLP, are derived. The extended PLP model is used for fast parallel (and sequential) approximations to a class of hard combinatorial optimization problems.vv

CITATION

BibTeX

Efraimidis_2001 
@incollection{efraimidis_2001b,
  address = {Boston, MA},
  title = {The {Lagrangian} {Search} {Method}},
  isbn = {978-1-4613-0279-7},
  url = {https://doi.org/10.1007/978-1-4613-0279-7_15},
  booktitle = {Advances in {Convex} {Analysis} and {Global} {Optimization}: {Honoring} the {Memory} of {C}. {Caratheodory} (1873–1950)},
  publisher = {Springer US},
  author = {Efraimidis, Pavlos S. and Spirakis, Paul G.},
  editor = {Hadjisavvas, Nicolas and Pardalos, Panos M.},
  year = {2001},
  doi = {10.1007/978-1-4613-0279-7_15},
  pages = {283--294}
}
Back to publications