Search results for "APX-hardness"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
129	Sounaka Mishra, Kripasindhu Sikdar	On the Hardness of Approximating Some NP-optimization Problems Related to Minimum Linear Ordering Problem.	IFIP TCS	2000	DBLP DOI BibTeX RDF	NP-optimization problems, Minimaximal and maximinimal NP-optimization problems, L-reduction, Approximation algorithms, Hardness of approximation, APX-hardness
107	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
82	Bernhard Fuchs	On the Hardness of Range Assignment Problems.	CIAC	2006	DBLP DOI BibTeX RDF
56	Julia Chuzhoy, Sanjeev Khanna	Hardness of cut problems in directed graphs.	STOC	2006	DBLP DOI BibTeX RDF	directed multicut, hardness of approximation, sparsest cut
48	Miroslav Chlebík, Janka Chlebíková	Approximation hardness of optimization problems in intersection graphs of d-dimensional boxes.	SODA	2005	DBLP BibTeX RDF
42	Joseph Cheriyan, Mohammad R. Salavatipour	Hardness and Approximation Results for Packing Steiner Trees.	Algorithmica	2006	DBLP DOI BibTeX RDF	Approximation algorithms, Steiner trees, Hardness of approximation, Packing problems
42	Joseph Cheriyan, Mohammad R. Salavatipour	Hardness and Approximation Results for Packing Steiner Trees.	ESA	2004	DBLP DOI BibTeX RDF
41	Sébastien Angibaud, Guillaume Fertin, Irena Rusu	On the Approximability of Comparing Genomes with Duplicates.	WALCOM	2008	DBLP DOI BibTeX RDF	conserved intervals, genome rearrangement, duplicates, breakpoints, adjacencies, common intervals, APX-Hardness
41	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
40	Basile Couëtoux, Laurent Gourvès, Jérôme Monnot, Orestis Telelis	On Labeled Traveling Salesman Problems.	ISAAC	2008	DBLP DOI BibTeX RDF
40	Moses Charikar, Venkatesan Guruswami, Anthony Wirth	Clustering with Qualitative Information.	FOCS	2003	DBLP DOI BibTeX RDF
39	Jingyang Zhao 0001, Mingyu Xiao 0001	The APX-hardness of the Traveling Tournament Problem.	CoRR	2023	DBLP DOI BibTeX RDF
39	Debajyoti Mondal, Angelin Jemima Rajasingh, N. Parthiban, Indra Rajasingh	APX-hardness and approximation for the k-burning number problem.	Theor. Comput. Sci.	2022	DBLP DOI BibTeX RDF
39	Mayank Chaturvedi, Bengt J. Nilsson	APX-Hardness of the Minimum Vision Points Problem.	CoRR	2022	DBLP DOI BibTeX RDF
39	Debajyoti Mondal, N. Parthiban, V. Kavitha 0003, Indra Rajasingh	APX-Hardness and Approximation for the k-Burning Number Problem.	WALCOM	2021	DBLP DOI BibTeX RDF
39	Debajyoti Mondal, N. Parthiban, V. Kavitha 0003, Indra Rajasingh	APX-Hardness and Approximation for the k-Burning Number Problem.	CoRR	2020	DBLP BibTeX RDF
39	Euiwoong Lee	APX-hardness of maximizing Nash social welfare with indivisible items.	Inf. Process. Lett.	2017	DBLP DOI BibTeX RDF
39	Euiwoong Lee	APX-Hardness of Maximizing Nash Social Welfare with Indivisible Items.	CoRR	2015	DBLP BibTeX RDF
39	Timothy M. Chan, Elyot Grant	Exact algorithms and APX-hardness results for geometric packing and covering problems.	Comput. Geom.	2014	DBLP DOI BibTeX RDF
39	Nabil H. Mustafa, Rajiv Raman 0001, Saurabh Ray	Settling the APX-Hardness Status for Geometric Set Cover.	FOCS	2014	DBLP DOI BibTeX RDF
39	Elyot Grant, Timothy M. Chan	Exact Algorithms and APX-Hardness Results for Geometric Set Cover.	CCCG	2011	DBLP BibTeX RDF
39	Mirela Damian, Sriram V. Pemmaraju	APX-hardness of domination problems in circle graphs.	Inf. Process. Lett.	2006	DBLP DOI BibTeX RDF
33	Rohit Khandekar, Tracy Kimbrel, Konstantin Makarychev, Maxim Sviridenko	On Hardness of Pricing Items for Single-Minded Bidders.	APPROX-RANDOM	2009	DBLP DOI BibTeX RDF
33	Nikhil Bansal 0001, Amit Chakrabarti, Amir Epstein, Baruch Schieber	A quasi-PTAS for unsplittable flow on line graphs.	STOC	2006	DBLP DOI BibTeX RDF	scheduling, approximation algorithms, resource allocation, approximation scheme, unsplittable flow
33	Hans-Joachim Böckenhauer, Dirk Bongartz, Juraj Hromkovic, Ralf Klasing, Guido Proietti, Sebastian Seibert, Walter Unger	On the Hardness of Constructing Minimal 2-Connected Spanning Subgraphs in Complete Graphs with Sharpened Triangle Inequality.	FSTTCS	2002	DBLP DOI BibTeX RDF	minimum-cost biconnected spanning subgraph, Approximation algorithm, inapproximability, augmentation
27	Patrick Briest, Piotr Krysta	Single-minded unlimited supply pricing on sparse instances.	SODA	2006	DBLP DOI BibTeX RDF
27	Uriel Feige, Jan Vondrák	Approximation algorithms for allocation problems: Improving the factor of 1 - 1/e.	FOCS	2006	DBLP DOI BibTeX RDF
27	Alexander Grigoriev, Joyce van Loon, René Sitters, Marc Uetz	How to Sell a Graph: Guidelines for Graph Retailers.	WG	2006	DBLP DOI BibTeX RDF	Pricing problems, tollbooth problem, highway problem, computational complexity, dynamic programming, fully polynomial time approximation scheme
20	Cristina Bazgan, Basile Couëtoux, Zsolt Tuza	Covering a Graph with a Constrained Forest (Extended Abstract).	ISAAC	2009	DBLP DOI BibTeX RDF
20	Piotr Berman, Bhaskar DasGupta, Marek Karpinski	Approximating Transitive Reductions for Directed Networks.	WADS	2009	DBLP DOI BibTeX RDF
20	Rohit Khandekar, Guy Kortsarz, Vahab S. Mirrokni, Mohammad R. Salavatipour	Two-Stage Robust Network Design with Exponential Scenarios.	ESA	2008	DBLP DOI BibTeX RDF
20	Thomas Erlebach, Erik Jan van Leeuwen	Domination in Geometric Intersection Graphs.	LATIN	2008	DBLP DOI BibTeX RDF
20	Michael Krivelevich, Zeev Nutov, Mohammad R. Salavatipour, Jacques Verstraëte, Raphael Yuster	Approximation algorithms and hardness results for cycle packing problems.	ACM Trans. Algorithms	2007	DBLP DOI BibTeX RDF	Cycle packing, edge-disjoint, approximation algorithms, hardness of approximation, integrality gap
20	Toshimasa Ishii	Greedy Approximation for Source Location Problem with Vertex-Connectivity Requirements in Undirected Graphs.	ISAAC	2007	DBLP DOI BibTeX RDF
20	Venkatesan Guruswami	On 2-Query Codeword Testing with Near-Perfect Completeness.	ISAAC	2006	DBLP DOI BibTeX RDF
20	Ralf Klasing, Euripides Markou, Tomasz Radzik, Fabiano Sarracco	Approximation Bounds for Black Hole Search Problems.	OPODIS	2005	DBLP DOI BibTeX RDF	black hole search, approximation algorithm, mobile agent, inapproximability, graph exploration
20	Dirk Bongartz	Some Notes on the Complexity of Protein Similarity Search under mRNA Structure Constraints.	SOFSEM	2004	DBLP DOI BibTeX RDF
20	Yossi Azar, Leah Epstein, Yossi Richter, Gerhard J. Woeginger	All-Norm Approximation Algorithms.	SWAT	2002	DBLP DOI BibTeX RDF
20	Bjarni V. Halldórsson, Magnús M. Halldórsson, R. Ravi 0001	On the Approximability of the Minimum Test Collection Problem.	ESA	2001	DBLP DOI BibTeX RDF