Monge matrices make maximization manageable

U. Pferschy, R. Rudolf, G.J. Woeginger

    Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

    8 Citaten (Scopus)

    Samenvatting

    We continue the research on the effects of Monge structures in the area of combinatorial optimization. We show that three optimization problems become easy if the underlying cost matrix fulfills the Monge property: (A) The balanced max-cut problem, (B) the problem of computing minimum weight binary k-matchings and (C) the computation of longest paths in bipartite, edge-weighted graphs. In all three results, we first prove that the Monge structure imposes some special combinatorial property on the structure of the optimum solution, and then we exploit this combinatorial property to derive efficient algorithms.
    Originele taal-2Engels
    Pagina's (van-tot)245-254
    Aantal pagina's10
    TijdschriftOperations Research Letters
    Volume16
    Nummer van het tijdschrift5
    DOI's
    StatusGepubliceerd - 1994

    Vingerafdruk

    Duik in de onderzoeksthema's van 'Monge matrices make maximization manageable'. Samen vormen ze een unieke vingerafdruk.

    Citeer dit