Library

X
You have 0 saved results.
Mark results and click the "Add To Watchlist" link in order to add them to this list.
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 bounded approximation for the minimum cost 2-sat problem (1992)
    Springer
    Algorithmica 8 (1992), S. 103-117 
    Details
    ISSN: 1432-0541
    Keywords: Satisfiability ; Combinatorial optimization ; Stable roommates problem ; Approximation algorithm
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Given a satisfiable Boolean formula in 2-CNF, it is NP-hard to find a satisfying assignment that contains a minimum number of true variables. A polynomial-time approximation algorithm is given that finds an assignment with at most twice as many true variables as necessary. The algorithm also works for a weighted generalization of the problem. An application to the optimal stable roommates problem is given in detail, and other applications are mentioned.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01758838
    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...