## Interfaces between computer science and operations research: proceedings of a symposium held at the Mathematisch Centrum, Amsterdam, September 7-10, 1976J. K. Lenstra, A. H. G. Rinnooy Kan, P. van Emde Boas |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

INTRODUCTION | 35 |

SETS AND INSTRUCTIONS | 36 |

HOW TO REPRESENT A GRAPH AN OMINOUS EXAMPLE | 39 |

38 other sections not shown

### Common terms and phrases

0-1 knapsack problem 0(n log accepted approximation algorithms assume binary heap binary search tree data structure defined DELETE denote deterministic DIRECTED HAMILTONIAN CIRCUIT dynamic programming edges element example executed Figure follows function Garey & Johnson given Gonzalez Graham graph greedy heuristic HAMILTONIAN CIRCUIT Ibarra implemented input instruction integer iteration Johnson's algorithm k-PRAM Karp knapsack problem label Lageweg large-item computation Lawler length linear logarithmic cost criteria lower bound Mathematisch Centrum max max membranes MRAM node nondeterministic RAM nondeterministic Turing machine NP-complete NP-hard obtained operations optimal schedule optimum tour pair Q,A parallel machines partitioning path polynomial polynomial-time precedence constraints procedure processing processor PSPACE RAM program RAM-ALGOL rectangle recursive requires Sahni scaled profit Section short strategy solution space bounds spanning walk storage S(n storage tape subset subtree Theorem tion traveling-salesman problem unary NP-hard uniform cost criteria vertices worst-case analysis yields