Approximation of the Quadratic Knapsack Problem

References

• Alon N, Arora S, Manokaran R, Moshkovitz D, Weinstein O (2011) Inapproximabilty of densest k-subgraph from average case hardness. Technical report, Computer Science Department, Princeton University, Princeton, NJ.Google Scholar
• Arora S, Karger D, Karpinski M (1999) Polynomial time approximation schemes for dense instances of NP-hard problems. J. Comput. System Sci. 58(1):193–210.Crossref, Google Scholar
• Baker BS (1994) Approximation algorithms for NP-complete problems on planar graphs. J. ACM 41(1):153–180.Crossref, Google Scholar
• Bernhart F, Kainen PC (1979) The book thickness of a graph. J. Combinatorial Theory, Ser. B 27(3):320–331.Crossref, Google Scholar
• Bhaskara A, Charikar M, Chlamtac E, Feige U, Vijayaraghavan A (2010) Detecting high log-densities: An O(n1/4) approximation for densest k-subgraph. Proc. 42nd ACM Sympos. Theory Comput., Cambridge, MA, 201–210.Crossref, Google Scholar
• Bodlaender HL (1996) A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput. 25(6):1305–1317.Crossref, Google Scholar
• Bodlaender HL (1998) A partial k-arboretum of graphs with bounded treewidth. Theoret. Comput. Sci. 209(1–2):1–45.Crossref, Google Scholar
• Bodlaender HL, Koster AMCA (2008) Combinatorial optimization on graphs of bounded treewidth. Comput. J. 51(3):255–269.Crossref, Google Scholar
• Chen D, Fleischer R, Li J (2011) Densest k-subgraph approximation on intersection graphs. Jansen K, Solis-Oba R, eds. WAOA ’10: Proc. 8th Internat. Conf. Approximation Online Algorithms, Lecture Notes in Computer Science, Vol. 6534 (Springer, New York), 83–93.Crossref, Google Scholar
• Chung FRK, Leighton FT, Rosenberg AL (1987) Embedding graphs in books: A layout problem with applications to VLSI design. SIAM J. Algebraic Discrete Methods 8(1):33–58.Crossref, Google Scholar
• Corneil DG, Perl Y (1984) Clustering and domination in perfect graphs. Discrete Appl. Math. 9(1):27–39.Crossref, Google Scholar
• Demaine ED, Hajiaghayi MT, Kawarabayashi K (2005) Algorithmic graph minor theory: Decomposition, approximation, and coloring. FOCS 2005: Proc. 46th Sympos. Foundations Comput. Sci., Pittsburgh, PA, 637–646.Crossref, Google Scholar
• Diestel R (2006) Graph Theory (Springer, Berlin).Google Scholar
• Feige U (2002) Relations between average case complexity and approximation complexity. STOC ’02: Proc. 34th Sympos. Theory Comput. (ACM, New York), 534–543.Crossref, Google Scholar
• Feige U, Peleg D, Kortsarz G (2001) The dense k-subgraph problem. Algorithmica 29(3):410–421.Crossref, Google Scholar
• Fomeni FD, Letchford AN (2014) A dynamic programming heuristic for the quadratic knapsack problem. INFORMS J. Comput. 26(1):173–182.Link, Google Scholar
• Kainen PC, Overbay S (2003) Book embeddings of graphs and a theorem of Whitney. Technical Report GUGU-2/25/03, Georgetown University, Washington, DC.Google Scholar
• Keil JM, Brecht TB (1991) The complexity of clustering in planar graphs. J. Combinatorial Math. Combinatorial Comput. 9:155–159.Google Scholar
• Kellerer H, Strusevich VA (2010) Fully polynomial approximation schemes for a symmetric quadratic knapsack problem and its scheduling applications. Algorithmica 57(4):769–795.Crossref, Google Scholar
• Kellerer H, Strusevich VA (2012) The symmetric quadratic knapsack problem: Approximation and scheduling applications. 4OR 10(2):111–161.Crossref, Google Scholar
• Kellerer H, Pferschy U, Pisinger D (2004) Knapsack Problems (Springer, Berlin).Crossref, Google Scholar
• Khot S (2006) Ruling out PTAS for graph min-bisection, dense k-subgraph, and bipartite clique. SIAM J. Comput. 36(4):1025–1071.Crossref, Google Scholar
• Lovász L (2006) Graph minor theory. Bull. Amer. Math. Soc. 43(1):75–86.Crossref, Google Scholar
• Moore C, Robson JM (2001) Hard tiling problems with simple tiles. Discrete Comput. Geometry 26(4):573–590.Crossref, Google Scholar
• Nonner T (2016) PTAS for densest k-subgraph in interval graphs. Algorithmica 74(1):528–539.Crossref, Google Scholar
• Oum S, Seymour P (2006) Approximating clique-width and branch-width. J. Combinatorial Theory, Ser. B 96(4):514–528.Crossref, Google Scholar
• Overbay S (2007) Graphs with small book thickness. Missouri J. Math. Sci. 19(2):121–130.Crossref, Google Scholar
• Pferschy U, Schauer J (2009) The knapsack problem with conflict graphs. J. Graph Algorithms Appl. 13(2):233–249.Crossref, Google Scholar
• Pferschy U, Schauer J (2014) Approximating the quadratic knapsack problem on special graph classes. Kaklamanis C, Pruhs K, eds. WAOA ’13: Proc. 11th Internat. Conf. Approximation Online Algorithms, Lecture Notes in Computer Science, Vol. 8447 (Springer, New York), 61–72.Crossref, Google Scholar
• Pisinger D (2007) The quadratic knapsack problem—A survey. Discrete Appl. Math. 155(5):623–648.Crossref, Google Scholar
• Pisinger WD, Rasmussen AB, Sandvik R (2007) Solution of large quadratic knapsack problems through aggressive reduction. INFORMS J. Comput. 19(2):280–290.Link, Google Scholar
• Rader DJ Jr, Woeginger GJ (2002) The quadratic 0-1 knapsack problem with series-parallel support. Oper. Res. Lett. 30(3):159–166.Crossref, Google Scholar
• Raghavendra P, Steurer D, Tulsiani M (2012) Reductions between expansion problems. Proc. 2012 IEEE Conf. Computat. Complexity (CCC) (IEEE Computer Society, Los Alamitos, CA), 64–73.Crossref, Google Scholar
• Rose DJ (1974) On simple characterizations of k-trees. Discrete Math. 7(3–4):317–322.Crossref, Google Scholar
• Xu Z (2012) A strongly polynomial FPTAS for the symmetric quadratic knapsack problem. Eur. J. Oper. Res. 218(2):377–381.Crossref, Google Scholar
• Yannakakis M (1989) Embedding planar graphs in four pages. J. Comput. System Sci. 38(1):36–67.Crossref, Google Scholar