Search results for "NP-hard"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
3	Peter Eades, Sue Whitesides	The Realization Problem for Euclidean Minimum Spanning Trees is NP-hard.	Symposium on Computational Geometry	1994	DBLP DOI BibTeX RDF	tree, NP-hard, spanning tree, graph drawing, graph layout
3	H. C. Du	Distributing a database for Parallel Processing is NP-hard.	SIGMOD Record	1984	DBLP DOI BibTeX RDF	parallel Processing, database, NP-hard
2	Sergio Cabello, Bojan Mohar	Adding one edge to planar graphs makes crossing number hard.	Symposium on Computational Geometry	2010	DBLP DOI BibTeX RDF	NP-hard, graph drawing, planar graphs, graph embedding, crossing number, topological graph theory
2	Rodica Mihai, Ioan Todinca	Pathwidth is NP-Hard for Weighted Trees.	FAW	2009	DBLP DOI BibTeX RDF
2	Christoph Dürr, Flavio Guiñez, Martín Matamala	Reconstructing 3-Colored Grids from Horizontal and Vertical Projections Is NP-hard.	ESA	2009	DBLP DOI BibTeX RDF
2	Andrea Francke, Michael Hoffmann	The Euclidean degree-4 minimum spanning tree problem is NP-hard.	Symposium on Computational Geometry	2009	DBLP DOI BibTeX RDF	degree-constricted graphs, degree-restricted graphs, np-complete, reduction, spanning trees, geometric optimization, geometric graphs, bounded-degree graphs
2	Meena Mahajan, Prajakta Nimbhorkar, Kasturi R. Varadarajan	The Planar k-Means Problem is NP-Hard.	WALCOM	2009	DBLP DOI BibTeX RDF
2	Karl Bringmann, Tobias Friedrich	Approximating the Least Hypervolume Contributor: NP-Hard in General, But Fast in Practice.	EMO	2009	DBLP DOI BibTeX RDF
2	Jiong Guo, Hannes Moser, Rolf Niedermeier	Iterative Compression for Exactly Solving NP-Hard Minimization Problems.	Algorithmics of Large and Complex Networks	2009	DBLP DOI BibTeX RDF
2	Vlado Keselj, Haibin Liu, Norbert Zeh, Christian Blouin, Chris Whidden	Finding optimal parameters for edit distance based sequence classification is NP-hard.	KDD Workshop on Statistical and Relational Learning in Bioinformatics	2009	DBLP DOI BibTeX RDF
2	Nadja Betzler, Michael R. Fellows, Jiong Guo, Rolf Niedermeier, Frances A. Rosamond	How similarity helps to efficiently compute Kemeny rankings.	AAMAS	2009	DBLP DOI BibTeX RDF	structural parameterization, exact algorithm, NP-hard problem, fixed-parameter tractability, rank aggregation
2	Guojun Li, Xiaotie Deng, Ying Xu	A polynomial-time approximation scheme for embedding hypergraph in a cycle.	ACM Transactions on Algorithms	2009	DBLP DOI BibTeX RDF	Hypergraph embedding, minimum congestion, NP-hard, polynomial-time approximation scheme
2	MingJian Tang, Jinli Cao, Xiaohua Jia, Ke-Yan Liu	Optimization on Data Object Compression and Replication in Wireless Multimedia Sensor Networks.	DASFAA	2009	DBLP DOI BibTeX RDF	Data compression and replication, subgradient method, Optimization, NP-hard, Lagrangian relaxation, Wireless Multimedia Sensor Networks
2	Franz-Josef Brandenburg, Mao-cheng Cai	Shortest Path and Maximum Flow Problems in Networks with Additive Losses and Gains.	FAW	2009	DBLP DOI BibTeX RDF	extended networks, lossy and gainy arcs, max-flow, unit-loss networks, shortest path, NP-hard
2	Fedor V. Fomin, Serge Gaspers, Saket Saurabh, Alexey A. Stepanov	On Two Techniques of Combining Branching and Treewidth.	Algorithmica	2009	DBLP DOI BibTeX RDF	Exact exponential time algorithms, #3-Coloring, #Minimum dominating set, Minimum maximal matching, k-Weighted vertex cover, NP hard problems, Treewidth, Parameterized algorithms
2	Wenqi Huang, Kun He	A pure quasi-human algorithm for solving the cuboid packing problem.	Science in China Series F: Information Sciences	2009	DBLP DOI BibTeX RDF	quasi-human approach, caving degree, heuristic, NP-hard, packing problem
2	David Eppstein, Michael T. Goodrich, Ethan Kim, Rasmus Tamstorf	Approximate topological matching of quad meshes.	The Visual Computer	2009	DBLP DOI BibTeX RDF	Topological matching, Lazy-greedy heuristic, NP-complete, NP-hard, Isomorphism, Quad mesh
2	Wolfgang Mulzer, Günter Rote	Minimum-weight triangulation is NP-hard.	J. ACM	2008	DBLP DOI BibTeX RDF	Optimal triangulations, PLANAR 1-IN-3-SAT
2	Parthasarathy Guturu, Ram Dantu	An Impatient Evolutionary Algorithm With Probabilistic Tabu Search for Unified Solution of Some NP-Hard Problems in Graph and Set Theory via Clique Finding.	IEEE Transactions on Systems, Man, and Cybernetics, Part B	2008	DBLP DOI BibTeX RDF
2	Deniss Kumlander	NP-Hard Graph Problems' Algorithms Testing Guidelines: Artificial Intelligence Principles and Testing as a Service.	Innovative Techniques in Instruction Technology, E-learning, E-assessment, and Education	2008	DBLP DOI BibTeX RDF
2	Alexander Perekrestenko	Minimalist Grammars with Unbounded Scrambling and Nondiscriminating Barriers Are NP-Hard.	LATA	2008	DBLP DOI BibTeX RDF
2	Oriana Ponta, Falk Hüffner, Rolf Niedermeier	Speeding up Dynamic Programming for Some NP-Hard Graph Recoloring Problems.	TAMC	2008	DBLP DOI BibTeX RDF
2	Marc Demange, Tinaz Ekim	Minimum Maximal Matching Is NP-Hard in Regular Bipartite Graphs.	TAMC	2008	DBLP DOI BibTeX RDF	unmatched pairs, Minimum Maximal Matching, regular bipartite graphs, stable marriage
2	Stephan Kottler, Michael Kaufmann, Carsten Sinz	A New Bound for an NP-Hard Subclass of 3-SAT Using Backdoors.	SAT	2008	DBLP DOI BibTeX RDF
2	Bin Chen, Guangri Quan	NP-Hard Problems of Learning from Examples.	FSKD	2008	DBLP DOI BibTeX RDF
2	Philippe Galinier, Alain Hertz, Sandrine Paroz, Gilles Pesant	Using Local Search to Speed Up Filtering Algorithms for Some NP-Hard Constraints.	CPAIOR	2008	DBLP DOI BibTeX RDF
2	Harry Buhrman, John M. Hitchcock	NP-Hard Sets Are Exponentially Dense Unless coNP C NP/poly.	IEEE Conference on Computational Complexity	2008	DBLP DOI BibTeX RDF	hard sets, polynomial advice, instance complexity
2	Xin Chen, Lan Liu, Zheng Liu, Tao Jiang	On the minimum common integer partition problem.	ACM Transactions on Algorithms	2008	DBLP DOI BibTeX RDF	approximation algorithm, combinatorial optimization, NP-hard, computational biology, Subset sum, integer partition
2	Danyu Bai, Lixin Tang, Meng Su	A New Machine Scheduling Problem with Temperature Loss.	WKDD	2008	DBLP DOI BibTeX RDF	Temperature Drop Curve, Total Temperature Drop Loss, Scheduling, NP-hard
2	Hitoshi Kanoh, Souichi Tsukahara	Virus Evolution Strategy for Vehicle Routing Problems with Time Windows.	PPSN	2008	DBLP DOI BibTeX RDF	NP-hard class, evolution strategy, schema, Vehicle routing problem, virus, infection
2	Ning Chen, Atri Rudra	Walrasian Equilibrium: Hardness, Approximations and Tractable Instances.	Algorithmica	2008	DBLP DOI BibTeX RDF	Walrasian equilibrium, Single-minded auction, Approximation, NP-hard, Combinatorial auction
2	Joseph Y.-T. Leung, Haibing Li, Michael Pinedo	Scheduling orders on either dedicated or flexible machines in parallel to minimize total weighted completion time.	Annals OR	2008	DBLP DOI BibTeX RDF	Order scheduling, Total weighted completion time, Approximation algorithms, NP-hard
2	Joseph Y.-T. Leung, Hairong Zhao	Scheduling problems in master-slave model.	Annals OR	2008	DBLP DOI BibTeX RDF	Master slave model, Approximation algorithms, NP-hard, Makespan, Total completion time
2	He Jiang, Xianchao Zhang, Guoliang Chen, MingChu Li	Backbone analysis and algorithm design for the quadratic assignment problem.	Science in China Series F: Information Sciences	2008	DBLP DOI BibTeX RDF	backbone analysis, biased instance, NP-hard, meta-heuristic, quadratic assignment problem
2	Robert W. Irving, David Manlove	Approximation algorithms for hard variants of the stable marriage and hospitals/residents problems.	J. Comb. Optim.	2008	DBLP DOI BibTeX RDF	Weak stability, Approximation algorithms, NP-hard problems, Stable matching
2	Jiong Guo, Rolf Niedermeier	Linear Problem Kernels for NP-Hard Problems on Planar Graphs.	ICALP	2007	DBLP DOI BibTeX RDF
2	David Nistér, Fredrik Kahl, Henrik Stewénius	Structure from Motion with Missing Data is NP-Hard.	ICCV	2007	DBLP DOI BibTeX RDF
2	Navin Kashyap	The "Art of Trellis Decoding" Is NP-Hard.	AAECC	2007	DBLP DOI BibTeX RDF
2	Pi-Rong Sheu, Shan-Tai Chen	On the Hardness of Approximating the Multicast Delay Variation Problem.	IEEE Trans. Computers	2007	DBLP DOI BibTeX RDF	inter-destination delay variation, NP-complete, NP-hard, multicast routing, Inapproximability
2	Deying Li, Jiannong Cao, Ming Liu, Yuan Zheng	K -Connected Target Coverage Problem in Wireless Sensor Networks.	COCOA	2007	DBLP DOI BibTeX RDF	k-connected target coverage, k-connected augmentation, wireless sensor networks, heuristic algorithms, NP-hard problems
2	Frank Kammer	Determining the Smallest k Such That G Is k -Outerplanar.	ESA	2007	DBLP DOI BibTeX RDF	Outerplanarity index, k-outerplanar, SPQR trees, NP-hard, fixed-parameter algorithms
2	Chuan-Ming Liu, Kun-Feng Lin	Disseminating dependent data in wireless broadcast environments.	Distributed and Parallel Databases	2007	DBLP DOI BibTeX RDF	Latency, NP-hard, Directed acyclic graphs, Data broadcasting, Access pattern
2	R. Kapoor, S. R. Arora	Complexity of a particular class of single and multiple ratio quadratic 0-1 fractional programming problems.	Operational Research	2007	DBLP DOI BibTeX RDF	0-1 Quadratic Fractional Programming, Global Verification, 90C32, Complexity, Local Search, NP-hard, 90C10, 90C60, 90C20
2	Vladik Kreinovich, Max Shpak	Aggregability is NP-hard.	SIGACT News	2006	DBLP DOI BibTeX RDF
2	Frank Neumann, Marco Laumanns	Speeding up Approximation Algorithms for NP-Hard Spanning Forest Problems by Multi-objective Optimization.	LATIN	2006	DBLP DOI BibTeX RDF
2	Wolfgang Mulzer, Günter Rote	Minimum weight triangulation is NP-hard.	Symposium on Computational Geometry	2006	DBLP DOI BibTeX RDF	PLANAR-1-IN-3-SAT, optimal triangulations
2	Isabelle Sivignon, David Coeurjolly	Minimal Decomposition of a Digital Surface into Digital Plane Segments Is NP-Hard.	DGCI	2006	DBLP DOI BibTeX RDF
2	Vladimir G. Deineko, Alexandre Tiskin	One-Sided Monge TSP Is NP-Hard.	ICCSA	2006	DBLP DOI BibTeX RDF
2	Rolf Klein, Martin Kutz	Computing Geometric Minimum-Dilation Graphs Is NP-Hard.	Graph Drawing	2006	DBLP DOI BibTeX RDF	spanning ratio, NP-hardness, dilation, stretch factor, plane graph, geometric network
2	Michael R. Fellows, Frances A. Rosamond, Udi Rotics, Stefan Szeider	Clique-width minimization is NP-hard.	STOC	2006	DBLP DOI BibTeX RDF	absolute approximation, NP-completeness, clique-width, pathwidth
2	Xiaotie Deng, Qizhi Fang, Xiaoxun Sun	Finding nucleolus of flow game.	SODA	2006	DBLP DOI BibTeX RDF	LP duality, flow game, nucleolus, NP-hard, efficient algorithm
2	Fedor V. Fomin, Fabrizio Grandoni, Dieter Kratsch	Measure and conquer: a simple O(20.288n) independent set algorithm.	SODA	2006	DBLP DOI BibTeX RDF	exponential-time exact algorithms, independent set problem, NP-hard problems, algorithms and data structures
2	David Zuckerman	Linear degree extractors and the inapproximability of max clique and chromatic number.	STOC	2006	DBLP DOI BibTeX RDF	approximation, NP-hard, clique, extractor, pseudorandom, disperser, chromatic number, explicit construction
2	Martin Fürer	A Faster Algorithm for Finding Maximum Independent Sets in Sparse Graphs.	LATIN	2006	DBLP DOI BibTeX RDF	exponential time algorithm, NP-hard, Maximum independent set, sparse graph
2	Juan Frausto Solís, Héctor Sanvicente Sánchez, Froilán Imperial-Valenzuela	ANDYMARK: An Analytical Method to Establish Dynamically the Length of the Markov Chain in Simulated Annealing for the Satisfiability Problem.	SEAL	2006	DBLP DOI BibTeX RDF	Optimization, Heuristics, Simulated Annealing, Combinatorial Optimization, Satisfiability, NP-Hard Problems
2	Chor Ping Low	On Load-Balanced Semi-matchings for Weighted Bipartite Graphs.	TAMC	2006	DBLP DOI BibTeX RDF	semi-matching, approximation algorithm, load balancing, NP-hard, bipartite graphs
2	Christian Bessière, Emmanuel Hebrard, Brahim Hnich, Zeynep Kiziltan, Toby Walsh	Filtering Algorithms for the NValueConstraint.	Constraints	2006	DBLP DOI BibTeX RDF	NValue constraint, AtleastNValue, AtMostNValue, NP-hard, pruning, global constraints, linear relaxation
2	Binwu Zhang, Jianzhong Zhang 0001, Liqun Qi	The shortest path improvement problems under Hamming distance.	J. Comb. Optim.	2006	DBLP DOI BibTeX RDF	NP-hard, Hamming distance, Shortest path problem
2	Venkatesan Guruswami, Alexander Vardy	Maximum-likelihood decoding of Reed-Solomon codes is NP-hard.	IEEE Transactions on Information Theory	2005	DBLP DOI BibTeX RDF
2	Uriel Feige	Rigorous analysis of heuristics for NP-hard problems.	SODA	2005	DBLP BibTeX RDF
2	Venkatesan Guruswami, Alexander Vardy	Maximum-likelihood decoding of Reed-Solomon codes is NP-hard.	SODA	2005	DBLP BibTeX RDF
2	Olga Kosheleva, Vladik Kreinovich, Günter Mayer, Hung T. Nguyen	Computing the cube of an interval matrix is NP-Hard.	SAC	2005	DBLP DOI BibTeX RDF
2	Marcello Dalpasso, Giuseppe Lancia, Romeo Rizzi	The String Barcoding Problem is NP-Hard.	Comparative Genomics	2005	DBLP DOI BibTeX RDF
2	Mustafa Tacettin, Tonguç Ünlüyurt	An Alternative Proof That Exact Inference Problem in Bayesian Belief Networks Is NP-Hard.	ISCIS	2005	DBLP DOI BibTeX RDF
2	Jesús Fabián López Pérez	A Meta-heuristic Applied for a Topologic Pickup and Delivery Problem with Time Windows Constraints.	International Conference on Computational Science	2005	DBLP DOI BibTeX RDF	Genetic Algorithms, NP-Hard, Logistics, Time Windows
2	Tsan-sheng Hsu, Kuo-Hui Tsai, Da-Wei Wang, D. T. Lee	Two Variations of the Minimum Steiner Problem.	J. Comb. Optim.	2005	DBLP DOI BibTeX RDF	minimum Steiner network, minimum union paths, NP-hard, directed acyclic graph, polynomial time
2	Ya-feng Wu, Yinlong Xu, Guo-Liang Chen	Approximation Algorithms for Steiner Connected Dominating Set.	J. Comput. Sci. Technol.	2005	DBLP DOI BibTeX RDF	Steiner connected dominated set, approximation algorithm, graph algorithm, NP-hard
2	Amin Coja-Oghlan, Sven Oliver Krumke, Till Nierhoff	A Hard Dial-a-Ride Problem that is Easy on Average.	J. Scheduling	2005	DBLP DOI BibTeX RDF	approximation algorithm, NP-hard, average-case analysis
2	Joseph Y.-T. Leung, Haibing Li, Michael Pinedo	Order Scheduling in an Environment with Dedicated Resources in Parallel.	J. Scheduling	2005	DBLP DOI BibTeX RDF	order scheduling, approximation, NP-hard, Tabu Search, total completion time
2	Mark Brehob, Stephen Wagner, Eric Torng, Richard J. Enbody	Optimal Replacement Is NP-Hard for Nonstandard Caches.	IEEE Trans. Computers	2004	DBLP DOI BibTeX RDF	optimal cache replacement policy, interval scheduling, skew cache, multilateral cache, approximation algorithm, Cache, victim cache
2	Wenci Yu, Han Hoogeveen, Jan Karel Lenstra	Minimizing Makespan in a Two-Machine Flow Shop with Delays and Unit-Time Operations is NP-Hard.	J. Scheduling	2004	DBLP DOI BibTeX RDF	intermediate delays, strong NP-hardness, computational complexity, makespan, flow shop scheduling
2	Per Olov Lindberg, Gholamreza Razmara	The Prize Collecting Connected Subgraph Problem - A New NP-Hard Problem arising in Snow Removal Routing.	OR	2004	DBLP DOI BibTeX RDF
2	Jianer Chen, Benny Chor, Mike Fellows, Xiuzhen Huang, David W. Juedes, Iyad A. Kanj, Ge Xia	Tight Lower Bounds for Certain Parameterized NP-Hard Problems.	IEEE Conference on Computational Complexity	2004	DBLP DOI BibTeX RDF
2	Jianer Chen, Xiuzhen Huang, Iyad A. Kanj, Ge Xia	Linear FPT reductions and computational lower bounds.	STOC	2004	DBLP DOI BibTeX RDF	lower bound, complexity theory, NP-hard problems
2	Jens Gramm, Jiong Guo, Falk Hüffner, Rolf Niedermeier	Automated Generation of Search Tree Algorithms for Hard Graph Modification Problems.	Algorithmica	2004	DBLP DOI BibTeX RDF	Graph modification, Search tree algorithms, Automated development and analysis of algorithms, Exact algorithms, NP-hard problems, Algorithm engineering
2	Aharon Ben-Tal, A. Goryashko, E. Guslitzer, Arkadi Nemirovski	Adjustable robust solutions of uncertain linear programs.	Math. Program.	2004	DBLP DOI BibTeX RDF	Uncertain linear programs, conic optimization, NP-hard continuous optimization problems, adjustable robust counterpart, affinely-adjustable robust counterpart, semidefinite programming, robust optimization
2	Manuel Gómez, Concha Bielza	Node deletion sequences in influence diagrams using genetic algorithms.	Statistics and Computing	2004	DBLP DOI BibTeX RDF	node deletion sequence, genetic algorithms, statistical analysis, NP-hard problems, influence diagrams, decision-making under uncertainty
2	Irit Dinur, Guy Kindler, Ran Raz, Shmuel Safra	Approximating CVP to Within Almost-Polynomial Factors is NP-Hard.	Combinatorica	2003	DBLP DOI BibTeX RDF	AMS Subject Classification (2000): 68Q17
2	Ivan Kovtun	Partial Optimal Labeling Search for a NP-Hard Subclass of (max, +) Problems.	DAGM-Symposium	2003	DBLP DOI BibTeX RDF
2	Mark Cieliebak, Stephan Eidenbenz, Paolo Penna	Noisy Data Make the Partial Digest Problem NP-hard.	WABI	2003	DBLP DOI BibTeX RDF
2	Liara Aparecida dos Santos Leal, Dalcidio Moraes Claudio, Laira Vieira Toscani, Paulo Blauth Menezes	A Categorical Approach to NP-Hard Optimization Problems.	EUROCAST	2003	DBLP DOI BibTeX RDF
2	Miroslav Chlebík, Janka Chlebíková	Approximation Hardness for Small Occurrence Instances of NP-Hard Problems.	CIAC	2003	DBLP DOI BibTeX RDF
2	Joseph Douglas Horton, Alejandro López-Ortiz	On the number of distributed measurement points for network tomography.	Internet Measurement Comference	2003	DBLP DOI BibTeX RDF	internet tomography, resilient overlay networks, approximation algorithms, NP-hard, network measurements, topology discovery
2	Vladik Kreinovich	Range Estimation Is NP-Hard for ?2 Accuracy and Feasible for epsilon2-[delta].	Reliable Computing	2002	DBLP DOI BibTeX RDF
2	René Sitters	The Minimum Latency Problem Is NP-Hard for Weighted Trees.	IPCO	2002	DBLP BibTeX RDF
2	Christophe Costa Florêncio	Consistent Identification in the Limit of Rigid Grammars from Strings Is NP-hard.	ICGI	2002	DBLP DOI BibTeX RDF
2	Tetsuo Asano, David G. Kirkpatrick, Chee-Keng Yap	Pseudo approximation algorithms, with applications to optimal motion planning.	Symposium on Computational Geometry	2002	DBLP DOI BibTeX RDF	d 1-optimal motion, optimal motion planning, pseudo approximation, approximation algorithms, NP-hard problem, binary search, robot motion planning, Euclidean shortest path
2	Alexander E. Mohr	Bit Allocation in Sub-linear Time and the Multiple-Choice Knapsack Problem.	DCC	2002	DBLP DOI BibTeX RDF	multiple choice knapsack problem, MCKP, data compression, NP-complete, NP-hard, quantization, knapsack problem, bit allocation, rate-distortion optimization
2	Marek Karpinski	Polynomial Time Approximation Schemes for Some Dense Instances of NP-Hard Optimization Problems.	Algorithmica	2001	DBLP DOI BibTeX RDF
2	Christophe Costa Florêncio	Consistent Identification in the Limit of Any of the Classes k -Valued Is NP-hard.	LACL	2001	DBLP DOI BibTeX RDF	Learning theory, Grammatical inference, Categorial grammars, Formal language theory
2	Wolfgang Espelage, Frank Gurski, Egon Wanke	How to Solve NP-hard Graph Problems on Clique-Width Bounded Graphs in Polynomial Time.	WG	2001	DBLP DOI BibTeX RDF
2	Xavier Muñoz, Walter Unger, Imrich Vrto	One Sided Crossing Minimization Is NP-Hard for Sparse Graphs.	Graph Drawing	2001	DBLP DOI BibTeX RDF
2	Sanjeev Arora	Approximation Schemes for Geometric NP-Hard Problems: A Survey.	FSTTCS	2001	DBLP DOI BibTeX RDF
2	Shai Halevi, Robert Krauthgamer, Eyal Kushilevitz, Kobbi Nissim	Private approximation of NP-hard functions.	STOC	2001	DBLP DOI BibTeX RDF
2	Jaejin Lee, David A. Padua	Hiding Relaxed Memory Consistency with a Compiler.	IEEE Trans. Computers	2001	DBLP DOI BibTeX RDF	relaxed memory consistency, fence, compiler, synchronization, NP-hard, dominator, Sequential consistency
2	Jan Poland, Kosmas Knödler, Alexander Mitterer, Thomas Fleischhauer, Frank Zuber-Goos, Andreas Zell	Evolutionary Search for Smooth Maps in Motor Control Unit Calibration.	SAGA	2001	DBLP DOI BibTeX RDF	Control Unit Calibration, Variable Alphabet Coding, Hybrid GA, Smooth Maps, Genetic Algorithm, Combinatorial Optimization, NP-hard
2	Nicolas J. Cerf, Lov K. Grover, Colin P. Williams	Nested Quantum Search and NP-Hard Problems.	Appl. Algebra Eng. Commun. Comput.	2000	DBLP DOI BibTeX RDF	Combinatorial search problems, Quantum computation, NP-hard problems, Quantum algorithms
2	Johan Håstad	Which NP-Hard Optimization Problems Admit Non-trivial Efficient Approximation Algorithms?	ICALP	2000	DBLP DOI BibTeX RDF
2	Jean-Cédric Chappelier, Martin Rajman	Monte-Carlo Sampling for NP-Hard Maximization Problems in the Framework of Weighted Parsing.	Natural Language Processing	2000	DBLP DOI BibTeX RDF
2	Irit Dinur	Approximating SVPinfty to within Almost-Polynomial Factors Is NP-Hard.	CIAC	2000	DBLP DOI BibTeX RDF