*Rolf Niedermeier*

- Published in print:
- 2006
- Published Online:
- September 2007
- ISBN:
- 9780198566076
- eISBN:
- 9780191713910
- Item type:
- chapter

- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198566076.003.0011
- Subject:
- Mathematics, Combinatorics / Graph Theory / Discrete Mathematics

This chapter surveys further important techniques for designing fixed-parameter algorithms. These include color-coding, integer linear programming, iterative compression, greedy localization, and ...
More

This chapter surveys further important techniques for designing fixed-parameter algorithms. These include color-coding, integer linear programming, iterative compression, greedy localization, and graph minor theory. The practical relevance of each technique is also evaluated. From a practical point of view, the two most important techniques are colour-coding and iterative compression.Less

This chapter surveys further important techniques for designing fixed-parameter algorithms. These include color-coding, integer linear programming, iterative compression, greedy localization, and graph minor theory. The practical relevance of each technique is also evaluated. From a practical point of view, the two most important techniques are colour-coding and iterative compression.

*Cristopher Moore and Stephan Mertens*

- Published in print:
- 2011
- Published Online:
- December 2013
- ISBN:
- 9780199233212
- eISBN:
- 9780191775079
- Item type:
- chapter

- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780199233212.003.0009
- Subject:
- Physics, Theoretical, Computational, and Statistical Physics

This chapter focuses on the relationships between decision problems and their optimisation versions. It shows that, for most problems, the optimal solution can be realised in polynomial time if and ...
More

This chapter focuses on the relationships between decision problems and their optimisation versions. It shows that, for most problems, the optimal solution can be realised in polynomial time if and only if we can tell whether a solution with a given quality exists. It then explores approximation algorithms for the traveling salesman problem and considers some large families of optimisation problems that can be solved in polynomial time, including linear programming and semidefinite programming. It demonstrates that the duality between MAX FLOW and MIN CUT is no accident — that linear programming problems come in pairs. In addition, the chapter looks at integer linear programming, which can be solved in polynomial time before concluding with a discussion of optimisation problems from a practical point of view.Less

This chapter focuses on the relationships between decision problems and their optimisation versions. It shows that, for most problems, the optimal solution can be realised in polynomial time if and only if we can tell whether a solution with a given quality exists. It then explores approximation algorithms for the traveling salesman problem and considers some large families of optimisation problems that can be solved in polynomial time, including linear programming and semidefinite programming. It demonstrates that the duality between MAX FLOW and MIN CUT is no accident — that linear programming problems come in pairs. In addition, the chapter looks at integer linear programming, which can be solved in polynomial time before concluding with a discussion of optimisation problems from a practical point of view.

*Rudolf Müller*

- Published in print:
- 2005
- Published Online:
- August 2013
- ISBN:
- 9780262033428
- eISBN:
- 9780262302920
- Item type:
- chapter

- Publisher:
- The MIT Press
- DOI:
- 10.7551/mitpress/9780262033428.003.0014
- Subject:
- Society and Culture, Technology and Society

This chapter offers information on several approaches used for making the winner determination problem (WDP) solvable by putting restrictions on the bid prices. It begins with integer linear ...
More

This chapter offers information on several approaches used for making the winner determination problem (WDP) solvable by putting restrictions on the bid prices. It begins with integer linear programming formulations of WDP in order to get a tractable case for the winner determination problem. The chapter then focuses on another approach that is used for making WDP a combinatorial optimization problem by using the intersection graph of bids. As reported, the latter approach leads to faster algorithms in comparison with the linear programming approach. The chapter further explains how other models such as restricting bid sets or bid values can become suitable methods for showing tractability. Limitations that can hamper the performance of these approaches including economic inefficiencies, incentive problems, and exposure problems.Less

This chapter offers information on several approaches used for making the winner determination problem (WDP) solvable by putting restrictions on the bid prices. It begins with integer linear programming formulations of WDP in order to get a tractable case for the winner determination problem. The chapter then focuses on another approach that is used for making WDP a combinatorial optimization problem by using the intersection graph of bids. As reported, the latter approach leads to faster algorithms in comparison with the linear programming approach. The chapter further explains how other models such as restricting bid sets or bid values can become suitable methods for showing tractability. Limitations that can hamper the performance of these approaches including economic inefficiencies, incentive problems, and exposure problems.

*Daniel Lehmann, Rudolf Müller, and Tuomas Sandholm*

- Published in print:
- 2005
- Published Online:
- August 2013
- ISBN:
- 9780262033428
- eISBN:
- 9780262302920
- Item type:
- chapter

- Publisher:
- The MIT Press
- DOI:
- 10.7551/mitpress/9780262033428.003.0013
- Subject:
- Society and Culture, Technology and Society

This chapter defines and formulates a combinatorial optimization problem, called the winner determination problem, and examines its complexity properties. A range of alternative mathematical ...
More

This chapter defines and formulates a combinatorial optimization problem, called the winner determination problem, and examines its complexity properties. A range of alternative mathematical programming models including integer linear programming, weighted stable set in graphs, knapsack, and matching that covers variants of the problem related to particular bidding languages is also discussed. The chapter further highlights inapproximability results, and reviews the approximation algorithm, which is a polynomial time algorithm. It concludes that the problem, which is represented as an integer program, is NP-complete and can be tackled by applying three fundamentally different approaches, which it discusses.Less

This chapter defines and formulates a combinatorial optimization problem, called the winner determination problem, and examines its complexity properties. A range of alternative mathematical programming models including integer linear programming, weighted stable set in graphs, knapsack, and matching that covers variants of the problem related to particular bidding languages is also discussed. The chapter further highlights inapproximability results, and reviews the approximation algorithm, which is a polynomial time algorithm. It concludes that the problem, which is represented as an integer program, is NP-complete and can be tackled by applying three fundamentally different approaches, which it discusses.