Index of papers in Proc. ACL 2014 that mention
  • linear programming
Thadani, Kapil
Abstract
Experiments show that these approximation strategies produce results comparable to a state-of-the-art integer linear programming formulation for the same joint inference task along with a significant improvement in runtime.
Conclusion
Experiments show that one of these approximation strategies produces results comparable to a state-of-the-art integer linear program for the same joint inference task with a 60% reduction in average inference time.
Introduction
Joint methods have also been proposed that invoke integer linear programming (ILP) formulations to simultaneously consider multiple structural inference problems—both over n-grams and input dependencies (Martins and Smith, 2009) or n-grams and all possible dependencies (Thadani and McKeown, 2013).
Introduction
We therefore consider methods to recover approximate solutions for the subproblem of finding the maximum weighted subtree in a graph, common among which is the use of a linear programming relaxation.
Introduction
This linear program (LP) appears empirically tight for compression problems and our experiments indicate that simply using the non-integral solutions of this LP in Lagrangian relaxation can empirically lead to reasonable compressions.
linear programming is mentioned in 5 sentences in this paper.
Topics mentioned in this paper:
Beltagy, Islam and Erk, Katrin and Mooney, Raymond
Background
Formally, from equation 3, the most probable interpretation, is the one that minimizes 27.61% Ar(d(7“))p. In case of p = 1, and given that all d (7“) are linear equations, then minimizing the sum requires solving a linear program , which, compared to inference in other probabilistic logics such as MLNs, can be done relatively efficiently using well-established techniques.
Introduction
On the other hand, inference in PSL reduces to a linear programming problem, which is theoretically and practically much more efficient.
PSL for STS
PSL’s inference is actually an iterative process where in each iteration a grounding phase is followed by an optimization phase (solving the linear program ).
linear programming is mentioned in 3 sentences in this paper.
Topics mentioned in this paper:
Chang, Yin-Wen and Rush, Alexander M. and DeNero, John and Collins, Michael
Adding Back Constraints
In general, it can be shown that Lagrangian relaxation is only guaranteed to solve a linear programming relaxation of the underlying combinatorial problem.
Related Work
General linear programming approaches have also been applied to word alignment problems.
Related Work
(2006) formulate the word alignment problem as quadratic assignment problem and solve it using an integer linear programming solver.
linear programming is mentioned in 3 sentences in this paper.
Topics mentioned in this paper: