| Description |
1 online resource (xiii, 412 pages) : illustrations |
| Series |
Lecture notes in computer science, 0302-9743 ; 9682 |
|
LNCS sublibrary. SL 1, Theoretical computer science and general issues |
|
Lecture notes in computer science ; 9682. 0302-9743
|
|
LNCS sublibrary. SL 1, Theoretical computer science and general issues.
|
| Contents |
Intro; Preface; Organization; Contents; On Approximation Algorithms for Concave Mixed-Integer Quadratic Programming; 1 Introduction; 2 Proof of Theorem1; 2.1 Approximation in the Inner Region; 2.2 Decomposition of the Outer Region; References; Centerpoints: A Link Between Optimization and Convex Geometry; 1 Introduction; 2 An Application to Mixed-Integer Optimization; 3 General Properties; 4 Specialized Properties; 5 Computational Aspects; 5.1 Exact Algorithms; 5.2 Approximation Algorithms; References; Rescaled Coordinate Descent Methods for Linear Programming; 1 Introduction; 2 Algorithm 1 |
|
3 Algorithm 2: A Dual Chubanov Algorithm3.1 Refinements; References; Approximating Min-Cost Chain-Constrained Spanning Trees: A Reduction from Weighted to Unweighted Problems; 1 Introduction; 2 An LP-Relaxation for MCCST and Preliminaries; 3 An LP-Rounding Approximation Algorithm; 3.1 An Overview; 3.2 Algorithm Details and Analysis; 4 A Reduction from Weighted to Unweighted Problems; 5 Towards a -Approximation Algorithm for (QP); References; Max-Cut Under Graph Constraints; 1 Introduction; 1.1 Our Results and Techniques; 1.2 Related Work; 2 Preliminaries; 3 Approximation Algorithm for GCMC |
|
3.1 Linear Program3.2 The Rounding Algorithm; 3.3 Algorithm Analysis; References; Sparsest Cut in Planar Graphs, Maximum Concurrent Flows and Their Connections with the Max-Cut Problem; 1 Introduction; 2 Preliminaries; 2.1 The Chinese Postman Problem and Minimum T-joins; 3 Sparsest Cut in Planar Graphs; 4 Graphs with no K5 Minor; 5 Maximum Concurrent Flow; 5.1 Planar Graphs; 5.2 Graphs with no K5 Minor; References; Intersection Cuts for Bilevel Optimization; 1 Introduction; 2 Literature Overview; 3 Bilevel-Free Sets; 4 Mixed-Integer Bilevel Linear Programming; 5 A New Family of Cuts for MIBLP |
|
6 Informed No-Good Cuts7 Preliminary Computational Results; References; Exact Algorithms for the Chance-Constrained Vehicle Routing Problem; 1 Introduction; 2 Problem Definition and an Edge-Based Formulation; 2.1 Edge-Based Formulation; 2.2 Vehicle Requirements in the Capacity Inequalities; 2.3 Joint Normal Random Demands; 3 Dantzig-Wolfe Formulation; 3.1 Relaxed Pricing; 3.2 Relaxed Pricing for Joint Normal Demands; 4 Computational Experiments; 4.1 Comparison of the CCVRP with Recourse Models; 5 Conclusion; References; Extended Formulations in Mixed-Integer Convex Programming; 1 Introduction |
|
2 Extended Formulations and Conic Representability3 An Outer-Approximation Algorithm for Mixed-Integer Conic Programming; 4 Extended Formulations and Disciplined Convex Programming; 5 Computational Results; References; k-Trails: Recognition, Complexity, and Approximations; 1 Introduction; 1.1 Our Results; 2 Recognition of k-Trails; 3 Containment of Minimum Weight k-Trails; References; Better s-t-Tours by Gao Trees; 1 Introduction; 1.1 Previous Work; 1.2 Notation and Preliminaries; 1.3 Best-of-Many Christofides; 1.4 Gao Trees; 1.5 Our Contribution; 2 Proof of the Structure Theorem |
| Summary |
This book constitutes the refereed proceedings of the 18th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2016, held in Liège, Belgium, in June 2016. The 33 full papers presented were carefully reviewed and selected from 125 submissions. The conference is a forum for researchers and practitioners working on various aspects of integer programming and combinatorial optimization. The aim is to present recent developments in theory, computation, and applications in these areas. The scope of IPCO is viewed in a broad sense, to include algorithmic and structural results in integer programming and combinatorial optimization as well as revealing computational studies and novel applications of discrete optimization to practical problems |
| Notes |
International conference proceedings |
|
Includes author index |
|
Online resource; title from PDF title page (SpringerLink, viewed June 6, 2016) |
| Subject |
Integer programming -- Congresses
|
|
Combinatorial optimization -- Congresses
|
|
Algorithms & data structures.
|
|
Discrete mathematics.
|
|
Network hardware.
|
|
Mathematical theory of computation.
|
|
Computers -- Programming -- Algorithms.
|
|
Computers -- Data Processing.
|
|
Computers -- Hardware -- Network Hardware.
|
|
Combinatorial optimization
|
|
Integer programming
|
| Genre/Form |
Conference papers and proceedings
|
| Form |
Electronic book
|
| Author |
Louveaux, Quentin, editor
|
|
Skutella, Martin (Mathematician), editor.
|
| ISBN |
9783319334615 |
|
3319334611 |
|
