The algebraic degree of geometric optimization problems (Q1104865): Difference between revisions

From MaRDI portal
Importer (talk | contribs)
Created a new Item
 
Added link to MaRDI item.
links / mardi / namelinks / mardi / name
 

Revision as of 01:50, 31 January 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

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references