About: Bin covering problem

An Entity of Type: Thing, from Named Graph: http://dbpedia.org, within Data Space: dbpedia.org

In the bin covering problem, items of different sizes must be packed into a finite number of bins or containers, each of which must contain at least a certain given total size, in a way that maximizes the number of bins used. This problem is a dual of the bin packing problem: in bin covering, the bin sizes are bounded from below and the goal is to maximize their number; in bin packing, the bin sizes are bounded from above and the goal is to minimize their number. The problem is NP-hard, but there are various efficient approximation algorithms:

Property Value
dbo:abstract
  • In the bin covering problem, items of different sizes must be packed into a finite number of bins or containers, each of which must contain at least a certain given total size, in a way that maximizes the number of bins used. This problem is a dual of the bin packing problem: in bin covering, the bin sizes are bounded from below and the goal is to maximize their number; in bin packing, the bin sizes are bounded from above and the goal is to minimize their number. The problem is NP-hard, but there are various efficient approximation algorithms: * Algorithms covering at least 1/2, 2/3 or 3/4 of the optimum bin count asymptotically, running in time respectively. * An asymptotic PTAS, algorithms with bounded worst-case behavior whose expected behavior is asymptotically-optimal for some discrete distributions, and a learning algorithm with asymptotically optimal expected behavior for all discrete distributions. * An asymptotic FPTAS. (en)
dbo:wikiPageExternalLink
dbo:wikiPageID
  • 65887746 (xsd:integer)
dbo:wikiPageLength
  • 13838 (xsd:nonNegativeInteger)
dbo:wikiPageRevisionID
  • 1101564625 (xsd:integer)
dbo:wikiPageWikiLink
dbp:wikiPageUsesTemplate
dcterms:subject
rdfs:comment
  • In the bin covering problem, items of different sizes must be packed into a finite number of bins or containers, each of which must contain at least a certain given total size, in a way that maximizes the number of bins used. This problem is a dual of the bin packing problem: in bin covering, the bin sizes are bounded from below and the goal is to maximize their number; in bin packing, the bin sizes are bounded from above and the goal is to minimize their number. The problem is NP-hard, but there are various efficient approximation algorithms: (en)
rdfs:label
  • Bin covering problem (en)
owl:sameAs
prov:wasDerivedFrom
foaf:isPrimaryTopicOf
is dbo:wikiPageRedirects of
is dbo:wikiPageWikiLink of
is foaf:primaryTopic of
Powered by OpenLink Virtuoso    This material is Open Knowledge     W3C Semantic Web Technology     This material is Open Knowledge    Valid XHTML + RDFa
This content was extracted from Wikipedia and is licensed under the Creative Commons Attribution-ShareAlike 3.0 Unported License