Vi presenterar randomiserade approximationsalgoritmer för multi-criteria Max-TSP. För Max-STSP med k > 1 objektiva funktioner får vi en approximationsgrad på 1 k − ε för godtyckligt liten ε > 0. För Max-ATSP med k objektiva funktioner får vi en approximationsgrad på 1 Multi-Criteria Traveling Salesman Problem Den resande säljare problem (TSP) är ett av de mest grundläggande problemen i kombinatoriska optimering. Med tanke på en graf, är målet att hitta en Hamiltonian cykel av minimum eller maximal vikt. Vi överväger att hitta Hamiltonian cyklar av maximal vikt (Max-TSP). Ett exempel på Max-TSP är en komplett graf G = (V, E) med kantvikter w : E → N. Målet är att hitta en Hamiltonian cykel av maximal vikt. Vikten av en Hamiltonian cykel (eller, mer allmänt, av en delmängd av E) är summan av vikterna av dess kanter. Om G är oriktad, talar vi om Max-STSP (symmetrisk TSP). Om G är regisserad har vi Max-ATSP (asymmetrisk TSP). Både Max-STSP och Max-ATSP är NP-hårda och APX-hårda. Därför är vi i behov av approximationsalgoritmer. De för närvarande bästa approximationsalgoritmerna för Max-STSP och Max-ATSP uppnår approximativa proportioner på 61/81 respektive 2/3 [2, 5]. Cykelomslag är ett viktigt verktyg för att utforma approximationsalgoritmer för TSP. En cykel omslag av en graf är en uppsättning av vertex-avskiljande cykler sådan att varje vertex är en del av exakt en cykel. Hamiltonska cykler är speciella fall av cykel täcker som består av bara en cykel. Vikten av en maximal vikt cykel täcka är således en övre gräns för vikten av en maximal vikt Hamiltonian cykel. I motsats till Hamiltons cykler kan cykelomslag av lägsta eller högsta vikt beräknas effektivt med hjälp av matchande algoritmer [1]. I många optimeringsproblem finns det mer än en objektiv funktion. Överväg att köpa en bil: Vi kanske vill köpa en billig, snabb bil med en bra gas körsträcka. Hur avgör vi * En utökad abstrakt av detta verk kommer att visas i
Bläser et al. REF utformade de första randomiserade approximationsalgoritmerna för MC-Max-STSP och MC-Max-ATSP.
Approximating Multi-Criteria Max-TSP
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}