Search results for "Non-approximability"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
69	Stefan Hougardy	Proof Checking and Non-approximability.	Lectures on Proof Verification and Approximation Algorithms	1997	DBLP DOI BibTeX RDF
55	Eric Angel, Evripidis Bampis, Laurent Gourvès, Jérôme Monnot	(Non)-Approximability for the Multi-criteria TSP(1, 2).	FCT	2005	DBLP DOI BibTeX RDF
49	Matthias Müller-Hannemann, Alexander Sonnikow	Non-approximability of just-in-time scheduling.	J. Sched.	2009	DBLP DOI BibTeX RDF	Earliness, Non-approximability, Special cases, Single machine scheduling, Just-in-time, Tardiness
49	Noriyuki Fujimoto	On Non-Approximability of Coarse-Grained Workflow Grid Scheduling.	ISPAN	2008	DBLP DOI BibTeX RDF	non-approximability, scheduling, grid computing, workflow
44	Beate Bollig, Martin Sauerhoff, Ingo Wegener	On the Non-Approximability of Boolean Functions by OBDDs and Read-K-Times Branching Programs.	CCC	2001	DBLP DOI BibTeX RDF	Computational complexity, lower bounds, approximations, binary decision diagrams, branching programs
37	Maria J. Serna, Luca Trevisan, Fatos Xhafa	The (Parallel) Approximability of Non-Boolean Satisfiability Problems and Restricted Integer Programming.	STACS	1998	DBLP DOI BibTeX RDF
35	Davide Bilò, Luciano Gualà, Guido Proietti	Improved approximability and non-approximability results for graph diameter decreasing problems.	Theor. Comput. Sci.	2012	DBLP DOI BibTeX RDF
35	Davide Bilò, Luciano Gualà, Guido Proietti	Improved Approximability and Non-approximability Results for Graph Diameter Decreasing Problems.	MFCS	2010	DBLP DOI BibTeX RDF
35	Alberto Bertoni, Roberto Radicioni	Approximability and Non-approximability Results in Computing the Mean Speedup of Trace Monoids.	Developments in Language Theory	2007	DBLP DOI BibTeX RDF
35	Christian Glaßer, Christian Reitwießner, Heinz Schmitz	Multiobjective Disk Cover Admits a PTAS.	ISAAC	2008	DBLP DOI BibTeX RDF
32	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
32	Luca Trevisan	Non-approximability results for optimization problems on bounded degree instances.	STOC	2001	DBLP DOI BibTeX RDF
32	Han Hoogeveen, Petra Schuurman, Gerhard J. Woeginger	Non-approximability Results for Scheduling Problems with Minsum Criteria.	IPCO	1998	DBLP DOI BibTeX RDF
32	Martin Mundhenk, Anna Slobodová	Optimal Non-approximability of MAXCLIQUE.	Lectures on Proof Verification and Approximation Algorithms	1997	DBLP DOI BibTeX RDF
30	Daniele Micciancio	The Shortest Vector in a Lattice is Hard to Approximate to Within Some Constant.	FOCS	1998	DBLP DOI BibTeX RDF	non-approximability, Sauer's lemma, lattices, shortest vector problem
23	Holger Boche, Rafael F. Schaefer, H. Vincent Poor	Shannon meets Turing: Non-computability and non-approximability of the finite state channel capacity.	Commun. Inf. Syst.	2020	DBLP DOI BibTeX RDF
23	Holger Boche, Rafael F. Schaefer, H. Vincent Poor	Shannon Meets Turing: Non-Computability and Non-Approximability of the Finite State Channel Capacity.	CoRR	2020	DBLP BibTeX RDF
23	Lars Engebretsen	The Non-approximability of Non-Boolean Predicates.	RANDOM-APPROX	2001	DBLP DOI BibTeX RDF
19	Zdenek Dvorák 0001, Ken-ichi Kawarabayashi	Additive non-approximability of chromatic number in proper minor-closed classes.	J. Comb. Theory, Ser. B	2023	DBLP DOI BibTeX RDF
19	Marcelo Arenas, Pablo Barceló, Leopoldo E. Bertossi, Mikaël Monet	On the Complexity of SHAP-Score-Based Explanations: Tractability via Knowledge Compilation and Non-Approximability Results.	J. Mach. Learn. Res.	2023	DBLP BibTeX RDF
19	Thomas Chen, Patricia Muñoz Ewald	Non-approximability of constructive global L2 minimizers by gradient descent in Deep Learning.	CoRR	2023	DBLP DOI BibTeX RDF
19	Marcelo Arenas, Pablo Barceló, Leopoldo E. Bertossi, Mikaël Monet	On the Complexity of SHAP-Score-Based Explanations: Tractability via Knowledge Compilation and Non-Approximability Results.	CoRR	2021	DBLP BibTeX RDF
19	Erwin Pesch, Katarzyna Anna Kuzmicz	Non-approximability of the single crane container transhipment problem.	Int. J. Prod. Res.	2020	DBLP DOI BibTeX RDF
19	Zdenek Dvorák 0001, Ken-ichi Kawarabayashi	Additive Non-Approximability of Chromatic Number in Proper Minor-Closed Classes.	ICALP	2018	DBLP DOI BibTeX RDF
19	Zdenek Dvorák 0001, Ken-ichi Kawarabayashi	Additive non-approximability of chromatic number in proper minor-closed classes.	CoRR	2017	DBLP BibTeX RDF
19	Mordecai J. Golin, Hadi Khodabande, Bo Qin	Non-approximability and Polylogarithmic Approximations of the Single-Sink Unsplittable and Confluent Dynamic Flow Problems.	CoRR	2017	DBLP BibTeX RDF
19	Mordecai J. Golin, Hadi Khodabande, Bo Qin	Non-approximability and Polylogarithmic Approximations of the Single-Sink Unsplittable and Confluent Dynamic Flow Problems.	ISAAC	2017	DBLP DOI BibTeX RDF
19	Xi Chen 0001, Xiaotie Deng	Non-approximability of Bimatrix Nash Equilibria.	Encyclopedia of Algorithms	2016	DBLP DOI BibTeX RDF
19	Frank Gurski, Magnus Roos	Binary linear programming solutions and non-approximability for control problems in voting systems.	Discret. Appl. Math.	2014	DBLP DOI BibTeX RDF
19	Marcel R. Ackermann, Johannes Blömer, Christoph Scholz 0001	Hardness and Non-Approximability of Bregman Clustering Problems.	Electron. Colloquium Comput. Complex.	2011	DBLP BibTeX RDF
19	Xi Chen 0001, Xiaotie Deng	Non-approximability of Bimatrix Nash Equilibria.	Encyclopedia of Algorithms	2008	DBLP DOI BibTeX RDF
19	Rodolphe Giroudeau, Jean-Claude König	General scheduling non-approximability results in presence of hierarchical communications.	Eur. J. Oper. Res.	2008	DBLP DOI BibTeX RDF
19	Birgit Schelm	Average-Case Non-Approximability of Optimisation Problems.	Theory Comput. Syst.	2007	DBLP DOI BibTeX RDF
19	Michael A. Ustinov	Non-approximability of the Randomness Deficiency Function.	CSR	2006	DBLP DOI BibTeX RDF
19	Bodo Manthey	Non-approximability of weighted multiple sequence alignment for arbitrary metrics.	Inf. Process. Lett.	2005	DBLP DOI BibTeX RDF
19	Sanjeev Arora, Eli Berger, Elad Hazan, Guy Kindler, Muli Safra	On Non-Approximability for Quadratic Programs	Electron. Colloquium Comput. Complex.	2005	DBLP BibTeX RDF
19	Michael R. Fellows, Frances A. Rosamond, Udi Rotics, Stefan Szeider	Proving NP-hardness for clique-width II: non-approximability of clique-width	Electron. Colloquium Comput. Complex.	2005	DBLP BibTeX RDF
19	Michael R. Fellows, Frances A. Rosamond, Udi Rotics, Stefan Szeider	Proving NP-hardness for clique-width I: non-approximability of sequential clique-width	Electron. Colloquium Comput. Complex.	2005	DBLP BibTeX RDF
19	Sanjeev Arora, Eli Berger, Elad Hazan, Guy Kindler, Muli Safra	On Non-Approximability for Quadratic Programs.	FOCS	2005	DBLP DOI BibTeX RDF
19	Birgit Schelm	Average-Case Non-approximability of Optimisation Problems.	FCT	2005	DBLP DOI BibTeX RDF
19	Craig A. Tovey	Non-approximability of precedence-constrained sequencing to minimize setups.	Discret. Appl. Math.	2004	DBLP DOI BibTeX RDF
19	Bodo Manthey	Non-approximability of weighted multiple sequence alignment.	Theor. Comput. Sci.	2003	DBLP DOI BibTeX RDF
19	Vojtech Bálint	The non-approximability of bicriteria network design problems.	J. Discrete Algorithms	2003	DBLP DOI BibTeX RDF
19	Venkatesan Guruswami, Piotr Indyk	Embeddings and non-approximability of geometric problems.	SODA	2003	DBLP BibTeX RDF
19	Christian Laforest	Construction of Efficient Communication Sub-structures: Non-approximability Results and Polynomial sub-cases.	Euro-Par	2003	DBLP DOI BibTeX RDF
19	Venkatesan T. Chakaravarthy, Susan Horwitz	On the non-approximability of points-to analysis.	Acta Informatica	2002	DBLP DOI BibTeX RDF
19	Bruno Codenotti, Igor E. Shparlinski	Non-approximability of the Permanent of Structured Matrices over Finite Fields	Electron. Colloquium Comput. Complex.	2002	DBLP BibTeX RDF
19	Noriyuki Fujimoto, Kenichi Hagihara	Non-approximability of the Bulk Synchronous Task Scheduling Problem.	Euro-Par	2002	DBLP DOI BibTeX RDF
19	Eric Angel, Evripidis Bampis, Rodolphe Giroudeau	Non-approximability Results for the Hierarchical Communication Problem with a Bounded Number of Clusters.	Euro-Par	2002	DBLP DOI BibTeX RDF
19	Han Hoogeveen, Petra Schuurman, Gerhard J. Woeginger	Non-Approximability Results for Scheduling Problems with Minsum Criteria.	INFORMS J. Comput.	2001	DBLP DOI BibTeX RDF
19	Bodo Siebert	Non-approximability of Weighted Multiple Sequence Alignment.	COCOON	2001	DBLP DOI BibTeX RDF
19	Andrea E. F. Clementi, Luca Trevisan	Improved Non-Approximability Results for Minimum Vertex Cover with Density Constraints.	Theor. Comput. Sci.	1999	DBLP DOI BibTeX RDF
19	Oded Goldreich 0001, Shafi Goldwasser	On the Limits of Non-Approximability of Lattice Problems.	STOC	1998	DBLP DOI BibTeX RDF
19	Oded Goldreich 0001, Shafi Goldwasser	On the Limits of Non-Approximability of Lattice Problems	Electron. Colloquium Comput. Complex.	1997	DBLP BibTeX RDF
19	Claus Rick, Hein Röhrig	Deriving Non-approximability Results by Reductions.	Lectures on Proof Verification and Approximation Algorithms	1997	DBLP DOI BibTeX RDF
19	Andrea E. F. Clementi, Luca Trevisan	Improved Non-approximability Results for Minimum Vertex Cover with Density Constraints	Electron. Colloquium Comput. Complex.	1996	DBLP BibTeX RDF
19	Andrea E. F. Clementi, Luca Trevisan	Improved Non-approximability Results for Vertex Cover with Density Constraints.	COCOON	1996	DBLP DOI BibTeX RDF
19	Mihir Bellare, Oded Goldreich 0001, Madhu Sudan 0001	Free Bits, PCP and Non-Approximability - Towards Tight Results	Electron. Colloquium Comput. Complex.	1995	DBLP BibTeX RDF
19	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
19	Mihir Bellare, Madhu Sudan 0001	Improved non-approximability results.	STOC	1994	DBLP DOI BibTeX RDF
14	Dvir Shabtay, George Steiner	Optimal due date assignment in multi-machine scheduling environments.	J. Sched.	2008	DBLP DOI BibTeX RDF	Multi-machine scheduling, Complexity, Approximation, Due date assignment
14	Fabian Kuhn, Thomas Moscibroda, Roger Wattenhofer	Unit disk graph approximation.	DIALM-POMC	2004	DBLP DOI BibTeX RDF	sensor networks, ad hoc networks, embedding, unit disk graph, virtual coordinates
12	Hassene Aissi, Cristina Bazgan, Daniel Vanderpooten	Approximation Complexity of min-max (Regret) Versions of Shortest Path, Spanning Tree, and Knapsack.	ESA	2005	DBLP DOI BibTeX RDF	min-max regret, mi-nimum spanning tree, approximation, shortest path, knapsack, min-max, fptas
12	Luisa Gargano, Adele A. Rescigno, Ugo Vaccaro	Multicasting to Groups in Optical Networks and Related Combinatorial Optimization Problems.	IPDPS	2003	DBLP DOI BibTeX RDF
12	Nitin Ahuja, Anand Srivastav	On Constrained Hypergraph Coloring and Scheduling.	APPROX	2002	DBLP DOI BibTeX RDF
12	Evripidis Bampis, Rodolphe Giroudeau, Alexander V. Kononov	Scheduling tasks with small communication delays for clusters of processors.	SPAA	2001	DBLP DOI BibTeX RDF
12	David P. Williamson	Gadgets, Approximation, and Linear Programming: Improved Hardness Results for Cut and Satisfiability Problems (Abstract of Invited Lecture).	WG	1997	DBLP DOI BibTeX RDF
12	Pierluigi Crescenzi	A Short Guide to Approximation Preserving Reductions.	CCC	1997	DBLP DOI BibTeX RDF	approximation preserving reductions, computational complexity, complexity, combinatorial optimization