Library

X
feed icon rss

Your email was sent successfully. Check your inbox.

An error occurred while sending the email. Please try again.

Proceed reservation?

Export
  • 1
    Electronic Resource
    Electronic Resource
    A PL homotopy for finding all the roots of a polynomial (1979)
    Springer
    Mathematical programming 16 (1979), S. 37-62 
    Details
    ISSN: 1436-4646
    Keywords: Roots of Polynomials ; Fixed Point Computing Methods ; Complementary Pivoting Methods ; Piecewise Linear Homotopy
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract This paper presents a constructive method which gives, for any polynomialF(Z) of the degreen, approximate values of all the roots ofF(Z).. The point of the method is on the use of a piecewise linear function $$\bar H$$ (Z, t) which approximates a homotopyH(Z, t) betweenF(Z) and a polynomialG(Z) of the degreen withn known simple roots. It is shown that the set of solutions to $$\bar H$$ (Z, t) = 0 includesn distinct paths,m of which converges to a root ofF(Z) if and only if the root has the multiplicitym. Starting from givenn roots ofG(Z), a complementary pivot algorithm generates thosen paths.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01582093
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    Electronic Resource
    Electronic Resource
    Computational complexity to verify the unstability of effectivity function (1993)
    Springer
    International journal of game theory 22 (1993), S. 225-239 
    Details
    ISSN: 1432-1270
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract Ann-person game is considered where each player has a preference order over a finite setA of possible alternatives and a rule for social choice is given in the form of an effectivity functionE. The effectivity function is called stable if for any combination of individual preference orders there exists a subset ofA called a core such that any alternative in the core cannot be ‘dominated’ by such individual preferences. It has been shown by Keiding (1985) that the effectivity functionE is stable if and only ifE does not generate any ‘Cycle’. This paper is concerned with the computational complexity of the problem (CYCLE) for determining whether or not a given effectivity function has a Cycle, We show that a familiar NPC problem SATISFIABILITY can be transformed into CYCLE through a polynomial time procedure. This, combined with the fact that CYCLE is an NP problem, implies NP-completeness of CYCLE, and therefore that of verifying the unstability of the effectivity function, thereby formally proving a previously unanswered conjecture.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01240054
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...