Advanced Combinatorial Algorithms

Authored by: Samir Khuller , Balaji Raghavachari

Algorithms and Theory of Computation Handbook

Print publication date:  November  2009
Online publication date:  November  2009

Print ISBN: 9781584888222
eBook ISBN: 9781584888239
Adobe ISBN:

10.1201/9781584888239-c8

 Download Chapter

 

Abstract

The optimization of a given objective, while working with limited resources is a fundamental problem that occurs in all walks of life, and is especially important in computer science and operations research. Problems in discrete optimization vary widely in their complexity, and efficient solutions are derived for many of these problems by studying their combinatorial structure and understanding their fundamental properties. In this chapter, we study several problems and advanced algorithmic techniques for solving them. One of the basic topics in this field is the study of network flow and related optimization problems; these problems occur in various disciplines, and provide a fundamental framework for solving problems. For example, the problem of efficiently moving entities, such as bits, people, or products, from one place to another in an underlying network, can be modeled as a network flow problem. Network flow finds applications in many other areas such as matching, scheduling, and connectivity problems in networks. The problem plays a central role in the fields of operations research and computer science, and considerable emphasis has been placed on the design of efficient algorithms for solving it.

 Cite
Search for more...
Back to top

Use of cookies on this website

We are using cookies to provide statistics that help us give you the best experience of our site. You can find out more in our Privacy Policy. By continuing to use the site you are agreeing to our use of cookies.