Approximation and Complexity in Numerical Optimization

1. Front Matter

   Pages i-xvii

   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

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.

• algorithms
• complexity
• global optimization
• linear optimization
• metaheuristic
• optimization
• programming
• scheduling

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

  Panos M. Pardalos

Policies and ethics