HTML Microdata document

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

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

Namespace Prefixes

Prefix	IRI
dcterms	http://purl.org/dc/terms/
dbo	http://dbpedia.org/ontology/
foaf	http://xmlns.com/foaf/0.1/
n14	https://global.dbpedia.org/id/
dbt	http://dbpedia.org/resource/Template:
rdfs	http://www.w3.org/2000/01/rdf-schema#
rdf	http://www.w3.org/1999/02/22-rdf-syntax-ns#
owl	http://www.w3.org/2002/07/owl#
wikipedia-en	http://en.wikipedia.org/wiki/
dbp	http://dbpedia.org/property/
dbc	http://dbpedia.org/resource/Category:
prov	http://www.w3.org/ns/prov#
xsdh	http://www.w3.org/2001/XMLSchema#
wikidata	http://www.wikidata.org/entity/
dbr	http://dbpedia.org/resource/

Statements

Subject Item: dbr:David_Applegate
dbo:wikiPageWikiLink: dbr:Convex_volume_approximation
dbp:subDiscipline: dbr:Convex_volume_approximation

Subject Item: dbr:Volume
dbo:wikiPageWikiLink: dbr:Convex_volume_approximation

Subject Item: dbr:Convex_polytope
dbo:wikiPageWikiLink: dbr:Convex_volume_approximation

Subject Item: dbr:Convex_volume_approximation
rdfs:label: Convex volume approximation
rdfs:comment: In the analysis of algorithms, several authors have studied the computation of the volume of high-dimensional convex bodies, a problem that can also be used to model many other problems in combinatorial enumeration.Often these works use a black box model of computation in which the input is given by a subroutine for testing whether a point is inside or outside of the convex body, rather than by an explicit listing of the vertices or faces of a convex polytope.It is known that, in this model, no deterministic algorithm can achieve an accurate approximation, and even for an explicit listing of faces or vertices the problem is #P-hard.However, a joint work by Martin Dyer, Alan M. Frieze and Ravindran Kannan provided a randomized polynomial time approximation scheme for the problem,providing a
dcterms:subject: dbc:Approximation_algorithms dbc:Computational_geometry
dbo:wikiPageID: 22721042
dbo:wikiPageRevisionID: 1102260072
dbo:wikiPageWikiLink: dbr:Markov_chain_Monte_Carlo dbr:Martin_Dyer dbr:Combinatorial_enumeration dbr:Convex_body dbr:Volume dbr:Fulkerson_Prize dbr:Markov_chain_mixing_time dbr:Rejection_sampling dbr:Convex_polytope dbc:Approximation_algorithms dbr:Oracle_machine dbr:Sharp-P-complete dbr:Ravindran_Kannan dbr:Random_walk dbr:Klee's_measure_problem dbr:Polynomial_time_approximation_scheme dbc:Computational_geometry dbr:Analysis_of_algorithms dbr:Deterministic_algorithm dbr:Alan_M._Frieze
owl:sameAs: wikidata:Q7226628 n14:4tS8V
dbp:wikiPageUsesTemplate: dbt:R dbt:Reflist
dbo:abstract: In the analysis of algorithms, several authors have studied the computation of the volume of high-dimensional convex bodies, a problem that can also be used to model many other problems in combinatorial enumeration.Often these works use a black box model of computation in which the input is given by a subroutine for testing whether a point is inside or outside of the convex body, rather than by an explicit listing of the vertices or faces of a convex polytope.It is known that, in this model, no deterministic algorithm can achieve an accurate approximation, and even for an explicit listing of faces or vertices the problem is #P-hard.However, a joint work by Martin Dyer, Alan M. Frieze and Ravindran Kannan provided a randomized polynomial time approximation scheme for the problem,providing a sharp contrast between the capabilities of randomized and deterministic algorithms. The main result of the paper is a randomized algorithm for finding an approximation to the volume of a convex body in -dimensional Euclidean space by assuming the existence of a membership oracle. The algorithm takes time bounded by a polynomial in , the dimension of and .The algorithm combines two ideas: * By using a Markov chain Monte Carlo (MCMC) method, it is possible to generate points that are nearly uniformly randomly distributed within a given convex body. The basic scheme of the algorithm is a nearly uniform sampling from within by placing a grid consisting of -dimensional cubes and doing a random walk over these cubes. By using the theory of rapidly mixing Markov chains, they show that it takes a polynomial time for the random walk to settle down to being a nearly uniform distribution. * By using rejection sampling, it is possible to compare the volumes of two convex bodies, one nested within another, when their volumes are within a small factor of each other. The basic idea is to generate random points within the outer of the two bodies, and to count how often those points are also within the inner body. The given convex body can be approximated by a sequence of nested bodies, eventually reaching one of known volume (a hypersphere), with this approach used to estimate the factor by which the volume changes at each step of this sequence. Multiplying these factors gives the approximate volume of the original body. This work earned its authors the 1991 Fulkerson Prize.
prov:wasDerivedFrom: wikipedia-en:Convex_volume_approximation?oldid=1102260072&ns=0
dbo:wikiPageLength: 7313
foaf:isPrimaryTopicOf: wikipedia-en:Convex_volume_approximation

Subject Item: dbr:Approximating_the_volume_of_convex_bodies
dbo:wikiPageWikiLink: dbr:Convex_volume_approximation
dbo:wikiPageRedirects: dbr:Convex_volume_approximation

Subject Item: dbr:Klee's_measure_problem
dbo:wikiPageWikiLink: dbr:Convex_volume_approximation

Subject Item: dbr:Polynomial-time_algorithm_for_approximating_the_volume_of_convex_bodies
dbo:wikiPageWikiLink: dbr:Convex_volume_approximation
dbo:wikiPageRedirects: dbr:Convex_volume_approximation

Subject Item: dbr:Polynomial_time_algorithm_for_approximating_the_volume_of_convex_bodies
dbo:wikiPageWikiLink: dbr:Convex_volume_approximation
dbo:wikiPageRedirects: dbr:Convex_volume_approximation

Subject Item: wikipedia-en:Convex_volume_approximation
foaf:primaryTopic: dbr:Convex_volume_approximation