Search results for "nonapproximability"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
54	Noriyuki Fujimoto, Kenichi Hagihara	On Approximation of the Bulk Synchronous Task Scheduling Problem.	IEEE Trans. Parallel Distributed Syst.	2003	DBLP DOI BibTeX RDF	software overhead, message packaging, bulk synchronous schedule, approximation, NP-complete, Task scheduling, distributed memory, fine grain, nonapproximability
54	Leonard Pitt, Manfred K. Warmuth	The Minimum Consistent DFA Problem Cannot be Approximated within any Polynomial.	J. ACM	1993	DBLP DOI BibTeX RDF	minimization of finite state machines, approximation algorithms, nonapproximability
51	Martin Thimm	On the Approximability of the Steiner Tree Problem.	MFCS	2001	DBLP DOI BibTeX RDF	Minimum Steiner tree, Gadget reduction, Lower bounds, Approximability
31	Haitao Jiang, Jingjing Ma, Junfeng Luan, Daming Zhu	Approximation and Nonapproximability for the One-Sided Scaffold Filling Problem.	COCOON	2015	DBLP DOI BibTeX RDF
31	Mikhail Alekhnovich, Sanjeev Arora, Iannis Tourlakis	Towards Strong Nonapproximability Results in the Lovász-Schrijver Hierarchy.	Comput. Complex.	2011	DBLP DOI BibTeX RDF
31	Sebastiaan A. Terwijn, Leen Torenvliet, Paul M. B. Vitányi	Nonapproximability of the normalized information distance.	J. Comput. Syst. Sci.	2011	DBLP DOI BibTeX RDF
31	Judy Goldsmith, Christopher Lusena, Martin Mundhenk	Nonapproximability Results for Partially Observable Markov Decision Processes	CoRR	2011	DBLP BibTeX RDF
31	Michael Alekhnovich, Sanjeev Arora, Iannis Tourlakis	Towards strong nonapproximability results in the Lovasz-Schrijver hierarchy.	STOC	2005	DBLP DOI BibTeX RDF	Lovász-Schrijver matrix cuts, inapproximability, integrality gaps
31	Lars Engebretsen	The Nonapproximability of Non-Boolean Predicates.	SIAM J. Discret. Math.	2004	DBLP DOI BibTeX RDF
31	Mikhail Alecknovich, Sanjeev Arora, Iannis Tourlakis	Towards strong nonapproximability results in the Lovasz-Schrijver hierarchy	Electron. Colloquium Comput. Complex.	2004	DBLP BibTeX RDF
31	Detlef Sieling	The Nonapproximability of OBDD Minimization.	Inf. Comput.	2002	DBLP DOI BibTeX RDF
31	Beate Bollig, Martin Sauerhoff, Ingo Wegener	On the Nonapproximability of Boolean Functions by OBDDs and Read-k-Times Branching Programs.	Inf. Comput.	2002	DBLP DOI BibTeX RDF
31	Christopher Lusena, Judy Goldsmith, Martin Mundhenk	Nonapproximability Results for Partially Observable Markov Decision Processes.	J. Artif. Intell. Res.	2001	DBLP DOI BibTeX RDF
31	Christopher Lusena, Judy Goldsmith, Martin Mundhenk	Nonapproximability Results for Partially Observable Markov Decision Processes	Universität Trier, Mathematik/Informatik, Forschungsbericht	2000	RDF
31	Oded Goldreich 0001, Shafi Goldwasser	On the Limits of Nonapproximability of Lattice Problems.	J. Comput. Syst. Sci.	2000	DBLP DOI BibTeX RDF
31	Beate Bollig, Ingo Wegener	Approximability and Nonapproximability by Binary Decision Diagrams	Electron. Colloquium Comput. Complex.	2000	DBLP BibTeX RDF
31	Hans Kellerer, Thomas Tautenhahn, Gerhard J. Woeginger	Approximability and Nonapproximability Results for Minimizing Total Flow Time on a Single Machine.	SIAM J. Comput.	1999	DBLP DOI BibTeX RDF
31	Peter Jonsson	Near-Optimal Nonapproximability Results for Some NPO PB-Complete Problems.	Inf. Process. Lett.	1998	DBLP DOI BibTeX RDF
31	Mihir Bellare, Oded Goldreich 0001, Madhu Sudan 0001	Free Bits, PCPs, and Nonapproximability-Towards Tight Results.	SIAM J. Comput.	1998	DBLP DOI BibTeX RDF
31	Peter Jonsson	A Nonapproximability Result for Finite Function Generation.	Inf. Process. Lett.	1997	DBLP DOI BibTeX RDF
31	Hans Kellerer, Thomas Tautenhahn, Gerhard J. Woeginger	Approximability and Nonapproximability Results for Minimizing Total Flow Time on a Single Machine.	STOC	1996	DBLP DOI BibTeX RDF	total flow time, scheduling, approximation algorithm, worst case analysis, release time, single machine
31	Anne Condon, Joan Feigenbaum, Carsten Lund, Peter W. Shor	Probabilistically Checkable Debate Systems and Nonapproximability of PSPACE-Hard Functions.	Chic. J. Theor. Comput. Sci.	1995	DBLP BibTeX RDF
28	Detlef Sieling	Minimization Problems for Parity OBDDs.	Theory Comput. Syst.	2009	DBLP DOI BibTeX RDF	Parity OBDD, Nonapproximability
28	Rodolphe Giroudeau, Jean-Claude König	General Non-Approximability Results in Presence of Hierarchical Communications.	ISPDC/HeteroPar	2004	DBLP DOI BibTeX RDF	hierarchical communications, scheduling, nonapproximability
28	Mihir Bellare, Oded Goldreich 0001, Madhu Sudan 0001	Free Bits, PCPs and Non-Approximability - Towards Tight Results.	FOCS	1995	DBLP DOI BibTeX RDF	free bits, logarithmic randomness, amortized free bits, Max Clique, Max-2-SAT, FGLSS connection, amortized free-bit complexity, amortized free bit complexity, FPCP parameters, triviality results, computational complexity, computational geometry, theorem proving, NP-hardness, NP complete problems, proof systems, chromatic number, PCPs, Max-cut, nonapproximability
25	Marek Karpinski	Approximating Bounded Degree Instances of NP-Hard Problems.	FCT	2001	DBLP DOI BibTeX RDF
25	Noga Alon, Richard Beigel	Lower Bounds for Approximations by Low Degree Polynomials Over Zm.	CCC	2001	DBLP DOI BibTeX RDF