The algebraic degree of geometric optimization problems (Q1104865): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set OpenAlex properties. |
||
(5 intermediate revisions by 4 users not shown) | |||
Property / author | |||
Property / author: Chanderjit L. Bajaj / rank | |||
Property / Wikidata QID | |||
Property / Wikidata QID: Q29307364 / rank | |||
Normal rank | |||
Property / author | |||
Property / author: Chanderjit L. Bajaj / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4050665 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The transitive groups of degree up to eleven<sup>+</sup> / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4126324 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5651303 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4155835 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3105730 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3935355 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5574527 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3902404 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Some Remarks on Computing Galois Groups / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5669010 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A Method to Compute Minimal Polynomials / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Polynomial Minimum Root Separation / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The Determination of Galois Groups / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5659661 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2071857538 / rank | |||
Normal rank |
Latest revision as of 11:16, 30 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The algebraic degree of geometric optimization problems |
scientific article |
Statements
The algebraic degree of geometric optimization problems (English)
0 references
1988
0 references
We apply Galois methods to certain fundamental geometric optimization problems whose exact computational complexity has been an open problem for a long time. In particular we show that the classic Weber problem, along with the line-restricted Weber problem and its three-dimensional version are in general not solvable by radicals over the field of rationals. One direct consequence of these results is that for these geometric optimization problems there exists no exact algorithm under models of computation where the root of an algebraic equation is obtained using arithmetic operations and the extraction of kth roots. This leaves only numerical or symbolic approximations to the solutions, where the complexity of the approximations is shown to be primarily a function of the algebraic degree of the optimum solution point.
0 references
algebraic degree
0 references
facility location
0 references
Galois methods
0 references
classic Weber problem
0 references
line-restricted Weber problem
0 references