Search results for "MAXSNP-hard"

Found 13 publication records. Showing 13 according to the selection in the facets

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
44	Serafim Batzoglou, Sorin Istrail	Physical Mapping with Repeated Probes: The Hypergraph Superstring Problem.	CPM	1999	DBLP DOI BibTeX RDF
42	Sanjeev Arora, Carsten Lund, Rajeev Motwani 0001, Madhu Sudan 0001, Mario Szegedy	Proof Verification and Hardness of Approximation Problems	FOCS	1992	DBLP DOI BibTeX RDF	approximation problems, polynomial-time probabilistic oracle machine, random bits, MAXSNP-hard, metric TSP, time complexity, NP, MAX-CUT, MAX-SAT, proof verification
29	Takehiro Ito, Erik D. Demaine, Xiao Zhou 0001, Takao Nishizeki	Approximability of Partitioning Graphs with Supply and Demand.	ISAAC	2006	DBLP DOI BibTeX RDF
26	Xiucui Guan, Jie Su	Further Research on Node Based Bottleneck Improvement Problem for Multicut.	ICIC (1)	2006	DBLP DOI BibTeX RDF
26	Giulia Galbiati, Edoardo Amaldi	On the Approximability of the Minimum Fundamental Cycle Basis Problem.	WAOA	2003	DBLP DOI BibTeX RDF
26	Avrim Blum, Tao Jiang 0001, Ming Li 0001, John Tromp, Mihalis Yannakakis	Linear Approximation of Shortest Superstrings.	J. ACM	1994	DBLP DOI BibTeX RDF	shortest common superstring, approximation algorithm
23	Yuichi Asahiro, Eiji Miyano, Shinichi Shimoirisa	Grasp and Delivery for Moving Objects on Broken Lines.	Theory Comput. Syst.	2008	DBLP DOI BibTeX RDF	Grasp and delivery, MAXSNP-hardness, Approximation algorithm, Moving objects
23	Harold N. Gabow	Upper degree-constrained partial orientations.	SODA	2006	DBLP DOI BibTeX RDF
23	Yuichi Asahiro, Eiji Miyano, Shinichi Shimoirisa	Pickup and Delivery for Moving Objects on Broken Lines.	ICTCS	2005	DBLP DOI BibTeX RDF
23	Artur Czumaj, Michelangelo Grigni, Papa A. Sissokho, Hairong Zhao	Approximation schemes for minimum 2-edge-connected and biconnected subgraphs in planar graphs.	SODA	2004	DBLP BibTeX RDF
23	Christof Krick, Harald Räcke, Matthias Westermann	Approximation Algorithms for Data Management in Networks.	Theory Comput. Syst.	2003	DBLP DOI BibTeX RDF
23	Ivan D. Baev, Rajmohan Rajaraman	Approximation algorithms for data placement in arbitrary networks.	SODA	2001	DBLP BibTeX RDF
23	Elias Koutsoupias, Christos H. Papadimitriou, Mihalis Yannakakis	Searching a Fixed Graph.	ICALP	1996	DBLP DOI BibTeX RDF

Displaying result #1 - #13 of 13 (100 per page; Change: )