Vi studerar approximabiliteten av den klassiska quadratic knapsack problem (QKP) på speciella graf klasser. I detta fall anges inte de kvadratiska termerna för den objektiva funktionen för varje par av knapsack-poster. Istället en kantvägd graf G = (V, E) vars hörn representerar knapsack objekten inducerar en kvadratisk vinst pij för objekten i och j när de är intilliggande i G (dvs (i, j) E). Vi visar att problemet tillåter en FPTAS på grafer av avgränsad trädbredd och en PTAS på plana grafer och mer allmänt på H-mindre fria grafer. Detta resultat visas genom att använda en teknik av Demaine et al. (2005)................................................................ Vi visar också stark N P-hårdhet av QKP på grafer som är 3-bok inbäddbara, en naturlig graf klass som är relaterad till planar grafer. Dessutom kommer vi att hävda att problemet sannolikt kommer att ha en dålig ungefärlighet beteende på alla graf klasser som inkluderar den fullständiga grafen eller innehåller stora klichéer. Dessa hårdhet approximations resultat under vissa komplexa antaganden överförs från de tätaste k-subgraf problemet.
Pferschy och Schauer REF generalisera detta resultat till grafer av avgränsad trädbredd.
Approximation of the Quadratic Knapsack Problem
{'venue': 'INFORMS J. Comput.', 'journal': 'INFORMS J. Comput.', 'mag_field_of_study': ['Mathematics', 'Computer Science']}