Reducibility Among Combinatorial Problems

From MaRDI portal
Publication:3565237

DOI10.1007/978-3-540-68279-0_8zbMath1187.90014OpenAlexW1975442866MaRDI QIDQ3565237

Richard M. Karp

Publication date: 3 June 2010

Published in: 50 Years of Integer Programming 1958-2008 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-68279-0_8




Related Items (45)

Unnamed ItemOn the complexity of working set selectionA dynamic programming algorithm for tree-like weighted set packing problemForming \(k\) coalitions and facilitating relationships in social networksApproximation algorithms for clustering with dynamic pointsDynamic programming for the subset sum problemA new formula for the decycling number of regular graphsA lower bound for the breakpoint phylogeny problemPreprocessing to reduce the search space: antler structures for feedback vertex setBalancing U-type assembly lines with human-robot collaborationOn the optimal rank-1 approximation of matrices in the Chebyshev normReducing hypergraph coloring to clique searchStrategies for parallel unaware cleanersClustering in Hypergraphs to Minimize Average Edge Service TimeComputing a feedback arc set using PageRankOn the impact of running intersection inequalities for globally solving polynomial optimization problemsA faster cryptographer's Conspiracy SantaAn ETH-Tight Exact Algorithm for Euclidean TSPUnnamed ItemUnnamed ItemDivide-and-price: a decomposition algorithm for solving large railway crew scheduling problems\textsc{max-cut} and containment relations in graphsGraph coloring approach with new upper bounds for the chromatic number: team building applicationRectangle packing with additional restrictionsControl: a perspectiveComputational complexity of \(k\)-block conjugacyPolicy analysis for administrative role-based access controlNotes on computational-to-statistical gaps: predictions using statistical physicsMinimizing a sum of clipped convex functionsA quantum walk-assisted approximate algorithm for bounded NP optimisation problemsTravelling salesman problem in tissue P systems with costsFinding Hamiltonian circuits in quasi-adjoint graphsApproximate Dynamic Programming based on High Dimensional Model RepresentationInteger programming models for the multidimensional assignment problem with star costsA wide-ranging computational comparison of high-performance graph colouring algorithmsFinding the longest isometric cycle in a graphHitting subgraphs in \(P_4\)-tidy graphsOn the integrality ratio of the subtour LP for Euclidean TSPReal-time solving of computationally hard problems using optimal algorithm portfoliosContinuous relaxations for the traveling salesman problemEfficient Network Dismantling via Node Explosive Percolation*Finding a tree structure in a resolution proof is NP-completeSieving for twin smooth integers with solutions to the Prouhet-Tarry-Escott problemComplexity of Restricted Variants of Skolem and Related ProblemsUnnamed Item




This page was built for publication: Reducibility Among Combinatorial Problems