UnivTrevesV1, Main, Exploration, bibRecord, 002D64

Deciding uniqueness in norm maximization

Identifieur interne : 002D64 ( Main/Exploration ); précédent : 002D63; suivant : 002D65

Deciding uniqueness in norm maximization

Auteurs : Peter Gritzmann [Allemagne] ; Victor Klee [États-Unis]

Source :

Mathematical Programming [ 0025-5610 ] ; 1992-05-01.

RBID : ISTEX:5CF3F3324CD79B6D3F78637D89EA42C1E9AE17D5

Descripteurs français

Pascal (Inist)
- Algorithme, Circumradius, Diamètre, Inradius, Largeur, Maximisation, Norm, Optimisation, Optimum global, Polytope, Problème NP dur, Programmation quadratique, Temps polynomial, Théorème unicité.

English descriptors

KwdEn :
- Algorithm, Diameter, Global optimum, Maximization, NP hard problem, Optimization, Polynomial time, Polytope, Quadratic programming, Uniqueness theorem, Width.

Abstract

Abstract: NP-hardness is established for the problem whose instance is a system of linear inequalities defining a polytopeP, and whose question is whether, onP, the global maximum of the Euclidean norm is attained at more than one vertex ofP. The NP-hardness persists even for the restricted problem in whichP is a full-dimensional parallelotope with one vertex at the origin. This makes it possible to establish NP-hardness for other uniqueness problems, including some from pseudoboolean programming and computational convexity.

Url:

https://api.istex.fr/document/5CF3F3324CD79B6D3F78637D89EA42C1E9AE17D5/fulltext/pdf

DOI: 10.1007/BF01581081

Affiliations:

Le document en format XML

<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">Deciding uniqueness in norm maximization</title>
<author><name sortKey="Gritzmann, Peter" sort="Gritzmann, Peter" uniqKey="Gritzmann P" first="Peter" last="Gritzmann">Peter Gritzmann</name>
</author>
<author><name sortKey="Klee, Victor" sort="Klee, Victor" uniqKey="Klee V" first="Victor" last="Klee">Victor Klee</name>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">ISTEX</idno>
<idno type="RBID">ISTEX:5CF3F3324CD79B6D3F78637D89EA42C1E9AE17D5</idno>
<date when="1992" year="1992">1992</date>
<idno type="doi">10.1007/BF01581081</idno>
<idno type="url">https://api.istex.fr/document/5CF3F3324CD79B6D3F78637D89EA42C1E9AE17D5/fulltext/pdf</idno>
<idno type="wicri:Area/Istex/Corpus">001093</idno>
<idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">001093</idno>
<idno type="wicri:Area/Istex/Curation">000F82</idno>
<idno type="wicri:Area/Istex/Checkpoint">001412</idno>
<idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">001412</idno>
<idno type="wicri:doubleKey">0025-5610:1992:Gritzmann P:deciding:uniqueness:in</idno>
<idno type="wicri:Area/Main/Merge">003341</idno>
<idno type="wicri:source">INIST</idno>
<idno type="RBID">Pascal:93-0190750</idno>
<idno type="wicri:Area/PascalFrancis/Corpus">001678</idno>
<idno type="wicri:Area/PascalFrancis/Curation">001368</idno>
<idno type="wicri:Area/PascalFrancis/Checkpoint">001470</idno>
<idno type="wicri:explorRef" wicri:stream="PascalFrancis" wicri:step="Checkpoint">001470</idno>
<idno type="wicri:doubleKey">0025-5610:1992:Gritzmann P:deciding:uniqueness:in</idno>
<idno type="wicri:Area/Main/Merge">003382</idno>
<idno type="wicri:Area/Main/Curation">002D64</idno>
<idno type="wicri:Area/Main/Exploration">002D64</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Deciding uniqueness in norm maximization</title>
<author><name sortKey="Gritzmann, Peter" sort="Gritzmann, Peter" uniqKey="Gritzmann P" first="Peter" last="Gritzmann">Peter Gritzmann</name>
<affiliation wicri:level="1"><country xml:lang="fr">Allemagne</country>
<wicri:regionArea>Fb IV, Mathematik, Universität Trier, Postfach 3825, W-5500, Trier</wicri:regionArea>
<wicri:noRegion>Trier</wicri:noRegion>
<wicri:noRegion>Trier</wicri:noRegion>
</affiliation>
</author>
<author><name sortKey="Klee, Victor" sort="Klee, Victor" uniqKey="Klee V" first="Victor" last="Klee">Victor Klee</name>
<affiliation wicri:level="4"><country xml:lang="fr">États-Unis</country>
<wicri:regionArea>Department of Mathematics, University of Washington, Seattle, WA</wicri:regionArea>
<placeName><region type="state">Washington (État)</region>
<settlement type="city">Seattle</settlement>
</placeName>
<orgName type="university">Université de Washington</orgName>
</affiliation>
</author>
</analytic>
<monogr></monogr>
<series><title level="j">Mathematical Programming</title>
<title level="j" type="abbrev">Mathematical Programming</title>
<idno type="ISSN">0025-5610</idno>
<idno type="eISSN">1436-4646</idno>
<imprint><publisher>Springer-Verlag</publisher>
<pubPlace>Berlin/Heidelberg</pubPlace>
<date type="published" when="1992-05-01">1992-05-01</date>
<biblScope unit="volume">57</biblScope>
<biblScope unit="issue">1-3</biblScope>
<biblScope unit="page" from="203">203</biblScope>
<biblScope unit="page" to="214">214</biblScope>
</imprint>
<idno type="ISSN">0025-5610</idno>
</series>
<idno type="istex">5CF3F3324CD79B6D3F78637D89EA42C1E9AE17D5</idno>
<idno type="DOI">10.1007/BF01581081</idno>
<idno type="ArticleID">BF01581081</idno>
<idno type="ArticleID">Art12</idno>
</biblStruct>
</sourceDesc>
<seriesStmt><idno type="ISSN">0025-5610</idno>
</seriesStmt>
</fileDesc>
<profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Algorithm</term>
<term>Diameter</term>
<term>Global optimum</term>
<term>Maximization</term>
<term>NP hard problem</term>
<term>Optimization</term>
<term>Polynomial time</term>
<term>Polytope</term>
<term>Quadratic programming</term>
<term>Uniqueness theorem</term>
<term>Width</term>
</keywords>
<keywords scheme="Pascal" xml:lang="fr"><term>Algorithme</term>
<term>Circumradius</term>
<term>Diamètre</term>
<term>Inradius</term>
<term>Largeur</term>
<term>Maximisation</term>
<term>Norm</term>
<term>Optimisation</term>
<term>Optimum global</term>
<term>Polytope</term>
<term>Problème NP dur</term>
<term>Programmation quadratique</term>
<term>Temps polynomial</term>
<term>Théorème unicité</term>
</keywords>
</textClass>
<langUsage><language ident="en">en</language>
</langUsage>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">Abstract: NP-hardness is established for the problem whose instance is a system of linear inequalities defining a polytopeP, and whose question is whether, onP, the global maximum of the Euclidean norm is attained at more than one vertex ofP. The NP-hardness persists even for the restricted problem in whichP is a full-dimensional parallelotope with one vertex at the origin. This makes it possible to establish NP-hardness for other uniqueness problems, including some from pseudoboolean programming and computational convexity.</div>
</front>
</TEI>
<affiliations><list><country><li>Allemagne</li>
<li>États-Unis</li>
</country>
<region><li>Washington (État)</li>
</region>
<settlement><li>Seattle</li>
</settlement>
<orgName><li>Université de Washington</li>
</orgName>
</list>
<tree><country name="Allemagne"><noRegion><name sortKey="Gritzmann, Peter" sort="Gritzmann, Peter" uniqKey="Gritzmann P" first="Peter" last="Gritzmann">Peter Gritzmann</name>
</noRegion>
</country>
<country name="États-Unis"><region name="Washington (État)"><name sortKey="Klee, Victor" sort="Klee, Victor" uniqKey="Klee V" first="Victor" last="Klee">Victor Klee</name>
</region>
</country>
</tree>
</affiliations>
</record>

Pour manipuler ce document sous Unix (Dilib)

EXPLOR_STEP=$WICRI_ROOT/Wicri/Rhénanie/explor/UnivTrevesV1/Data/Main/Exploration

HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 002D64 | SxmlIndent | more

HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 002D64 | SxmlIndent | more

Pour mettre un lien sur cette page dans le réseau Wicri

{{Explor lien
   |wiki=    Wicri/Rhénanie
   |area=    UnivTrevesV1
   |flux=    Main
   |étape=   Exploration
   |type=    RBID
   |clé=     ISTEX:5CF3F3324CD79B6D3F78637D89EA42C1E9AE17D5
   |texte=   Deciding uniqueness in norm maximization
}}

This area was generated with Dilib version V0.6.31.
Data generation: Sat Jul 22 16:29:01 2017. Site generation: Wed Feb 28 14:55:37 2024

Serveur d'exploration sur l'Université de Trèves

Deciding uniqueness in norm maximization

Deciding uniqueness in norm maximization

Source :

Descripteurs français

English descriptors

Abstract

Links toward previous steps (curation, corpus...)

Le document en format XML

Pour manipuler ce document sous Unix (Dilib)

Pour mettre un lien sur cette page dans le réseau Wicri

	Serveur d'exploration sur l'Université de Trèves
	Attention, ce site est en cours de développement ! Attention, site généré par des moyens informatiques à partir de corpus bruts. Les informations ne sont donc pas validées.