Tag #np-hard
20 papers:
ICML-2017-ChenGWWYY #optimisation- Strong NP-Hardness for Sparse Optimization with Concave Penalty Functions (YC, DG, MW, ZW, YY, HY), pp. 740–747.
ICPR-2016-WeissenbergRDG #optimisation #problem- Dilemma First Search for effortless optimization of NP-hard problems (JW, HR, RD, LVG), pp. 4154–4159.
ICALP-v1-2015-KariKMPS #set #synthesis- Binary Pattern Tile Set Synthesis Is NP-hard (LK, SK, PÉM, MJP, SS), pp. 1022–1034.
STOC-2012-ODonnellW #game studies- A new point of NP-hardness for unique games (RO, JW), pp. 289–306.
- STOC-2011-KhotM #approximate #equation #linear
- NP-hardness of approximately solving linear equations over reals (SK, DM), pp. 413–420.
- STOC-2010-AkaviaGGM
- Erratum for: on basing one-way functions on NP-hardness (AA, OG, SG, DM), pp. 795–796.
LATA-2009-GlasserPT #fault tolerance #problem- The Fault Tolerance of NP-Hard Problems (CG, AP, SDT), pp. 374–385.
- LATA-2008-Perekrestenko #bound
- Minimalist Grammars with Unbounded Scrambling and Nondiscriminating Barriers Are NP-Hard (AP), pp. 421–432.
SAT-2008-KottlerKS08a #bound #satisfiability #subclass #using- A New Bound for an NP-Hard Subclass of 3-SAT Using Backdoors (SK, MK, CS), pp. 161–167.
PODS-2007-GottlobMS - Generalized hypertree decompositions: np-hardness and tractable variants (GG, ZM, TS), pp. 13–22.
- ICALP-2007-GuoN #graph #kernel #linear #problem
- Linear Problem Kernels for NP-Hard Problems on Planar Graphs (JG, RN), pp. 375–386.
- STOC-2006-AkaviaGGM #on the
- On basing one-way functions on NP-hardness (AA, OG, SG, DM), pp. 701–710.
- STOC-2006-FellowsRRS #clique
- Clique-width minimization is NP-hard (MRF, FAR, UR, SS), pp. 354–362.
SAC-2005-KoshelevaKMN #matrix- Computing the cube of an interval matrix is NP-Hard (OK, VK, GM, HTN), pp. 1449–1453.
- STOC-2001-HaleviKKN #approximate
- Private approximation of NP-hard functions (SH, RK, EK, KN), pp. 550–559.
- ICALP-2000-Hastad #algorithm #approximate #optimisation #performance #problem #question
- Which NP-Hard Optimization Problems Admit Non-trivial Efficient Approximation Algorithms? (JH), p. 235.
- STOC-1998-Ajtai #problem #random #reduction
- The Shortest Vector Problem in L2 is NP-hard for Randomized Reductions (MA), pp. 10–19.
- STOC-1998-Arora #problem
- The Approximability of NP-hard Problems (SA), pp. 337–348.
- SAC-1996-GowerW #problem
- R-by-C Crozzle: an NP-hard problem (MG, RWW), pp. 73–76.
- STOC-1995-AroraKK #approximate #polynomial #problem
- Polynomial time approximation schemes for dense instances of NP-hard problems (SA, DRK, MK), pp. 284–293.
