Search results for "Approximability"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
94	Peter Jonsson, Johan Thapper	Approximability of the Maximum Solution Problem for Certain Families of Algebras.	CSR	2009	DBLP DOI BibTeX RDF	computational complexity, approximability, Optimisation, constraint satisfaction, algebra
77	Maxim Sviridenko, Gerhard J. Woeginger	Approximability and in-approximability results for no-wait shop scheduling.	FOCS	2000	DBLP DOI BibTeX RDF	in-approximability results, no-wait shop scheduling, makespan criterion, computational complexity, approximability, processor scheduling, polynomial time approximation scheme, polynomial approximation, APX-hard
68	Andrei A. Bulatov, Martin Grohe, Phokion G. Kolaitis, Andrei A. Krokhin	09441 Abstracts Collection - The Constraint Satisfaction Problem: Complexity and Approximability.	The Constraint Satisfaction Problem: Complexity and Approximability	2009	DBLP BibTeX RDF
68	Andrei A. Bulatov, Martin Grohe, Phokion G. Kolaitis, Andrei A. Krokhin	09441 Executive Summary - The Constraint Satisfaction Problem: Complexity and Approximability.	The Constraint Satisfaction Problem: Complexity and Approximability	2009	DBLP BibTeX RDF
61	Tommy Färnqvist, Peter Jonsson, Johan Thapper	Approximability Distance in the Space of H-Colourability Problems.	CSR	2009	DBLP DOI BibTeX RDF	graph H-colouring, computational complexity, approximability, optimisation, graph homomorphism
61	Fredrik Kuivinen	Approximability of Bounded Occurrence Max Ones.	MFCS	2006	DBLP DOI BibTeX RDF	Bounded occurrence, Max Ones, Approximability, Matching, Constraint satisfaction problems
60	Peter Jonsson, Fredrik Kuivinen, Gustav Nordh	Approximability of Integer Programming with Generalised Constraints.	CP	2006	DBLP DOI BibTeX RDF
60	Stefan Hougardy	Proof Checking and Non-approximability.	Lectures on Proof Verification and Approximation Algorithms	1997	DBLP DOI BibTeX RDF
52	Andrei A. Bulatov, Martin Grohe, Phokion G. Kolaitis, Andrei A. Krokhin (eds.)	The Constraint Satisfaction Problem: Complexity and Approximability, 25.10. - 30.10.2009	The Constraint Satisfaction Problem: Complexity and Approximability	2009	DBLP BibTeX RDF
52	Barnaby Martin, Jos Martin	The complexity of positive first-order logic without equality II: The four-element case.	The Constraint Satisfaction Problem: Complexity and Approximability	2009	DBLP BibTeX RDF
52	Ross Willard	PP-DEFINABILITY IS CO-NEXPTIME-COMPLETE.	The Constraint Satisfaction Problem: Complexity and Approximability	2009	DBLP BibTeX RDF
52	Matthew Valeriote, Simone Bova, Hubie Chen	On the Expression Complexity of Equivalence and Isomorphism of Primitive Positive Formulas.	The Constraint Satisfaction Problem: Complexity and Approximability	2009	DBLP BibTeX RDF
50	Martin Thimm	On the Approximability of the Steiner Tree Problem.	MFCS	2001	DBLP DOI BibTeX RDF	Minimum Steiner tree, Gadget reduction, Lower bounds, Approximability
49	Birgit Schelm	Average-Case Non-Approximability of Optimisation Problems.	Theory Comput. Syst.	2007	DBLP DOI BibTeX RDF
49	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	Birgit Schelm	Average-Case Non-approximability of Optimisation Problems.	FCT	2005	DBLP DOI BibTeX RDF
49	Béla Csaba, Marek Karpinski, Piotr Krysta	Approximability of dense and sparse instances of minimum 2-connectivity, TSP and path problems.	SODA	2002	DBLP BibTeX RDF
49	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
49	Sanjeev Khanna, Madhu Sudan 0001, Luca Trevisan	Constraint Satisfaction: The Approximability of Minimization Problems.	CCC	1997	DBLP DOI BibTeX RDF	complete problems, computational classes, computational complexity, Approximation algorithms, combinatorial optimization
43	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
38	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
38	Noriyuki Fujimoto	On Non-Approximability of Coarse-Grained Workflow Grid Scheduling.	ISPAN	2008	DBLP DOI BibTeX RDF	non-approximability, scheduling, grid computing, workflow
38	Christos H. Papadimitriou, Mihalis Yannakakis	On the Approximability of Trade-offs and Optimal Access of Web Sources.	FOCS	2000	DBLP DOI BibTeX RDF	Web sources, optimal access, cost criteria, Pareto curve, polynomially succinct curve, multiple linear objectives, cost-time-quality trade-off, information retrieval, World-Wide Web, computational complexity, complexity, approximability, optimisation, multiobjective optimization, information resources, trade-offs, combinatorial mathematics, combinatorial optimization problem, hyperplane
38	Sanjeev Khanna, Rajeev Motwani 0001, Madhu Sudan 0001, Umesh V. Vazirani	On Syntactic versus Computational Views of Approximability	FOCS	1994	DBLP DOI BibTeX RDF	computational classes, computational views, approximation classes, MAX SNP, structural results, approximability, syntactic
38	Khaled M. Elbassioni, Rajiv Raman 0001, Saurabh Ray, René Sitters	On the approximability of the maximum feasible subsystem problem with 0/1-coefficients.	SODA	2009	DBLP DOI BibTeX RDF
38	Moshe Babaioff, Patrick Briest, Piotr Krysta	On the Approximability of Combinatorial Exchange Problems.	SAGT	2008	DBLP DOI BibTeX RDF
38	Liming Cai, Xiuzhen Huang	Fixed-Parameter Approximation: Conceptual Framework and Approximability Results.	IWPEC	2006	DBLP DOI BibTeX RDF
38	Yijia Chen, Martin Grohe, Magdalena Grüber	On Parameterized Approximability.	IWPEC	2006	DBLP DOI BibTeX RDF
38	Fredrik Kuivinen	Tight Approximability Results for the Maximum Solution Equation Problem over Zp.	MFCS	2005	DBLP DOI BibTeX RDF
38	Tiziana Calamoneri, Paola Vocca	On the Approximability of the L(h, k)-Labelling Problem on Bipartite Graphs (Extended Abstract).	SIROCCO	2005	DBLP DOI BibTeX RDF
38	Giulia Galbiati, Edoardo Amaldi	On the Approximability of the Minimum Fundamental Cycle Basis Problem.	WAOA	2003	DBLP DOI BibTeX RDF
38	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
38	Hans-Joachim Böckenhauer, Juraj Hromkovic, Ralf Klasing, Sebastian Seibert, Walter Unger	An Improved Lower Bound on the Approximability of Metric TSP and Approximation Algorithms for the TSP with Sharpened Triangle Inequality.	STACS	2000	DBLP DOI BibTeX RDF
38	Toshihiro Fujito	On Approximability of the Independent/Connected Edge Dominating Set Problems.	FSTTCS	2000	DBLP DOI BibTeX RDF
38	Viggo Kann	Strong Lower Bounds on the Approximability of some NPO PB-Complete Maximization Problems.	MFCS	1995	DBLP DOI BibTeX RDF
38	Edoardo Amaldi, Viggo Kann	On the Approximability of Finding Maximum Feasible Subsystems of Linear Systems.	STACS	1994	DBLP DOI BibTeX RDF
34	Peter Jonsson, Andrei A. Krokhin, Fredrik Kuivinen	Ruling Out Polynomial-Time Approximation Schemes for Hard Constraint Satisfaction Problems.	CSR	2007	DBLP DOI BibTeX RDF	maximum constraint satisfaction, complexity, approximability
34	Han Hoogeveen, Martin Skutella, Gerhard J. Woeginger	Preemptive Scheduling with Rejection.	ESA	2000	DBLP DOI BibTeX RDF	in-approximability, Scheduling, computational complexity, approximation algorithm, preemption, worst case ratio
34	Sascha Ott	Lower Bounds for Approximating Shortest Superstrings over an Alphabet of Size 2.	WG	1999	DBLP DOI BibTeX RDF	Superstrings, lower bounds, approximability, APX-hardness
33	Christian Glaßer, Christian Reitwießner, Heinz Schmitz	Multiobjective Disk Cover Admits a PTAS.	ISAAC	2008	DBLP DOI BibTeX RDF
33	Julia Chuzhoy, Sudipto Guha, Eran Halperin, Sanjeev Khanna, Guy Kortsarz, Robert Krauthgamer, Joseph Naor	Asymmetric k-center is log* n-hard to approximate.	J. ACM	2005	DBLP DOI BibTeX RDF	asymmetric k-center, metric k-center, Approximation algorithms, hardness of approximation
33	Julia Chuzhoy, Sudipto Guha, Eran Halperin, Sanjeev Khanna, Guy Kortsarz, Joseph Naor	Asymmetric k-center is log* n-hard to approximate.	STOC	2004	DBLP DOI BibTeX RDF	asymmetric k-center, metric k-center, approximation algorithms, hardness of approximation
31	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
31	Davide Bilò, Luciano Gualà, Guido Proietti	Improved Approximability and Non-approximability Results for Graph Diameter Decreasing Problems.	MFCS	2010	DBLP DOI BibTeX RDF
31	Marc Demange, Vangelis Th. Paschos	The Approximability Behaviour of Some Combinatorial Problems with Respect to the Approximability of a Class of Maximum Independent Set Problems.	Comput. Optim. Appl.	1997	DBLP DOI BibTeX RDF
27	Binhai Zhu	Approximability and Fixed-Parameter Tractability for the Exemplar Genomic Distance Problems.	TAMC	2009	DBLP DOI BibTeX RDF
27	Marcel Ochel, Berthold Vöcking	Approximability of OFDMA Scheduling.	ESA	2009	DBLP DOI BibTeX RDF
27	Tomoko Izumi, Taisuke Izumi, Hirotaka Ono 0001, Koichi Wada 0001	Relationship between Approximability and Request Structures in the Minimum Certificate Dispersal Problem.	COCOON	2009	DBLP DOI BibTeX RDF
27	John Abraham, Zhixiang Chen 0001, Richard H. Fowler, Bin Fu, Binhai Zhu	On the Approximability of Some Haplotyping Problems.	AAIM	2009	DBLP DOI BibTeX RDF
27	Vladimir G. Deineko, Peter Jonsson, Mikael Klasson, Andrei A. Krokhin	The approximability of MAX CSP with fixed-value constraints.	J. ACM	2008	DBLP DOI BibTeX RDF	Complexity of approximation, maximum constraint satisfaction, dichotomy, Monge properties, supermodularity
27	Sylvain Guillemot	Parameterized Complexity and Approximability of the SLCS Problem.	IWPEC	2008	DBLP DOI BibTeX RDF
27	Till Tantau	Logspace Optimization Problems and Their Approximability Properties.	Theory Comput. Syst.	2007	DBLP DOI BibTeX RDF
27	Hans-Joachim Böckenhauer, Juraj Hromkovic, Joachim Kneis, Joachim Kupke 0002	The Parameterized Approximability of TSP with Deadlines.	Theory Comput. Syst.	2007	DBLP DOI BibTeX RDF
27	Xujin Chen, Xiaodong Hu 0001, Tianping Shuai	Inapproximability and approximability of maximal tree routing and coloring.	J. Comb. Optim.	2006	DBLP DOI BibTeX RDF	coloring, multicast routing, maximum independent set
27	Takehiro Ito, Erik D. Demaine, Xiao Zhou 0001, Takao Nishizeki	Approximability of Partitioning Graphs with Supply and Demand.	ISAAC	2006	DBLP DOI BibTeX RDF
27	Jérôme Monnot	On Complexity and Approximability of the Labeled Maximum/Perfect Matching Problems.	ISAAC	2005	DBLP DOI BibTeX RDF	labeled matching, approximate algorithms, NP-complete, bipartite graphs, colored matching
27	Bruno Escoffier, Jérôme Monnot, Vangelis Th. Paschos	Weighted Coloring: Further Complexity and Approximability Results.	ICTCS	2005	DBLP DOI BibTeX RDF	weighted coloring, line graph of bipartite graphs, Approximation algorithm, NP-complete problems, interval graphs, partial k-tree
27	Till Tantau	Logspace Optimization Problems and Their Approximability Properties.	FCT	2005	DBLP DOI BibTeX RDF
27	Alexander Grigoriev, Gerhard J. Woeginger	Project scheduling with irregular costs: complexity, approximability, and algorithms.	Acta Informatica	2004	DBLP DOI BibTeX RDF
27	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
27	Nikhil Bansal 0001, Maxim Sviridenko	New approximability and inapproximability results for 2-dimensional Bin Packing.	SODA	2004	DBLP BibTeX RDF
27	Dominique de Werra, Marc Demange, Jérôme Monnot, Vangelis Th. Paschos	The Hypocoloring Problem: Complexity and Approximability Results when the Chromatic Number Is Small.	WG	2004	DBLP DOI BibTeX RDF
27	Miroslav Chlebík, Janka Chlebíková	On Approximability of the Independent Set Problem for Low Degree Graphs.	SIROCCO	2004	DBLP DOI BibTeX RDF
27	Alexander Grigoriev, Gerhard J. Woeginger	Project Scheduling with Irregular Costs: Complexity, Approximability, and Algorithms.	ISAAC	2002	DBLP DOI BibTeX RDF
27	Antonio Miranda, Luz Torres, Jianer Chen	On the Approximability of Multiprocessor Task Scheduling Problems.	ISAAC	2002	DBLP DOI BibTeX RDF
27	Marek Karpinski	Approximability of the Minimum Bisection Problem: An Algorithmic Challenge.	MFCS	2002	DBLP DOI BibTeX RDF
27	Gerhard J. Woeginger	On the Approximability of Average Completion Time Scheduling under Precedence Constraints.	ICALP	2001	DBLP DOI BibTeX RDF
27	Luca Trevisan	Non-approximability results for optimization problems on bounded degree instances.	STOC	2001	DBLP DOI BibTeX RDF
27	Bodo Siebert	Non-approximability of Weighted Multiple Sequence Alignment.	COCOON	2001	DBLP DOI BibTeX RDF
27	Harry B. Hunt III, Madhav V. Marathe, Richard Edwin Stearns	Strongly-local reductions and the complexity/efficient approximability of algebra and optimization on abstract algebraic structures.	ISSAC	2001	DBLP DOI BibTeX RDF
27	Han Hoogeveen, Petra Schuurman, Gerhard J. Woeginger	Non-approximability Results for Scheduling Problems with Minsum Criteria.	IPCO	1998	DBLP DOI BibTeX RDF
27	Martin Mundhenk, Anna Slobodová	Optimal Non-approximability of MAXCLIQUE.	Lectures on Proof Verification and Approximation Algorithms	1997	DBLP DOI BibTeX RDF
27	Maria J. Serna, Fatos Xhafa	The Parallel Approximability of a Subclass of Quadratic Programming.	ICPADS	1997	DBLP DOI BibTeX RDF	Parallel Approximation Algorithms, De-randomization, Quadratic Programming, Randomized Rounding
27	David Fernández-Baca, Jens Lagergren	On the Approximability of the Steiner Tree Problem in Phylogeny.	ISAAC	1996	DBLP DOI BibTeX RDF
27	Ian Barland, Phokion G. Kolaitis, Madhukar N. Thakur	Integer Programming as a Framework for Optimization and Approximability.	CCC	1996	DBLP DOI BibTeX RDF	structural complexity theory, approximation algorithms, combinatorial optimization, Integer Programming
27	Sven Oliver Krumke, Hartmut Noltemeier, S. S. Ravi, Madhav V. Marathe	Complexity and Approximability of Certain Bicriteria Location Problems.	WG	1995	DBLP DOI BibTeX RDF
27	Mihalis Yannakakis	Recent Developments on the Approximability of Combinatorial Problems.	ISAAC	1993	DBLP DOI BibTeX RDF
23	C. Thach Nguyen, Nguyen Bao Nguyen, Wing-Kin Sung, Louxin Zhang	Reconstructing Recombination Network from Sequence Data: The Small Parsimony Problem.	IEEE ACM Trans. Comput. Biol. Bioinform.	2007	DBLP DOI BibTeX RDF	parsimony method, dynamic programming, approximability, NP-hardness, combination network, phylogenetic network
23	Evripidis Bampis, Alexander V. Kononov	Bicriteria approximation algorithms for scheduling problems with communications delays.	J. Sched.	2005	DBLP DOI BibTeX RDF	scheduling, approximability, communications delays, multicriteria optimization
23	Tapio Elomaa, Matti Kääriäinen	The Difficulty of Reduced Error Pruning of Leveled Branching Programs.	Ann. Math. Artif. Intell.	2004	DBLP DOI BibTeX RDF	reduced error pruning, approximability, NP-completeness, concept learning, branching programs
23	Andrea E. F. Clementi, Paolo Penna, Riccardo Silvestri	On the Power Assignment Problem in Radio Networks.	Mob. Networks Appl.	2004	DBLP DOI BibTeX RDF	ad-hoc radio networks, approximability, NP-completeness, energy consumption
23	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
22	Arnab Bhattacharyya 0001, Elena Grigorescu, Kyomin Jung, Sofya Raskhodnikova, David P. Woodruff	Transitive-closure spanners.	SODA	2009	DBLP DOI BibTeX RDF
22	Chee-Keng Yap	Theory of Real Computation According to EGC.	Reliable Implementation of Real Number Algorithms	2008	DBLP DOI BibTeX RDF
22	Jiong Guo, Rolf Niedermeier, Sebastian Wernicke 0001	Parameterized Complexity of Vertex Cover Variants.	Theory Comput. Syst.	2007	DBLP DOI BibTeX RDF
22	Naveen Garg 0001, Amit Kumar 0001	Minimizing Average Flow-time : Upper and Lower Bounds.	FOCS	2007	DBLP DOI BibTeX RDF
22	Hermann Gruber, Markus Holzer 0001	Inapproximability of Nondeterministic State and Transition Complexity Assuming P=!NP.	Developments in Language Theory	2007	DBLP DOI BibTeX RDF
22	Jaroslaw Byrka	An Optimal Bifactor Approximation Algorithm for the Metric Uncapacitated Facility Location Problem.	APPROX-RANDOM	2007	DBLP DOI BibTeX RDF
22	Hans-Joachim Böckenhauer, Juraj Hromkovic, Joachim Kneis, Joachim Kupke 0002	On the Approximation Hardness of Some Generalizations of TSP.	SWAT	2006	DBLP DOI BibTeX RDF
22	David P. Woodruff	Better Approximations for the Minimum Common Integer Partition Problem.	APPROX-RANDOM	2006	DBLP DOI BibTeX RDF
22	Jiong Guo, Rolf Niedermeier, Sebastian Wernicke 0001	Parameterized Complexity of Generalized Vertex Cover Problems.	WADS	2005	DBLP DOI BibTeX RDF
22	Miroslav Chlebík, Janka Chlebíková	On Approximation Hardness of the Minimum 2SAT-DELETION Problem.	MFCS	2004	DBLP DOI BibTeX RDF
22	Alberto Caprara	Packing 2-Dimensional Bins in Harmony.	FOCS	2002	DBLP DOI BibTeX RDF
22	Christopher Umans	On the Complexity and Inapproximability of Shortest Implicant Problems.	ICALP	1999	DBLP DOI BibTeX RDF
22	Vangelis Th. Paschos	A Survey of Approximately Optimal Solutions to Some Covering and Packing Problems.	ACM Comput. Surv.	1997	DBLP DOI BibTeX RDF	approximation algorithms, constrained optimization, combinatorial algorithms, algorithm analysis, problem complexity
22	Douglas N. Arnold, Xiaobo Liu	Interior estimates for a low order finite element method for the Reissner-Mindlin plate model.	Adv. Comput. Math.	1997	DBLP DOI BibTeX RDF	Reissner-Mindlin plate, interior error estimate, 73N10, 65N30, mixed finite element, boundary layer
22	Viggo Kann	Polynomially Bounded Minimization Problems which are Hard to Approximate.	ICALP	1993	DBLP DOI BibTeX RDF
16	Christian Rieger, Holger Wendland	On the Approximability and Curse of Dimensionality of Certain Classes of High-Dimensional Functions.	SIAM J. Numer. Anal.	2024	DBLP DOI BibTeX RDF
16	Yann Disser, David Weckbecker	Unified Greedy Approximability beyond Submodular Maximization.	SIAM J. Discret. Math.	2024	DBLP DOI BibTeX RDF
16	Chi-Ning Chou, Alexander Golovnev, Madhu Sudan 0001, Santhoshini Velusamy	Sketching Approximability of All Finite CSPs.	J. ACM	2024	DBLP DOI BibTeX RDF