Complexity in numerical optimization

Author(s)

• Pardalos, P. M. (Panos M.)

Bibliographic Information

Complexity in numerical optimization

editor, Panos M. Pardalos

World Scientific, 1993

Note

Includes bibliographical references

Description and Table of Contents

Description

Computational complexity, originated from the interactions between computer science and numerical 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.This book is a collection of articles on recent complexity developments in numerical optimization. The topics covered include complexity of approximation algorithms, new polynomial time algorithms for convex quadratic minimization, interior point algorithms, complexity issues regarding test generation of NP-hard problems, complexity of scheduling problems, min-max, fractional combinatorial optimization, fixed point computations and network flow problems.The collection of articles provide a broad spectrum of the direction in which research is going and help to elucidate the nature of computational complexity in optimization. The book will be a valuable source of information to faculty, students and researchers in numerical optimization and related areas.

Table of Contents

• Average performance of self-dual interior point algorithm for linear programming, K.M. Anstreicher et al
• the complexity of approximating a nonlinear program, M. Bellare and P. Rogaway
• algorithms for the least distance problem, P. Berman et al
• translational cuts for convex minimization, J.V. Burke et al
• maximizing concave functions in fixed dimension, E. Cohen and N. Megiddo
• the complexity of allocating resources in parallel - upper and lower bounds, E.J. Friedman
• complexity issues in nonconvex network flow problems, G. Guisewite and P.M. Pardalos
• a classification of static scheduling problems, J.W. Herrmann et al
• complexity of single machine dual criteria and hierarchical scheduling - a survey, C.-Y. Lee and G. Vairaktarakis
• performance driven graph enhancement problems, D. Paik and S. Sahni
• weighted means of cuts, parametric flows and fractional combinatorial optimization, T. Radzik
• some complexity issues involved in the construction of test cases for NP-hard problems, L. Sanchis
• a note on the complexity of fixed-point computation for noncontractive maps, C.W. Tsai and K. Sikorski
• maximizing non-linear concave functions in fixed dimension, S. Toledo
• polynomial time weak approximation algorithms for quadratic programming, S. Vavasis
• complexity results for a class of min-max problems with robust optimization applications, G. Yu and P. Kouvelis. (Part contents).

by "Nielsen BookData"

Details

• NCID: BA21207973
• ISBN:
  • 9810214154
• LCCN: 93004827
• Country Code: si
• Title Language Code: eng
• Text Language Code: eng
• Place of Publication: Singapore ; River Edge, N.J.
• Pages/Volumes: xiii, 511 p.
• Size: 23 cm
• Classification:
  • LCC : QA267.7
  • DC20 : 519.3
• Subject Headings:
  • LCSH : Computational complexity
  • LCSH : Mathematical optimization
  • LCSH : Numerical analysis