Search results for "APX-complete"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
83	Pierluigi Crescenzi, Luca Trevisan	On Approximation Scheme Preserving Reducability and Its Applications.	FSTTCS	1994	DBLP DOI BibTeX RDF
66	Euripides Markou, Stathis Zachos, Christodoulos Fragoudakis	Maximizing the Guarded Boundary of an Art Gallery Is APX-Complete.	CIAC	2003	DBLP DOI BibTeX RDF
50	Cristina Bazgan, Bruno Escoffier, Vangelis Th. Paschos	Poly-APX- and PTAS-Completeness in Standard and Differential Approximation.	ISAAC	2004	DBLP DOI BibTeX RDF
38	Bruno Escoffier, Laurent Gourvès, Jérôme Monnot	Complexity and Approximation Results for the Connected Vertex Cover Problem.	WG	2007	DBLP DOI BibTeX RDF	Connected vertex cover, APX-complete, approximation algorithm, planar graphs, bipartite graphs, chordal graphs
35	Salomon Bendayan, Joseph Cheriyan, Kevin K. H. Cheung	Unconstrained traveling tournament problem is APX-complete.	Oper. Res. Lett.	2023	DBLP DOI BibTeX RDF
35	Salomon Bendayan, Joseph Cheriyan, Kevin K. H. Cheung	Unconstrained Traveling Tournament Problem is APX-complete.	CoRR	2022	DBLP DOI BibTeX RDF
35	Raffaele Bruno 0001, Vania Conan, Stéphane Rousseau	Maximizing the number of accepted flows in TDMA-based wireless ad hoc networks is APX-complete	CoRR	2009	DBLP BibTeX RDF
35	Christodoulos Fragoudakis, Euripides Markou, Stathis Zachos	Maximizing the guarded boundary of an Art Gallery is APX-complete.	Comput. Geom.	2007	DBLP DOI BibTeX RDF
35	Viggo Kann, Jens Lagergren, Alessandro Panconesi	Approximability of Maximum Splitting of k-Sets and Some Other Apx-Complete Problems.	Inf. Process. Lett.	1996	DBLP DOI BibTeX RDF
30	Omid Amini, Stéphane Pérennes, Ignasi Sau	Hardness and Approximation of Traffic Grooming.	ISAAC	2007	DBLP DOI BibTeX RDF	SONET ADM, Approximation Algorithms, Optical Networks, PTAS, inapproximability, Traffic Grooming, APX-hardness
30	Khaled M. Elbassioni, Irit Katriel, Martin Kutz, Meena Mahajan	Simultaneous Matchings.	ISAAC	2005	DBLP DOI BibTeX RDF
30	David Fernández-Baca, Jens Lagergren	On the Approximability of the Steiner Tree Problem in Phylogeny.	ISAAC	1996	DBLP DOI BibTeX RDF
19	Markus Bläser, Bodo Manthey	Approximating Maximum Weight Cycle Covers in Directed Graphs with Weights Zero and One.	Algorithmica	2005	DBLP DOI BibTeX RDF	Approximation algorithms, Combinatorial optimization, Traveling salesman problem, Inapproximability, Cycle covers
17	Li Liu 0001, Hao Li, Junling Wang, Lian Li 0003, Caihong Li	Heuristics for Mobile Object Tracking Problem in Wireless Sensor Networks.	FAW	2009	DBLP DOI BibTeX RDF
17	Eui-woong Lee, David Buchfuhrer, Lachlan L. H. Andrew, Ao Tang, Steven H. Low	Progress on pricing with peering.	CISS	2008	DBLP DOI BibTeX RDF
17	Andreas Bley	On the complexity of vertex-disjoint length-restricted path problems.	Comput. Complex.	2003	DBLP DOI BibTeX RDF	Mathematics Subject Classification (2000). 68Q25, 90C27, 05C38, 05C40
15	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
15	Antonio Miranda, Luz Torres, Jianer Chen	On the Approximability of Multiprocessor Task Scheduling Problems.	ISAAC	2002	DBLP DOI BibTeX RDF
15	S. Mishra, Jaikumar Radhakrishnan, Sivaramakrishnan Sivasubramanian	On the Hardness of Approximating Minimum Monopoly Problems.	FSTTCS	2002	DBLP DOI BibTeX RDF
15	Clemens Gröpl, Stefan Hougardy, Till Nierhoff, Hans Jürgen Prömel	Lower Bounds for Approximation Algorithms for the Steiner Tree Problem.	WG	2001	DBLP DOI BibTeX RDF
15	Paola Alimonti, Viggo Kann	Hardness of Approximating Problems on Cubic Graphs.	CIAC	1997	DBLP DOI BibTeX RDF