## Expressing Optimization Problems as Integer Programs, and Undirected Path Problems: A Descriptive Complexity Approach |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

Integer Programming as a Framework for Optimization and Approx | 14 |

Integer Programs to Express Optimization Problems | 18 |

MaxFSLIP and its subclasses | 26 |

Copyright | |

9 other sections not shown

### Common terms and phrases

2star approximation algorithm approximation properties articulation point assignment biconnected biconnected component bounded number clique computing constant constant-approximable corresponding cycle3 cycleS is expressible decision problems define Definition descriptive complexity disjunctive program edge relation encoding endpoint exist express MaxClique expressible in Datalog expressible in Lw expressing optimization problems Fagin's theorem feasible solution first-order logic Fixed Subgraph Homeomorphism FSHP graph G greedy algorithm inequality input relations instance Integer program template LaPaugh and Rivest Matching Max Capacity Representatives Max Majority IP Max Majority Sat MaxCut MaxEi MaxFSBLIP(2 MaxFSLIP maximization problems MaxMatching MaxPB MaxSat negation node disjoint paths NP-complete objective function objective variable path of length pattern graphs pebbles player polynomial proof pumping lemma quantifiers query recursively-defined relations second-order logic sentence separator similarly simple cycle containing step Stratified Datalog structure subclass Subgraph Homeomorphism Problem syntactic Theorem three disjoint paths three node disjoint tuples Turing Machine undirected graph values vertex vertices winning strategy