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

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

Namespace Prefixes

PrefixIRI
dctermshttp://purl.org/dc/terms/
n29http://www.inf.ethz.ch/personal/gaertner/texts/own_work/
dbohttp://dbpedia.org/ontology/
n15http://dbpedia.org/resource/File:
foafhttp://xmlns.com/foaf/0.1/
n24https://www.cs.princeton.edu/~chazelle/pubs/
n4http://www.cs.uu.nl/research/techreps/repo/CS-2007/
n27http://www.inf.ethz.ch/personal/ybrise/data/papers/
n6https://global.dbpedia.org/id/
n25http://www.cs.ucdavis.edu/~amenta/pubs/
n7http://www.cs.uwaterloo.ca/~tmchan/
n16http://www.people.hbs.edu/dbell/
dbthttp://dbpedia.org/resource/Template:
rdfshttp://www.w3.org/2000/01/rdf-schema#
freebasehttp://rdf.freebase.com/ns/
n22http://commons.wikimedia.org/wiki/Special:FilePath/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
n21https://drops.dagstuhl.de/opus/volltexte/2008/1527/
owlhttp://www.w3.org/2002/07/owl#
n28http://www.inf.ethz.ch/personal/emo/PublFiles/
n23http://www.lix.polytechnique.fr/~nielsen/pdf/
n18http://cg.scs.carleton.ca/~morin/publications/facility/
n20http://www.almaden.ibm.com/u/kclarkson/lp/
wikipedia-enhttp://en.wikipedia.org/wiki/
dbphttp://dbpedia.org/property/
dbchttp://dbpedia.org/resource/Category:
provhttp://www.w3.org/ns/prov#
xsdhhttp://www.w3.org/2001/XMLSchema#
wikidatahttp://www.wikidata.org/entity/
goldhttp://purl.org/linguistics/gold/
dbrhttp://dbpedia.org/resource/
n10https://hal.archives-ouvertes.fr/hal-01621504/file/

Statements

Subject Item
dbr:LP-type_problem
rdf:type
dbo:Disease
rdfs:label
LP-type problem
rdfs:comment
In the study of algorithms, an LP-type problem (also called a generalized linear program) is an optimization problem that shares certain properties with low-dimensional linear programs and that may be solved by similar algorithms. LP-type problems include many important optimization problems that are not themselves linear programs, such as the problem of finding the smallest circle containing a given set of planar points. They may be solved by a combination of randomized algorithms in an amount of time that is linear in the number of elements defining the problem, and subexponential in the dimension of the problem.
foaf:depiction
n22:Smallest_circle_problem.svg
dcterms:subject
dbc:Computational_geometry dbc:Linear_programming
dbo:wikiPageID
34676009
dbo:wikiPageRevisionID
1124282962
dbo:wikiPageWikiLink
dbr:Hypercube dbr:Algorithm dbr:Pointwise_maximum dbr:1-center_problem dbr:Linear_time dbr:Discrete_Applied_Mathematics dbr:Convex_optimization dbr:Convex_set dbr:Violator_space dbr:Linear_program dbr:Journal_of_the_ACM dbr:Discrete_and_Computational_Geometry dbr:Rotating_calipers dbr:Randomized_algorithm dbr:Computational_geometry dbr:Lexicographic_order dbr:Smallest_circle_problem dbc:Computational_geometry n15:Lp_Balls.webm dbr:Bregman_divergence dbr:Facility_location dbr:Directed_acyclic_graph dbr:Prefix_(computer_science) dbr:Ordered_pair n15:Smallest_circle_problem.svg dbr:SIAM_Journal_on_Computing dbr:Unique_sink_orientation dbr:Convex_polytope dbr:Simplex_method dbr:Information_Processing_Letters dbr:Finite_element_method dbr:Proceedings_of_the_National_Academy_of_Sciences_of_the_United_States_of_America dbr:Linear_complementarity_problem dbr:Quasiconvex_function dbr:Optimization_problem dbc:Linear_programming dbr:Centerpoint_(geometry) dbr:Convex_hull dbr:Computational_Geometry_(journal) dbr:Ellipsoid dbr:Algorithmica dbr:Integer_program dbr:Symposium_on_Foundations_of_Computer_Science dbr:Symposium_on_Computational_Geometry dbr:Algorithmic_game_theory dbr:Diameter dbr:Function_of_a_real_variable dbr:Cardinality dbr:Symposium_on_Theory_of_Computing dbr:Mathematics_of_Operations_Research
dbo:wikiPageExternalLink
n4:2007-025.pdf n7:depth_soda.pdf n10:articleDGCI2017-RepresentationOfDigitalNoisyShapes.pdf n16:theorem%20on%20integer%20lattice.pdf n18:center-ijcga.pdf n20:p.pdf n21: n23:2008-SmallestInformationDisk-IPL.pdf n24:OptimizationFixedDim.pdf n25:helly.pdf n27:VS.pdf n28:SubexLinProg_ALG16_96.pdf n28:UniqueSink_FOCS42nd_01.pdf n29:mb.pdf n29:sampling.pdf n29:subex.pdf
owl:sameAs
n6:4pna7 freebase:m.0j2535_ wikidata:Q6459640
dbp:wikiPageUsesTemplate
dbt:Refend dbt:Reflist dbt:Harvs dbt:Math dbt:Refbegin dbt:! dbt:Citation dbt:Mvar dbt:Harvnb dbt:Harvtxt dbt:Mabs dbt:Radic
dbo:thumbnail
n22:Smallest_circle_problem.svg?width=300
dbo:abstract
In the study of algorithms, an LP-type problem (also called a generalized linear program) is an optimization problem that shares certain properties with low-dimensional linear programs and that may be solved by similar algorithms. LP-type problems include many important optimization problems that are not themselves linear programs, such as the problem of finding the smallest circle containing a given set of planar points. They may be solved by a combination of randomized algorithms in an amount of time that is linear in the number of elements defining the problem, and subexponential in the dimension of the problem.
gold:hypernym
dbr:Problem
prov:wasDerivedFrom
wikipedia-en:LP-type_problem?oldid=1124282962&ns=0
dbo:wikiPageLength
38815
foaf:isPrimaryTopicOf
wikipedia-en:LP-type_problem