---
title: "Optimization in Coreference Resolution is not — Klenner 2009"
description: "The paper tackles a practical obstacle to using Zero-One Integer Linear Programming (ILP) for coreference resolution."
authors: ["Manfred Klenner", "Étienne Ailloud"]
year: 2009
venue: "Proceedings of the 12th Conference of the European Chapter of the ACL (EACL 2009)"
source: "https://aclanthology.org/E09-1051/"
licence: "CC BY-NC-SA 3.0 (ACL Anthology, before 2016)"
licence_url: "https://creativecommons.org/licenses/by-nc-sa/3.0/"
summary_licence: "Elamur Cosmic License"
canonical: "https://research.elamur.ai/free/papers/klenner-2009-optimization-coreference-resolution-is-not/"
---
[Elamur Research](https://md.research.elamur.ai/) · [this page in HTML](https://research.elamur.ai/free/papers/klenner-2009-optimization-coreference-resolution-is-not/)

[home](https://md.research.elamur.ai/) / [papers](https://md.research.elamur.ai/free/papers/) / [2009](https://md.research.elamur.ai/free/papers/2009/) / Optimization in Coreference Resolution is not Needed: A Nearly-Optimal Algorithm with Intensional Constraints

# Optimization in Coreference Resolution is not Needed: A Nearly-Optimal Algorithm with Intensional Constraints

**Authors:** [Manfred Klenner](https://md.research.elamur.ai/free/authors/manfred-klenner/), Étienne Ailloud · **Year:** 2009 · **Venue:** Proceedings of the 12th Conference of the European Chapter of the ACL (EACL 2009) · **Licence:** [CC BY-NC-SA 3.0 (ACL Anthology, before 2016)](https://creativecommons.org/licenses/by-nc-sa/3.0/)

**Links:** [Publisher's page](https://aclanthology.org/E09-1051/) · [PDF](https://aclanthology.org/E09-1051.pdf) · [OpenAlex](https://openalex.org/W7098366563)

**Citations:** 0 citations (openalex-snapshot · 2026-10-14) · [5](#cited-by) in our library, of the 140673 papers whose bibliographies we read

## Summary
The paper tackles a practical obstacle to using Zero-One Integer Linear Programming (ILP) for coreference resolution. Global constraints such as transitivity, together with exclusivity rules derived from binding, are needed to make the decisions of a pairwise classifier consistent. However, standard ILP requires every instance of these constraints to be written out in advance, which quickly becomes intractable. The authors adapt the Balas (1965) algorithm so that constraints are handled intensionally, meaning instances are generated only when the search actually needs them. Weights come from a TiMBL memory-based pairwise classifier, converted into classification costs. Experiments on German use the TüBa-D/Z coreference corpus with five-fold cross-validation. The central finding is that the first consistent solution found by the search (Balas-First) is as good as the fully optimized one in F-measure, and even marginally better. This matters because exhaustive NP-complete optimization can be skipped, which often cuts runtime substantially. Global consistency still significantly improves on the raw classifier output, and the Balas weight ordering beats a linear ordering.

## Key points
- **Data.** TüBa-D/Z is a treebank of 1,100 German newspaper texts and about 25,000 sentences. It contains 13,818 anaphoric, 1,031 cataphoric and 12,752 coreferential relations.
- **Candidate pairs and features.** The TiMBL classifier uses features such as distance, POS, grammatical function, head match, salience and semantic class. Candidate pairs are generated only within a 3-sentence sliding window.
- **Why intensional constraints are needed.** Writing out transitivity for about 150 noun phrases (roughly 30 sentences) already yields around 1,500,000 equations.
- **Approximating c-command.** Exclusivity relies on simple predicates (clause bound, np bound) instead of full syntactic c-command.
- **Ordering results.**
  - With all mentions, F rises from 62.83 to 64.27 (+1.44) when Balas ordering replaces linear ordering.
  - With true mentions, F rises from 76.08 to 78.90 (+2.82).
  - Without boundness enforcement constraints, solving takes quadratic time.

*Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.*

Fields: [Linguistics & languages](https://md.research.elamur.ai/free/shelves/linguistics/)

Topics: [Coreference resolution](https://md.research.elamur.ai/free/topics/coreference-resolution/)

## Cited by

Cited by

5 papers of our library cite it (of the 140673 whose bibliographies we read); 4 of them have a page here, 1 not yet.

- [Extending BART to Provide a Coreference Resolution System for German](https://md.research.elamur.ai/free/papers/broscheit-2010-extending-bart-provide-coreference-resolution/)
- [Bootstrapping coreference resolution using word associations](https://md.research.elamur.ai/free/papers/kobdani-2011-bootstrapping-coreference-resolution-word-associations/)
- [Supervised Noun Phrase Coreference Research: The First Fifteen Years](https://md.research.elamur.ai/free/papers/ng-2010-supervised-noun-phrase-coreference-research/)
- [A Global Relaxation Labeling Approach to Coreference Resolution](https://md.research.elamur.ai/free/papers/sapena-2010-global-relaxation-labeling-approach-coreference/)

## Cite

The paper itself, not this page. BibTeX from the library's record of the work.

```bibtex
@inproceedings{klenner2009optimization,
  title = {{Optimization in Coreference Resolution is not Needed: A Nearly-Optimal Algorithm with Intensional Constraints}},
  author = {Klenner, Manfred and Ailloud, Étienne},
  booktitle = {Proceedings of the 12th Conference of the European Chapter of the ACL (EACL 2009)},
  year = {2009},
  url = {https://aclanthology.org/E09-1051/}
}
```

- [← previous OntoNotes: The 90% Solution](https://md.research.elamur.ai/free/papers/pradhan-2009-ontonotes-90-solution/)
- [next → Paraphrase Identification as Probabilistic Quasi-Synchronous Recognition](https://md.research.elamur.ai/free/papers/das-2009-paraphrase-identification-as-probabilistic-quasi/)
- [↑ back to papers of 2009](https://md.research.elamur.ai/free/papers/2009/)

## References

24 references, 9 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

1. E. Althaus, N. Karamanis, and A. Koller. 2004. Computing locally coherent discourses. In Proc. of the ACL. [find](https://scholar.google.com/scholar?q=E%2E+Althaus%2C+N%2E+Karamanis%2C+and+A%2E+Koller%2E+2004%2E+Computing+locally+coherent+discourses%2E+In+Proc%2E+of+the+ACL%2E)
2. A. Bagga and B. Baldwin. 1998. Algorithms for scoring coreference chains. In Proceedings of the Linguistic Coreference Workshop at The First International Conference on Language Resources and Evaluation (LREC98), pages 563–566. [find](https://scholar.google.com/scholar?q=A%2E+Bagga+and+B%2E+Baldwin%2E+1998%2E+Algorithms+for+scoring+coreference+chains%2E+In+Proceedings+of+the+Linguistic+Coreference+Workshop+at+The+First+International+Conference+on+Language+Resources+and+Evaluati) [our card](https://md.research.elamur.ai/free/papers/bagga-1998-algorithms-scoring-coreference-chains/)
3. E. Balas. 1965. An additive algorithm for solving linear programs with zero-one variables. Operations Research, 13(4):517–546. [find](https://scholar.google.com/scholar?q=E%2E+Balas%2E+1965%2E+An+additive+algorithm+for+solving+linear+programs+with+zero%2Done+variables%2E+Operations+Research%2C+13%284%29%3A517%E2%80%93546%2E)
4. J.W. Chinneck. 2004. Practical optimization: a gentle introduction. Electronic document: [http://www.sce.carleton.ca/faculty/chinneck/po.html](http://www.sce.carleton.ca/faculty/chinneck/po.html). [↗](http://www.sce.carleton.ca/faculty/chinneck/po.html)
5. W. Daelemans, J. Zavrel, K. van der Sloot, and A. van den Bosch. 2004. TiMBL: Tilburg Memory-Based Learner. [find](https://scholar.google.com/scholar?q=W%2E+Daelemans%2C+J%2E+Zavrel%2C+K%2E+van+der+Sloot%2C+and+A%2E+van+den+Bosch%2E+2004%2E+TiMBL%3A+Tilburg+Memory%2DBased+Learner%2E)
6. P. Denis and J. Baldridge. 2007. Joint determination of anaphoricity and coreference resolution using integer programming. Proceedings of NAACL HLT, pages 236–243. [find](https://scholar.google.com/scholar?q=P%2E+Denis+and+J%2E+Baldridge%2E+2007%2E+Joint+determination+of+anaphoricity+and+coreference+resolution+using+integer+programming%2E+Proceedings+of+NAACL+HLT%2C+pages+236%E2%80%93243%2E) [our card](https://md.research.elamur.ai/free/papers/denis-2007-joint-determination-anaphoricity-coreference-resolution/)
7. P. Denis and J. Baldridge. 2008. Specialized models and ranking for coreference resolution. In Proceedings of the Empirical Methods in Natural Language Processing (EMNLP 2008), Hawaii, USA. To appear. [find](https://scholar.google.com/scholar?q=P%2E+Denis+and+J%2E+Baldridge%2E+2008%2E+Specialized+models+and+ranking+for+coreference+resolution%2E+In+Proceedings+of+the+Empirical+Methods+in+Natural+Language+Processing+%28EMNLP+2008%29%2C+Hawaii%2C+USA%2E+To+appear%2E) [our card](https://md.research.elamur.ai/free/papers/denis-2008-specialized-models-ranking-coreference-resolution/)
8. J.R. Finkel and C.D. Manning. 2008. Enforcing transitivity in coreference resolution. Association for Computational Linguistics. [find](https://scholar.google.com/scholar?q=J%2ER%2E+Finkel+and+C%2ED%2E+Manning%2E+2008%2E+Enforcing+transitivity+in+coreference+resolution%2E+Association+for+Computational+Linguistics%2E) [our card](https://md.research.elamur.ai/free/papers/finkel-2008-enforcing-transitivity-coreference-resolution/)
9. E. Hinrichs, K. Filippova, and H. Wunsch. 2005. A data-driven approach to pronominal anaphora resolution in German. In Proc. of RANLP ’05. [find](https://scholar.google.com/scholar?q=E%2E+Hinrichs%2C+K%2E+Filippova%2C+and+H%2E+Wunsch%2E+2005%2E+A+data%2Ddriven+approach+to+pronominal+anaphora+resolution+in+German%2E+In+Proc%2E+of+RANLP+%E2%80%9905%2E)
10. M. Klenner and É. Ailloud. 2008. Enhancing coreference clustering. In C. Johansson, editor, Proc. of the Second Workshop on Anaphora Resolution (WAR II), volume 2 of NEALT Proceedings Series, pages 31–40, Bergen, Norway. [find](https://scholar.google.com/scholar?q=M%2E+Klenner+and+E%CC%81%2E+Ailloud%2E+2008%2E+Enhancing+coreference+clustering%2E+In+C%2E+Johansson%2C+editor%2C+Proc%2E+of+the+Second+Workshop+on+Anaphora+Resolution+%28WAR+II%29%2C+volume+2+of+NEALT+Proceedings+Series%2C+pages+3)
11. M. Klenner. 2007. Enforcing consistency on coreference sets. In Recent Advances in Natural Language Processing (RANLP), pages 323–328, September. [find](https://scholar.google.com/scholar?q=M%2E+Klenner%2E+2007%2E+Enforcing+consistency+on+coreference+sets%2E+In+Recent+Advances+in+Natural+Language+Processing+%28RANLP%29%2C+pages+323%E2%80%93328%2C+September%2E)
12. X. Luo, A. Ittycheriah, H. Jing, N. Kambhatla, and S. Roukos. 2004. A mention-synchronous coreference resolution algorithm based on the Bell tree. Proceedings of the 42nd Annual Meeting on Association for Computational Linguistics. [find](https://scholar.google.com/scholar?q=X%2E+Luo%2C+A%2E+Ittycheriah%2C+H%2E+Jing%2C+N%2E+Kambhatla%2C+and+S%2E+Roukos%2E+2004%2E+A+mention%2Dsynchronous+coreference+resolution+algorithm+based+on+the+Bell+tree%2E+Proceedings+of+the+42nd+Annual+Meeting+on+Association) [our card](https://md.research.elamur.ai/free/papers/luo-2004-mention-synchronous-coreference-resolution-algorithm/)
13. X. Luo. 2005. On coreference resolution performance metrics. In Proceedings of the conference on Human Language Technology and Empirical Methods in Natural Language Processing, pages 25–32. Association for Computational Linguistics Morristown, NJ, USA. [find](https://scholar.google.com/scholar?q=X%2E+Luo%2E+2005%2E+On+coreference+resolution+performance+metrics%2E+In+Proceedings+of+the+conference+on+Human+Language+Technology+and+Empirical+Methods+in+Natural+Language+Processing%2C+pages+25%E2%80%9332%2E+Associatio) [our card](https://md.research.elamur.ai/free/papers/luo-2005-coreference-resolution-performance-metrics/)
14. T. Marciniak and M. Strube. 2005. Beyond the pipeline: Discrete optimization in NLP. In Proc. of the CoNLL. [find](https://scholar.google.com/scholar?q=T%2E+Marciniak+and+M%2E+Strube%2E+2005%2E+Beyond+the+pipeline%3A+Discrete+optimization+in+NLP%2E+In+Proc%2E+of+the+CoNLL%2E)
15. K. Naumann. 2006. Manual for the annotation of indocument referential relations. Electronic document: [http://www.sfs.uni-tuebingen.de/de_tuebadz.shtml](http://www.sfs.uni-tuebingen.de/de_tuebadz.shtml). [↗](http://www.sfs.uni-tuebingen.de/de_tuebadz.shtml)
16. V. Ng and C. Cardie. 2002. Improving machine learning approaches to coreference resolution. In Proc. of the ACL. [find](https://scholar.google.com/scholar?q=V%2E+Ng+and+C%2E+Cardie%2E+2002%2E+Improving+machine+learning+approaches+to+coreference+resolution%2E+In+Proc%2E+of+the+ACL%2E) [our card](https://md.research.elamur.ai/free/papers/ng-2002-improving-machine-learning-approaches-coreference/)
17. C. Nicolae and G. Nicolae. 2006. Best Cut: A graph algorithm for coreference resolution. In Proceedings of the 2006 Conference on Empirical Methods in Natural Language Processing, pages 275–283. Association for Computational Linguistics. [find](https://scholar.google.com/scholar?q=C%2E+Nicolae+and+G%2E+Nicolae%2E+2006%2E+Best+Cut%3A+A+graph+algorithm+for+coreference+resolution%2E+In+Proceedings+of+the+2006+Conference+on+Empirical+Methods+in+Natural+Language+Processing%2C+pages+275%E2%80%93283%2E+Assoc)
18. C.H. Papadimitriou and K. Steiglitz. 1998. Combinatorial Optimization: Algorithms and Complexity. Dover Publications. [find](https://scholar.google.com/scholar?q=C%2EH%2E+Papadimitriou+and+K%2E+Steiglitz%2E+1998%2E+Combinatorial+Optimization%3A+Algorithms+and+Complexity%2E+Dover+Publications%2E)
19. S.P. Ponzetto and M. Strube. 2006. Exploiting semantic role labeling, WordNet and Wikipedia for coreference resolution. In Proc. of HLT-NAACL, volume 6, pages 192–199. [find](https://scholar.google.com/scholar?q=S%2EP%2E+Ponzetto+and+M%2E+Strube%2E+2006%2E+Exploiting+semantic+role+labeling%2C+WordNet+and+Wikipedia+for+coreference+resolution%2E+In+Proc%2E+of+HLT%2DNAACL%2C+volume+6%2C+pages+192%E2%80%93199%2E) [our card](https://md.research.elamur.ai/free/papers/ponzetto-2006-exploiting-semantic-role-labeling-wordnet/)
20. V. Punyakanok, D. Roth, W. Yih, and D. Zimak. 2004. Semantic role labeling via integer linear programming inference. In Proc. of the COLING. [find](https://scholar.google.com/scholar?q=V%2E+Punyakanok%2C+D%2E+Roth%2C+W%2E+Yih%2C+and+D%2E+Zimak%2E+2004%2E+Semantic+role+labeling+via+integer+linear+programming+inference%2E+In+Proc%2E+of+the+COLING%2E)
21. S. Riedel and J. Clarke. 2006. Incremental integer linear programming for non-projective dependency parsing. In Proc. of the EMNLP. [find](https://scholar.google.com/scholar?q=S%2E+Riedel+and+J%2E+Clarke%2E+2006%2E+Incremental+integer+linear+programming+for+non%2Dprojective+dependency+parsing%2E+In+Proc%2E+of+the+EMNLP%2E)
22. W.M. Soon, H.T. Ng, and D.C.Y. Lim. 2001. A machine learning approach to coreference resolution of noun phrases. Computational Linguistics, 27(4):521–544. [find](https://scholar.google.com/scholar?q=W%2EM%2E+Soon%2C+H%2ET%2E+Ng%2C+and+D%2EC%2EY%2E+Lim%2E+2001%2E+A+machine+learning+approach+to+coreference+resolution+of+noun+phrases%2E+Computational+Linguistics%2C+27%284%29%3A521%E2%80%93544%2E) [our card](https://md.research.elamur.ai/free/papers/soon-2001-machine-learning-approach-coreference-resolution/)
23. H. Telljohann, E.W. Hinrichs, S. Kübler, and H. Zinsmeister. 2005. Stylebook for the Tübingen treebank of written German (TüBa-D/Z). Seminar fur Sprachwissenschaft, Universität Tübingen, Tübingen, Germany. [find](https://scholar.google.com/scholar?q=H%2E+Telljohann%2C+E%2EW%2E+Hinrichs%2C+S%2E+Ku%CC%88bler%2C+and+H%2E+Zinsmeister%2E+2005%2E+Stylebook+for+the+Tu%CC%88bingen+treebank+of+written+German+%28Tu%CC%88Ba%2DD%2FZ%29%2E+Seminar+fur+Sprachwissenschaft%2C+Universita%CC%88t+Tu%CC%88bingen%2C+Tu%CC%88binge)
24. Y. Versley. 2006. A constraint-based approach to noun phrase coreference resolution in German newspaper text. In Konferenz zur Verarbeitung Natürlicher Sprache (KONVENS). [find](https://scholar.google.com/scholar?q=Y%2E+Versley%2E+2006%2E+A+constraint%2Dbased+approach+to+noun+phrase+coreference+resolution+in+German+newspaper+text%2E+In+Konferenz+zur+Verarbeitung+Natu%CC%88rlicher+Sprache+%28KONVENS%29%2E)