Index of papers in Proc. ACL 2009 that mention

**linear programming**

Abstract | We formulate the problem of non-projective dependency parsing as a polynomial-sized integer linear program . |

Abstract | The model parameters are learned in a max-margin framework by employing a linear programming relaxation. |

Dependency Parsing as an ILP | A linear program (LP) is an optimization problem of the form |

Dependency Parsing as an ILP | If we add the constraint x E Zd, then the above is called an integer linear program (ILP). |

Introduction | Much attention has recently been devoted to integer linear programming (ILP) formulations of NLP problems, with interesting results in applications like semantic role labeling (Roth and Yih, 2005; Punyakanok et al., 2004), dependency parsing (Riedel and Clarke, 2006), word alignment for machine translation (Lacoste-Julien et al., 2006), summarization (Clarke and Lapata, 2008), and coreference resolution (Denis and Baldridge, 2007), among others. |

linear programming is mentioned in 5 sentences in this paper.

Topics mentioned in this paper:

- dependency parsing (21)
- ILP (19)
- dependency tree (14)

Abstract | We augment the standard perceptron algorithm with a global integer linear programming formulation to optimize both local fit of information into each topic and global coherence across the entire overview. |

Introduction | We estimate the parameters of our model using the perceptron algorithm augmented with an integer linear programming (ILP) formulation, run over a training set of example articles in the given domain. |

Method | To select the optimal excerpts, we employ integer linear programming (ILP). |

Method | Solving the ILP Solving an integer linear program is NP-hard (Cormen et al., 1992); however, in practice there exist several strategies for solving certain ILPs efficiently. |

linear programming is mentioned in 4 sentences in this paper.

Topics mentioned in this paper:

- ILP (9)
- perceptron (7)
- cosine similarity (5)

Abstract | We combine this knowledge with discourse information, and formulate the debate side classification task as an Integer Linear Programming problem. |

Introduction | This information is employed, in conjunction with discourse information, in an Integer Linear Programming (ILP) framework. |

Method | We formulate the problem of finding the overall side of the post as an Integer Linear Programming (ILP) problem. |

linear programming is mentioned in 3 sentences in this paper.

Topics mentioned in this paper:

- F-measure (4)
- Linear Programming (3)
- Semantic Relatedness (3)