Muutke küpsiste eelistusi

Iterative Methods in Combinatorial Optimization [Kõva köide]

3.50/5 (4 hinnangut Goodreads-ist)
(Carnegie Mellon University, Pennsylvania), (McGill University, Montréal), (The Chinese University of Hong Kong)
  • Formaat: Hardback, 254 pages, kõrgus x laius x paksus: 235x159x18 mm, kaal: 480 g, Worked examples or Exercises; 44 Line drawings, unspecified
  • Sari: Cambridge Texts in Applied Mathematics
  • Ilmumisaeg: 18-Apr-2011
  • Kirjastus: Cambridge University Press
  • ISBN-10: 1107007518
  • ISBN-13: 9781107007512
Teised raamatud teemal:
Iterative Methods in Combinatorial OptimizationSuurem pilt
  • Formaat: Hardback, 254 pages, kõrgus x laius x paksus: 235x159x18 mm, kaal: 480 g, Worked examples or Exercises; 44 Line drawings, unspecified
  • Sari: Cambridge Texts in Applied Mathematics
  • Ilmumisaeg: 18-Apr-2011
  • Kirjastus: Cambridge University Press
  • ISBN-10: 1107007518
  • ISBN-13: 9781107007512
Teised raamatud teemal:
Püsilink: https://www.kriso.ee/db/9781107007512.html
Märksõnad:
"With the advent of approximation algorithms for NP-hard combinatorial optimization problems, several techniques from exact optimization such as the primal-dual method have proven their staying power and versatility. This book describes a simple and powerful method that is iterative in essence and similarly useful in a variety of settings for exact and approximate optimization. The authors highlight the commonality and uses of this method to prove a variety of classical polyhedral results on matchings, trees, matroids, and flows. The presentation style is elementary enough to be accessible to anyone with exposure to basic linear algebra and graph theory, making the book suitable for introductory courses in combinatorial optimization at the upper undergraduate and beginning graduate levels. Discussions of advanced applications illustrate their potential for future application in research in approximation algorithms"--

"With the advent of approximation algorithms for NP-hard combinatorial optimization problems, several techniques from exact optimization such as the primal-dual method have proven their staying power and versatility. This book describes a simple and powerful method that is iterative in essence, and similarly useful in a variety of settings for exact and approximate optimization. The authors highlight the commonality and uses of this method to prove a variety of classical polyhedral results on matchings, trees, matroids, and flows. The presentation style is elementary enough to be accessible to anyone with exposure to basic linear algebra and graph theory, making the book suitable for introductory courses in combinatorial optimization at the upper undergraduate and beginning graduate levels. Discussions of advanced applications illustrate their potential for future application in research in approximation algorithms"--

Provided by publisher.

Muu info

A simple, powerful method that is iterative and useful in a variety of settings for exact and approximate optimization.
Preface ix
1 Introduction
1(11)
1.1 The assignment problem
1(2)
1.2 Iterative algorithm
3(2)
1.3 Approach outline
5(3)
1.4 Context and applications of iterative rounding
8(1)
1.5 Book chapters overview
8(2)
1.6 Notes
10(2)
2 Preliminaries
12(16)
2.1 Linear programming
12(7)
2.2 Graphs and digraphs
19(2)
2.3 Submodular and supermodular functions
21(7)
3 Matching and vertex cover in bipartite graphs
28(18)
3.1 Matchings in bipartite graphs
28(4)
3.2 Generalized assignment problem
32(3)
3.3 Maximum budgeted allocation
35(5)
3.4 Vertex cover in bipartite graphs
40(3)
3.5 Vertex cover and matching: duality
43(1)
3.6 Notes
44(2)
4 Spanning trees
46(19)
4.1 Minimum spanning trees
46(8)
4.2 Iterative 1-edge-finding algorithm
54(3)
4.3 Minimum bounded-degree spanning trees
57(3)
4.4 An additive one approximation algorithm
60(2)
4.5 Notes
62(3)
5 Matroids
65(23)
5.1 Preliminaries
65(2)
5.2 Maximum weight basis
67(4)
5.3 Matroid intersection
71(3)
5.4 Duality and min-max theorem
74(3)
5.5 Minimum bounded degree matroid basis
77(5)
5.6 k matroid intersection
82(3)
5.7 Notes
85(3)
6 Arborescence and rooted connectivity
88(22)
6.1 Minimum cost arborescence
89(6)
6.2 Minimum cost rooted k-connected subgraphs
95(6)
6.3 Minimum bounded degree arborescence
101(5)
6.4 Additive performance guarantee
106(2)
6.5 Notes
108(2)
7 Submodular flows and applications
110(21)
7.1 The model and the main result
110(2)
7.2 Primal integrality
112(4)
7.3 Dual integrality
116(1)
7.4 Applications of submodular flows
117(7)
7.5 Minimum bounded degree submodular flows
124(4)
7.6 Notes
128(3)
8 Network matrices
131(14)
8.1 The model and main results
131(2)
8.2 Primal integrality
133(3)
8.3 Dual integrality
136(3)
8.4 Applications
139(4)
8.5 Notes
143(2)
9 Matchings
145(19)
9.1 Graph matching
145(10)
9.2 Hypergraph matching
155(5)
9.3 Notes
160(4)
10 Network design
164(18)
10.1 Survivable network design problem
164(4)
10.2 Connection to the traveling salesman problem
168(4)
10.3 Minimum bounded degree Steiner networks
172(3)
10.4 An additive approximation algorithm
175(4)
10.5 Notes
179(3)
11 Constrained optimization problems
182(9)
11.1 Vertex cover
182(2)
11.2 Partial vertex cover
184(3)
11.3 Multicriteria spanning trees
187(2)
11.4 Notes
189(2)
12 Cut problems
191(12)
12.1 Triangle cover
191(3)
12.2 Feedback vertex set on bipartite tournaments
194(3)
12.3 Node multiway cut
197(3)
12.4 Notes
200(3)
13 Iterative relaxation: Early and recent examples
203(28)
13.1 A discrepancy theorem
203(3)
13.2 Rearrangments of sums
206(2)
13.3 Minimum cost circulation
208(2)
13.4 Minimum cost unsplittable flow
210(2)
13.5 Bin packing
212(8)
13.6 Iterative randomized rounding: Steiner trees
220(8)
13.7 Notes
228(3)
14 Summary
231(2)
Bibliography 233(8)
Index 241
Lap-Chi Lau is an Assistant Professor in the Department of Computer Science and Engineering at The Chinese University of Hong Kong. Lap-Chi's main research interests are in combinatorial optimization and graph algorithms. His paper on Steiner tree packing was given the Machtey award in the IEEE Foundations of Computer Science Conference. His Ph.D. thesis was awarded the Doctoral Prize from the Canadian Mathematical Society and a Doctoral Prize from the Natural Sciences and Engineering Research Council of Canada. R. Ravi is Carnegie Bosch Professor of Operations Research and Computer Science at Carnegie Mellon University. Ravi's main research interests are in combinatorial optimization (particularly in approximation algorithms), computational molecular biology and electronic commerce. He is currently on the editorial boards of Management Science and the ACM Transactions on Algorithms. Mohit Singh is an Assistant Professor in the School of Computer Science, McGill University. He completed his Ph.D. in 2008 at the Tepper School of Business, Carnegie Mellon University, where his advisor was Professor R. Ravi. His thesis was awarded the Tucker prize by the Mathematical Programming Society. His research interests include approximation algorithms, combinatorial optimization and studying models that deal with uncertainty in data.