This HTML5 document contains 36 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
dcthttp://purl.org/dc/terms/
dbohttp://dbpedia.org/ontology/
foafhttp://xmlns.com/foaf/0.1/
n8https://global.dbpedia.org/id/
dbthttp://dbpedia.org/resource/Template:
rdfshttp://www.w3.org/2000/01/rdf-schema#
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
owlhttp://www.w3.org/2002/07/owl#
wikipedia-enhttp://en.wikipedia.org/wiki/
provhttp://www.w3.org/ns/prov#
dbphttp://dbpedia.org/property/
dbchttp://dbpedia.org/resource/Category:
xsdhhttp://www.w3.org/2001/XMLSchema#
wikidatahttp://www.wikidata.org/entity/
dbrhttp://dbpedia.org/resource/

Statements

Subject Item
dbr:Configuration_linear_program
dbo:wikiPageWikiLink
dbr:Karmarkar-Karp_bin_packing_algorithms
Subject Item
dbr:Karmarkar-Karp_bin_packing_algorithms
rdfs:label
Karmarkar-Karp bin packing algorithms
rdfs:comment
The Karmarkar-Karp (KK) bin packing algorithms are several related approximation algorithm for the bin packing problem. The bin packing problem is a problem of packing items of different sizes into bins of identical capacity, such that the total number of bins is as small as possible. Finding the optimal solution is computationally hard. Karmarkar and Karp devised an algorithm that runs in polynomial time and finds a solution with at most bins, where OPT is the number of bins in the optimal solution. They also devised several other algorithms with slightly different approximation guarantees and run-time bounds.
dct:subject
dbc:Bin_packing
dbo:wikiPageID
69706395
dbo:wikiPageRevisionID
1075017207
dbo:wikiPageWikiLink
dbr:Integer_programming dbr:Dual_linear_program dbr:Separation_oracle dbr:Bin_packing_problem dbr:Basic_feasible_solution dbr:Richard_M._Karp dbr:Approximation_algorithm dbr:Ellipsoid_method dbr:Configuration_linear_program dbr:NP-hardness dbr:Next-fit_bin_packing dbr:Narendra_Karmarkar dbr:Knapsack_problem dbr:Polynomial-time dbc:Bin_packing dbr:High-multiplicity_bin_packing
owl:sameAs
n8:GGx7D wikidata:Q110555082
dbp:wikiPageUsesTemplate
dbt:Reflist dbt:Refimprove dbt:Clarify dbt:Multiple_issues dbt:More_footnotes
dbo:abstract
The Karmarkar-Karp (KK) bin packing algorithms are several related approximation algorithm for the bin packing problem. The bin packing problem is a problem of packing items of different sizes into bins of identical capacity, such that the total number of bins is as small as possible. Finding the optimal solution is computationally hard. Karmarkar and Karp devised an algorithm that runs in polynomial time and finds a solution with at most bins, where OPT is the number of bins in the optimal solution. They also devised several other algorithms with slightly different approximation guarantees and run-time bounds. The KK algorithms were considered a breakthrough in the study of bin packing: the previously-known algorithms found multiplicative approximation, where the number of bins was at most for some constants , or at most . The KK algorithms were the first ones to attain an additive approximation.
prov:wasDerivedFrom
wikipedia-en:Karmarkar-Karp_bin_packing_algorithms?oldid=1075017207&ns=0
dbo:wikiPageLength
31093
foaf:isPrimaryTopicOf
wikipedia-en:Karmarkar-Karp_bin_packing_algorithms
Subject Item
dbr:Bin_packing_problem
dbo:wikiPageWikiLink
dbr:Karmarkar-Karp_bin_packing_algorithms
Subject Item
dbr:Separation_oracle
dbo:wikiPageWikiLink
dbr:Karmarkar-Karp_bin_packing_algorithms
Subject Item
wikipedia-en:Karmarkar-Karp_bin_packing_algorithms
foaf:primaryTopic
dbr:Karmarkar-Karp_bin_packing_algorithms