Skip to main content
SpringerLink
Log in

Approximation and Complexity in Numerical Optimization

Continuous and Discrete Problems

  • Book
  • © 2000

Overview

Editors:
  1. Panos M. Pardalos

    1. Center for Applied Optimization, Department of Industrial and Systems Engineering, University of Florida, USA

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

Part of the book series: Nonconvex Optimization and Its Applications (NOIA, volume 42)

This is a preview of subscription content, log in via an institution to check access.

Access this book

Log in via an institution
eBook USD 169.00
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book USD 219.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info
Hardcover Book USD 219.99
Price excludes VAT (USA)
  • Durable hardcover edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Other ways to access

Licence this eBook for your library

Institutional subscriptions

Table of contents (32 chapters)

  1. Front Matter

    Pages i-xvii
    Download chapter PDF

  2. Navigating Graph Surfaces

    • James Abello, Shankar Krishnan
    Pages 1-16

  3. The Steiner Ratio of L p -planes

    • Jens Albrecht, Dietmar Cieslik
    Pages 17-30

  4. Hamiltonian Cycle Problem via Markov Chains and Min-type Approaches

    • Mikhail Andramonov, Jerzy Filar, Panos Pardalos, Alexander Rubinov
    Pages 31-47

  5. Solving Large Scale Uncapacitated Facility Location Problems

    • Francisco Barahona, Fabián A. Chudak
    Pages 48-62

  6. A Branch-and-Bound Procedure for the Largest Clique in a Graph

    • Earl R. Barnes
    Pages 63-77

  7. A New “Annealed” Heuristic for the Maximum Clique Problem

    • Immanuel M. Bomze, Marco Budinich, Marcello Pelillo, Claudio Rossi
    Pages 78-95

  8. Inapproximability of some Geometric and Quadratic Optimization Problems

    • Andreas Brieden, Peter Gritzmann, Victor Klee
    Pages 96-115

  9. Convergence Rate of the P-Algorithm for Optimization of Continuous Functions

    • James M. Calvin
    Pages 116-129

  10. Application of Semidefinite Programming to Circuit Partitioning

    • Changhui Cris Choi, Yinyu Ye
    Pages 130-137

  11. Combinatorial Problems Arising in Deregulated Electrical Power Industry: Survey and Future Directions

    • Doug Cook, Gregory Hicks, Vance Faber, Madhav V. Marathe, Aravind Srinivasan, Yoram J. Sussmann et al.
    Pages 138-162

  12. On Approximating a Scheduling Problem

    • Pierluigi Crescenzi, Xiaotie Deng, Christos H. Papadimitriou
    Pages 163-174

  13. Models and Solution for On-Demand Data Delivery Problems

    • Michael C. Ferris, Robert R. Meyer
    Pages 175-188

  14. Complexity and experimental evaluation of primal-dual shortest path tree algorithms

    • Paola Festa, Raffaele Cerulli, Giancarlo Raiconi
    Pages 189-208

  15. Machine Partitioning and Scheduling under Fault-Tolerance Constraints

    • Dimitris A. Fotakis, Paul G. Spirakis
    Pages 209-244

  16. Finding Optimal Boolean Classifiers

    • John Franco
    Pages 245-286

  17. Tighter Bounds on the Performance of First Fit Bin Packing

    • Martin Fürer
    Pages 287-297

  18. Block Exchange in Graph Partitioning

    • William W. Hager, Soon Chul Park, Timothy A. Davis
    Pages 298-307

  19. On the Efficient Approximability of “HARD” Problems: A Survey

    • Harry B. Hunt III, Madhav V. Marathe, Richard E. Stearns
    Pages 308-322

  20. Exceptional Family of Elements, Feasibility, Solvability and Continuous Paths of ε-Solutions for Nonlinear Complementarity Problems

    • G. Isac
    Pages 323-337
Back to top

Keywords

About this book

There has been much recent progress in approximation algorithms for nonconvex continuous and discrete problems from both a theoretical and a practical perspective. In discrete (or combinatorial) optimization many approaches have been developed recently that link the discrete universe to the continuous universe through geomet­ ric, analytic, and algebraic techniques. Such techniques include global optimization formulations, semidefinite programming, and spectral theory. As a result new ap­ proximate algorithms have been discovered and many new computational approaches have been developed. Similarly, for many continuous nonconvex optimization prob­ lems, new approximate algorithms have been developed based on semidefinite pro­ gramming and new randomization techniques. On the other hand, computational complexity, originating from the interactions between computer science and numeri­ cal optimization, is one of the major theories that have revolutionized the approach to solving optimization problems and to analyzing their intrinsic difficulty. The main focus of complexity is the study of whether existing algorithms are efficient for the solution of problems, and which problems are likely to be tractable. The quest for developing efficient algorithms leads also to elegant general approaches for solving optimization problems, and reveals surprising connections among problems and their solutions. A conference on Approximation and Complexity in Numerical Optimization: Con­ tinuous and Discrete Problems was held during February 28 to March 2, 1999 at the Center for Applied Optimization of the University of Florida.

Editors and Affiliations

  • Center for Applied Optimization, Department of Industrial and Systems Engineering, University of Florida, USA

    Panos M. Pardalos

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation