Search results for "approximability"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
11	Andrea E. F. Clementi, Afonso Ferreira, Paolo Penna, Stephane Perennes, Riccardo Silvestri	The Minimum Range Assignment Problem on Linear Radio Networks.	ESA	2000	DBLP DOI BibTeX RDF
11	Johan Håstad	Which NP-Hard Optimization Problems Admit Non-trivial Efficient Approximation Algorithms?	ICALP	2000	DBLP DOI BibTeX RDF
11	Michael Elkin, David Peleg	Strong Inapproximability of the Basic k-Spanner Problem.	ICALP	2000	DBLP DOI BibTeX RDF
11	Tamar Eilam, Shlomo Moran, Shmuel Zaks	Approximation Algorithms for Survivable Optical Networks.	DISC	2000	DBLP DOI BibTeX RDF
11	Goran Konjevod, Sven Oliver Krumke, Madhav V. Marathe	Budget Constrained Minimum Cost Connected Medians.	WG	2000	DBLP DOI BibTeX RDF
11	Michael Elkin, David Peleg	The Hardness of Approximating Spanner Problems.	STACS	2000	DBLP DOI BibTeX RDF
11	Arnold L. Rosenberg	Optimal schedules for data-parallel cycle-stealing in networks of workstations (extended abstract).	SPAA	2000	DBLP DOI BibTeX RDF
11	Amotz Bar-Noy, Magnús M. Halldórsson, Guy Kortsarz, Ravit Salman, Hadas Shachnai	Sum Multi-coloring of Graphs.	ESA	1999	DBLP DOI BibTeX RDF
11	Gerhard J. Woeginger	An FPTAS for Agreeably Weighted Variance on a Single Machine.	ICALP	1999	DBLP DOI BibTeX RDF
11	Hans-Christoph Wirth, Jan Steffan	On Minimum Diameter Spanning Trees under Reload Costs.	WG	1999	DBLP DOI BibTeX RDF	Node weighted graphs, Network Design, Spanning Tree, Diameter, Transportation problems
11	Michael A. Bender, Chandra Chekuri	Performance Guarantees for the TSP with a Parameterized Triangle Inequality.	WADS	1999	DBLP DOI BibTeX RDF
11	Juraj Hromkovic	Stability of Approximation Algorithms for Hard Optimization Problems.	SOFSEM	1999	DBLP DOI BibTeX RDF
11	Andrea E. F. Clementi, Pierluigi Crescenzi, Gianluca Rossi	On the Complexity of Approximating Colored-Graph Problems.	COCOON	1999	DBLP DOI BibTeX RDF
11	Magnús M. Halldórsson	Approximations of Weighted Independent Set and Hereditary Subset Problems.	COCOON	1999	DBLP DOI BibTeX RDF
11	Daniel W. Engels, David R. Karger, Stavros G. Kolliopoulos, Sudipta Sengupta, R. N. Uma, Joel Wein	Techniques for Scheduling with Rejection.	ESA	1998	DBLP DOI BibTeX RDF
11	Bang Ye Wu, Kun-Mao Chao, Chuan Yi Tang	Approximation and Exact Algorithms for Constructing Minimum Ultrametric Trees from Distance Matrices.	COCOON	1998	DBLP DOI BibTeX RDF	ultrametric trees, approximation algorithms, branch and bound, computational biology
11	Stavros G. Kolliopoulos, Clifford Stein 0001	Improved Approximation Algorithms for Unsplittable Flow Problems.	FOCS	1997	DBLP DOI BibTeX RDF
11	Toshihiro Fujito	A Primal-Dual Approach to Approximation of Node-Deletion Problems for Matroidal Properties.	ICALP	1997	DBLP DOI BibTeX RDF
11	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
11	Sachin B. Patkar, Shabbir H. Batterywala, M. Chandramouli, H. Narayanan	A New Partitioning Strategy Based on Supermodular Functions.	VLSI Design	1997	DBLP DOI BibTeX RDF
11	Pierluigi Crescenzi	A Short Guide to Approximation Preserving Reductions.	CCC	1997	DBLP DOI BibTeX RDF	approximation preserving reductions, computational complexity, complexity, combinatorial optimization
11	Noga Alon, János Csirik, Sergey V. Sevastianov, Arjen P. A. Vestjens, Gerhard J. Woeginger	On-line and Off-line Approximation Algorithms for Vector Covering Problems.	ESA	1996	DBLP DOI BibTeX RDF	Approximation algorithm, on-line algorithm, covering problem, packing problem, worst case ratio
11	Toshihiro Fujito	A Unified Local Ratio Approximation of Node-Deletion Problems (Extended Abstract).	ESA	1996	DBLP DOI BibTeX RDF
11	Ewa Malesinska, Alessandro Panconesi	On the Hardness of Allocating Frequencies for Hybrid Networks.	WG	1996	DBLP DOI BibTeX RDF
11	Michele Flammini, Giorgio Gambosi, Sandro Salomone	Interval Routing Schemes.	STACS	1995	DBLP DOI BibTeX RDF	Topics computational complexity, theory of parallel and distributed computing
11	Tatsuya Akutsu, Magnús M. Halldórsson	On the Approximation of Largest Common Subtrees and Largest Common Point Sets.	ISAAC	1994	DBLP DOI BibTeX RDF
11	Martin Middendorf	On the Approximation of Finding Various Minimal, Maximal, and Consistent Sequences.	ISAAC	1994	DBLP DOI BibTeX RDF
11	Surajit Chaudhuri, Phokion G. Kolaitis	Can Datalog be Approximated?	PODS	1994	DBLP DOI BibTeX RDF	Datalog
11	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
11	Erich Grädel, Anders Malmström	Approximable Minimization Problems and Optimal Solutions on Random Inputs.	CSL	1993	DBLP DOI BibTeX RDF
11	Luca Aceto, Matthew Hennessy	Termination, Deadlock, and Divergence.	J. ACM	1992	DBLP DOI BibTeX RDF
11	Edmund Ihler	The Complexity of Approximating the Class Steiner Tree Problem.	WG	1991	DBLP DOI BibTeX RDF