✦ LIBER ✦

NP-hardness of deciding convexity of quartic polynomials and related problems

✍ Scribed by Amir Ali Ahmadi, Alex Olshevsky, Pablo A. Parrilo, John N. Tsitsiklis

Book ID: 118791917
Publisher: Springer-Verlag
Year: 2011
Tongue: English
Weight: 274 KB
Volume: 137
Category: Article
ISSN: 0025-5610
DOI: 10.1007/s10107-011-0499-2

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

NP-hardness of linear multiplicative pro

NP-hardness of linear multiplicative programming and related problems

✍ T. Matsui 📂 Article 📅 1996 🏛 Springer US 🌐 English ⚖ 362 KB

Decidable, polynomial-time, and np-compl

Decidable, polynomial-time, and np-complete cases of the isotone bipartite graph problem

✍ V. G. Timkovskii; L. V. Knyazeva 📂 Article 📅 1991 🏛 Springer US 🌐 English ⚖ 844 KB

Polynomial Time Approximation Schemes fo

Polynomial Time Approximation Schemes for Dense Instances of NP-Hard Problems

✍ Sanjeev Arora; David Karger; Marek Karpinski 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 250 KB

We present a unified framework for designing polynomial time approximation schemes (PTASs) for ``dense'' instances of many NP-hard optimization problems, including maximum cut, graph bisection, graph separation, minimum k-way cut with and without specified terminals, and maximum 3-satisfiability. By

NP-Hardness of Some Linear Control Desig

NP-Hardness of Some Linear Control Design Problems

✍ Blondel, Vincent; Tsitsiklis, John N. 📂 Article 📅 1997 🏛 Society for Industrial and Applied Mathematics 🌐 English ⚖ 552 KB

On NP-hardness of the clique partition—I

On NP-hardness of the clique partition—Independence number gap recognition and related problems

✍ Stanislav Busygin; Dmitrii V. Pasechnik 📂 Article 📅 2006 🏛 Elsevier Science 🌐 English ⚖ 162 KB

On the NP-hardness of edge-deletion and

On the NP-hardness of edge-deletion and -contraction problems

✍ Toshimasa Watanabe; Tadashi Ae; Akira Nakamura 📂 Article 📅 1983 🏛 Elsevier Science 🌐 English ⚖ 1015 KB