ON A SEARCH PROBLEM RELATED TO BRANCH-AND-BOUND PROCEDURES.

R. M. Karp, M. Saks, A. Wigderson

Research output: Chapter in Book/Report/Conference proceedingConference contribution

18 Scopus citations

Abstract

A model is described that captures the essential elements common to all branch-and-bound procedures. Storage limitations in these procedures raise an interesting search problem. Deterministic and probabilistic algorithms for this problem presented. The algorithms imply that branch-and-bound can be performed with very small storage and only slightly superlinear time.

Original languageEnglish (US)
Title of host publicationAnnual Symposium on Foundations of Computer Science (Proceedings)
PublisherIEEE
Pages19-28
Number of pages10
ISBN (Print)0818607408, 9780818607400
DOIs
StatePublished - 1986
Externally publishedYes

Publication series

NameAnnual Symposium on Foundations of Computer Science (Proceedings)
ISSN (Print)0272-5428

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture

Cite this