IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v203y2010i1p216-221.html
   My bibliography  Save this article

On the complexity of Slater's problems

Author

Listed:
  • Hudry, Olivier

Abstract

Given a tournament T, Slater's problem consists in determining a linear order (i.e. a complete directed graph without directed cycles) at minimum distance from T, the distance between T and a linear order O being the number of directed edges with different orientations in T and in O. This paper studies the complexity of this problem and of several variants of it: computing a Slater order, computing a Slater winner, checking that a given vertex is a Slater winner and so on.

Suggested Citation

  • Hudry, Olivier, 2010. "On the complexity of Slater's problems," European Journal of Operational Research, Elsevier, vol. 203(1), pages 216-221, May.
    • Handle: RePEc:eee:ejores:v:203:y:2010:i:1:p:216-221
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377-2217(09)00533-5
    Download Restriction: Full text for ScienceDirect subscribers only
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Hudry, Olivier, 2009. "A survey on the complexity of tournament solutions," Mathematical Social Sciences, Elsevier, vol. 57(3), pages 292-303, May.
    2. Olivier Hudry, 2004. "A note on “Banks winners in tournaments are difficult to recognize” by G. J. Woeginger," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 23(1), pages 113-114, August.
    3. Pierre Barthelemy, Jean & Monjardet, Bernard, 1981. "The median procedure in cluster analysis and social choice theory," Mathematical Social Sciences, Elsevier, vol. 1(3), pages 235-267, May.
    4. Gerhard J. Woeginger, 2003. "Banks winners in tournaments are difficult to recognize," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 20(3), pages 523-528, June.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Irène Charon & Olivier Hudry, 2010. "An updated survey on the linear ordering problem for weighted or unweighted tournaments," Annals of Operations Research, Springer, vol. 175(1), pages 107-158, March.
    2. Olivier Hudry, 2015. "Complexity results for extensions of median orders to different types of remoteness," Annals of Operations Research, Springer, vol. 225(1), pages 111-123, February.
    3. Juan Aparicio & Mercedes Landete & Juan F. Monge, 2020. "A linear ordering problem of sets," Annals of Operations Research, Springer, vol. 288(1), pages 45-64, May.
    4. Burak Can & Mohsen Pourpouneh & Ton Storcken, 2021. "An axiomatic characterization of the Slater rule," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 56(4), pages 835-853, May.
    5. Olivier Hudry & Bernard Monjardet, 2010. "Consensus theories: an oriented survey," Université Paris1 Panthéon-Sorbonne (Post-Print and Working Papers) halshs-00504974, HAL.
    6. Hudry, Olivier, 2012. "On the computation of median linear orders, of median complete preorders and of median weak orders," Mathematical Social Sciences, Elsevier, vol. 64(1), pages 2-10.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Irène Charon & Olivier Hudry, 2010. "An updated survey on the linear ordering problem for weighted or unweighted tournaments," Annals of Operations Research, Springer, vol. 175(1), pages 107-158, March.
    2. Hudry, Olivier, 2009. "A survey on the complexity of tournament solutions," Mathematical Social Sciences, Elsevier, vol. 57(3), pages 292-303, May.
    3. Olivier Hudry & Bernard Monjardet, 2010. "Consensus theories: An oriented survey," Documents de travail du Centre d'Economie de la Sorbonne 10057, Université Panthéon-Sorbonne (Paris 1), Centre d'Economie de la Sorbonne.
    4. Scott Moser, 2015. "Majority rule and tournament solutions," Chapters, in: Jac C. Heckelman & Nicholas R. Miller (ed.), Handbook of Social Choice and Voting, chapter 6, pages 83-101, Edward Elgar Publishing.
    5. Thomas Demuynck, 2014. "The computational complexity of rationalizing Pareto optimal choice behavior," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 42(3), pages 529-549, March.
    6. Demuynck, Thomas, 2011. "The computational complexity of rationalizing boundedly rational choice behavior," Journal of Mathematical Economics, Elsevier, vol. 47(4-5), pages 425-433.
    7. Felix Brandt & Florian Grundbacher, 2023. "The Banks Set and the Bipartisan Set May Be Disjoint," Papers 2308.01881, arXiv.org, revised Oct 2024.
    8. Fujun Hou, 2024. "A new social welfare function with a number of desirable properties," Papers 2403.16373, arXiv.org.
    9. Olivier Hudry, 2015. "Complexity results for extensions of median orders to different types of remoteness," Annals of Operations Research, Springer, vol. 225(1), pages 111-123, February.
    10. Hudry, Olivier, 2012. "On the computation of median linear orders, of median complete preorders and of median weak orders," Mathematical Social Sciences, Elsevier, vol. 64(1), pages 2-10.
    11. Brandt, Felix & Harrenstein, Paul & Seedig, Hans Georg, 2017. "Minimal extending sets in tournaments," Mathematical Social Sciences, Elsevier, vol. 87(C), pages 55-63.
    12. Fabrice Talla Nobibon & Laurens Cherchye & Yves Crama & Thomas Demuynck & Bram De Rock & Frits C. R. Spieksma, 2016. "Revealed Preference Tests of Collectively Rational Consumption Behavior: Formulations and Algorithms," Operations Research, INFORMS, vol. 64(6), pages 1197-1216, December.
    13. Yongjie Yang & Jiong Guo, 2017. "Possible winner problems on partial tournaments: a parameterized study," Journal of Combinatorial Optimization, Springer, vol. 33(3), pages 882-896, April.
    14. Hannu Salonen, 2014. "Aggregating and Updating Information," Czech Economic Review, Charles University Prague, Faculty of Social Sciences, Institute of Economic Studies, vol. 8(2), pages 55-67, October.
    15. Nehring, Klaus & Pivato, Marcus & Puppe, Clemens, 2014. "The Condorcet set: Majority voting over interconnected propositions," Journal of Economic Theory, Elsevier, vol. 151(C), pages 268-303.
    16. Nehring, Klaus & Pivato, Marcus & Puppe, Clemens, 2011. "Condorcet admissibility: Indeterminacy and path-dependence under majority voting on interconnected decisions," MPRA Paper 32434, University Library of Munich, Germany.
    17. Vincent Anesi, 2012. "A new old solution for weak tournaments," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 39(4), pages 919-930, October.
    18. Joseph, Rémy-Robert, 2010. "Making choices with a binary relation: Relative choice axioms and transitive closures," European Journal of Operational Research, Elsevier, vol. 207(2), pages 865-877, December.
    19. Marcus Pivato, 2013. "Voting rules as statistical estimators," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 40(2), pages 581-630, February.
    20. Dewan F. Wahid & Elkafi Hassini, 2022. "A Literature Review on Correlation Clustering: Cross-disciplinary Taxonomy with Bibliometric Analysis," SN Operations Research Forum, Springer, vol. 3(3), pages 1-42, September.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:ejores:v:203:y:2010:i:1:p:216-221. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.