Search results for "inapproximability"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
70	Michael Elkin, David Peleg	Strong Inapproximability of the Basic k-Spanner Problem.	ICALP	2000	DBLP DOI BibTeX RDF
65	Erik D. Demaine, Mohammad Taghi Hajiaghayi, Uriel Feige, Mohammad R. Salavatipour	Combination can be hard: approximability of the unique coverage problem.	SODA	2006	DBLP DOI BibTeX RDF
52	Zhixiang Chen 0001, Richard H. Fowler, Bin Fu, Binhai Zhu	On the inapproximability of the exemplar conserved interval distance problem of genomes.	J. Comb. Optim.	2008	DBLP DOI BibTeX RDF	Exemplar conserved interval distance, Weak approximation, Approximation algorithm, Genome rearrangement, Inapproximability
52	Thomas Erlebach, Alexander Hall	NP-Hardness of Broadcast Scheduling and Inapproximability of Single-Source Unsplittable Min-Cost Flow.	J. Sched.	2004	DBLP DOI BibTeX RDF	approximation algorithm, NP-complete, inapproximability, resource augmentation, broadcast scheduling
52	Johan Håstad	Some optimal inapproximability results.	J. ACM	2001	DBLP DOI BibTeX RDF	NP-hard optimization problems, max-sat, linear equations, Inapproximability, probabilistically checkable proofs
47	Kord Eickmeyer, Martin Grohe, Magdalena Grüber	Approximation of Natural W[P]-Complete Minimisation Problems Is Hard.	CCC	2008	DBLP DOI BibTeX RDF	derandomisation, parameterized complexity, inapproximability
47	Michael Alekhnovich, Sanjeev Arora, Iannis Tourlakis	Towards strong nonapproximability results in the Lovasz-Schrijver hierarchy.	STOC	2005	DBLP DOI BibTeX RDF	Lovász-Schrijver matrix cuts, inapproximability, integrality gaps
44	Hermann Gruber, Markus Holzer 0001	Inapproximability of Nondeterministic State and Transition Complexity Assuming P=!NP.	Developments in Language Theory	2007	DBLP DOI BibTeX RDF
44	Subhash Khot	Guest column: inapproximability results via Long Code based PCPs.	SIGACT News	2005	DBLP DOI BibTeX RDF
44	Piotr Berman, Marek Karpinski	On Some Tighter Inapproximability Results (Extended Abstract).	ICALP	1999	DBLP DOI BibTeX RDF	Approximation Hardness, Bounded Dependency Satisfiability, Breakpoint Graphs, Node Cover, Approximation Algorithms, Independent Set, MAX-CUT, Sorting by Reversals
39	Arnab Bhattacharyya 0001, Elena Grigorescu, Kyomin Jung, Sofya Raskhodnikova, David P. Woodruff	Transitive-closure spanners.	SODA	2009	DBLP DOI BibTeX RDF
39	Allan Borodin, David Cashman, Avner Magen	How Well Can Primal-Dual and Local-Ratio Algorithms Perform?.	ICALP	2005	DBLP DOI BibTeX RDF
39	Christopher Umans	Hardness of Approximating Sigma2p Minimization Problems.	FOCS	1999	DBLP DOI BibTeX RDF	computational complexity, hardness of approximation, logic minimization, dispersers, polynomial hierarchy
39	Chunmei Liu, Yinglei Song, Legand L. Burge III	Parameterized lower bound and inapproximability of polylogarithmic string barcoding.	J. Comb. Optim.	2008	DBLP DOI BibTeX RDF	Polylogarithmic string barcoding, Parameterized lower bound, Inapproximability
39	Bhaskar DasGupta, Sergio Ferrarini, Uthra Gopalakrishnan, Nisha Raj Paryani	Inapproximability results for the lateral gene transfer problem.	J. Comb. Optim.	2006	DBLP DOI BibTeX RDF	Lateral gene transfer, Phylogeny, Inapproximability
39	Sanjeev Arora	Reductions, Codes, PCPs, and Inapproximability.	FOCS	1995	DBLP DOI BibTeX RDF	NP-hard functions, code-like Levin reduction, complexity assumption, positive fraction, 3-colorable graph, code-like reduction, computational complexity, graph theory, error correction codes, error-correcting codes, NP-hardness, codes, inapproximability, PCPs, hardness, approximation ratio
34	Zhou Xu 0001, Liang Xu	Approximation Algorithms for Min-Max Path Cover Problems with Service Handling Time.	ISAAC	2009	DBLP DOI BibTeX RDF	min-max vehicle routing, approximation algorithm, inapproximability, path covers
34	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
34	Tommy Färnqvist, Peter Jonsson	Bounded Tree-Width and CSP-Related Problems.	ISAAC	2007	DBLP DOI BibTeX RDF	Computational complexity, constraint satisfaction, homomorphism, inapproximability, relational structure
34	Jin-yi Cai, Hong Zhu 0004	Progress in Computational Complexity Theory.	J. Comput. Sci. Technol.	2005	DBLP DOI BibTeX RDF	computational complexity theory, PCP theorem, logspace complexity, Reingold's theorem, GAP problem, complexity of lattice problems, worst-case to average-case reductions, extractors, pseudorandomness, inapproximability, primality testing, theoretical computer science, holographic algorithms
34	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
34	Oleg A. Prokopyev, Panos M. Pardalos	Minimum elsilon-equivalent Circuit Size Problem.	J. Comb. Optim.	2004	DBLP DOI BibTeX RDF	minimum circuit size problem, natural properties, combinatorial optimization, approximation, inapproximability, Boolean circuits
34	Spyros Angelopoulos 0001	Order-Preserving Transformations and Greedy-Like Algorithms.	WAOA	2004	DBLP DOI BibTeX RDF	inapproximability results, facility location, dominating set, Priority algorithms
34	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
34	John H. Reif	Fast Spatial Decomposition and Closest Pair Computation for Limited Precision Input.	Algorithmica	2000	DBLP DOI BibTeX RDF	Visibility problems, Gap-preserving reductions, Telecommunications, Terrains, Inapproximability, Art gallery
31	Venkatesan Guruswami, Rajsekar Manokaran, Prasad Raghavendra	Beating the Random Ordering is Hard: Inapproximability of Maximum Acyclic Subgraph.	FOCS	2008	DBLP DOI BibTeX RDF
31	Jirí Matousek 0001, Anastasios Sidiropoulos	Inapproximability for Metric Embeddings into R^d.	FOCS	2008	DBLP DOI BibTeX RDF
31	Christoph Ambühl, Monaldo Mastrolilli, Ola Svensson	Inapproximability Results for Sparsest Cut, Optimal Linear Arrangement, and Precedence Constrained Scheduling.	FOCS	2007	DBLP DOI BibTeX RDF
31	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
31	Oded Regev 0001	Improved Inapproximability of Lattice and Coding Problems with Preprocessing.	CCC	2003	DBLP DOI BibTeX RDF
31	Thomas Erlebach, Alexander Hall	NP-hardness of broadcast scheduling and inapproximability of single-source unsplittable min-cost flow.	SODA	2002	DBLP BibTeX RDF
31	Stephan J. Eidenbenz	Optimum Inapproximability Results for Finding Minimum Hidden Guard Sets in Polygons and Terrains.	SWAT	2002	DBLP DOI BibTeX RDF
31	Stephan J. Eidenbenz, Christoph Stamm, Peter Widmayer	Inapproximability Results for Guarding Polygons and Terrains.	Algorithmica	2001	DBLP DOI BibTeX RDF
31	Christian Schindelhauer	On the inapproximability of broadcasting time.	APPROX	2000	DBLP DOI BibTeX RDF
31	Christopher Umans	On the Complexity and Inapproximability of Shortest Implicant Problems.	ICALP	1999	DBLP DOI BibTeX RDF
31	Stephan J. Eidenbenz	Inapproximability Results for Guarding Polygons without Holes.	ISAAC	1998	DBLP DOI BibTeX RDF
31	Liming Cai, David W. Juedes, Iyad A. Kanj	The Inapproximability of Non NP-hard Optimization Problems.	ISAAC	1998	DBLP DOI BibTeX RDF
31	Johan Håstad	Some Recent Strong Inapproximability Results.	SWAT	1998	DBLP DOI BibTeX RDF
26	Erik D. Demaine, Mohammad Taghi Hajiaghayi, Hamid Mahini, Amin S. Sayedi-Roshkhar, Shayan Oveis Gharan, Morteza Zadimoghaddam	Minimizing movement.	ACM Trans. Algorithms	2009	DBLP DOI BibTeX RDF	pebble placement, graphs, Motion planning, Euclidean plane
26	Guang Xu, Jinhui Xu 0001	An improved approximation algorithm for uncapacitated facility location problem with penalties.	J. Comb. Optim.	2009	DBLP DOI BibTeX RDF	Algorithms, Approximation algorithms, Outliers, Facility location problem
26	Leonid Khachiyan, Endre Boros, Konrad Borys, Khaled M. Elbassioni, Vladimir Gurvich, Gábor Rudolf, Jihui Zhao	On Short Paths Interdiction Problems: Total and Node-Wise Limited Interdiction.	Theory Comput. Syst.	2008	DBLP DOI BibTeX RDF	Dijkstra’s algorithm, Most vital arcs problem, Cyclic game, Maxmin mean cycle, Minimal vertex cover, Network inhibition, Network interdiction, Approximation algorithm
26	Irit Dinur	The PCP theorem by gap amplification.	J. ACM	2007	DBLP DOI BibTeX RDF	Gap amplification, PCP
26	Michael Elkin, David Peleg	The Hardness of Approximating Spanner Problems.	Theory Comput. Syst.	2007	DBLP DOI BibTeX RDF
26	Erik D. Demaine, Mohammad Taghi Hajiaghayi, Hamid Mahini, Amin S. Sayedi-Roshkhar, Shayan Oveis Gharan, Morteza Zadimoghaddam	Minimizing movement.	SODA	2007	DBLP BibTeX RDF
26	Shmuel Safra, Oded Schwartz	On the complexity of approximating tsp with neighborhoods and related problems.	Comput. Complex.	2006	DBLP DOI BibTeX RDF	68Q25, Subject classification. 68Q17
26	Vitaly Feldman	Hardness of approximate two-level logic minimization and PAC learning with membership queries.	STOC	2006	DBLP DOI BibTeX RDF	DNF minimization, proper learning, two-level logic minimization, hardness of approximation, uniform distribution, membership queries, truth table
26	Zhixiang Chen 0001, Bin Fu, Binhai Zhu	The Approximability of the Exemplar Breakpoint Distance Problem.	AAIM	2006	DBLP DOI BibTeX RDF
26	Sriram V. Pemmaraju, Rajiv Raman 0001	Approximation Algorithms for the Max-coloring Problem.	ICALP	2005	DBLP DOI BibTeX RDF
26	Gregor Gramlich, Georg Schnitger	Minimizing NFA's and Regular Expressions.	STACS	2005	DBLP DOI BibTeX RDF
26	Jérôme Monnot, Vangelis Th. Paschos, Dominique de Werra, Marc Demange, Bruno Escoffier	Weighted Coloring on Planar, Bipartite and Split Graphs: Complexity and Improved Approximation.	ISAAC	2004	DBLP DOI BibTeX RDF
26	Amitai Armon, Yossi Azar, Leah Epstein	Temporary Tasks Assignment Resolved.	Algorithmica	2003	DBLP DOI BibTeX RDF	Unrelated machines, Load balancing, Competitive, On-line, PTAS
26	Miroslav Chlebík, Janka Chlebíková	Approximation Hardness for Small Occurrence Instances of NP-Hard Problems.	CIAC	2003	DBLP DOI BibTeX RDF
26	Erik D. Demaine, Susan Hohenberger, David Liben-Nowell	Tetris is Hard, Even to Approximate.	COCOON	2003	DBLP DOI BibTeX RDF
26	Kasturi R. Varadarajan, Srinivasan Venkatesh 0001, Jiawei Zhang	On Approximating the Radii of Point Sets in High Dimensions.	FOCS	2002	DBLP DOI BibTeX RDF
26	Miroslav Chlebík, Janka Chlebíková	Approximation Hardness of the Steiner Tree Problem on Graphs.	SWAT	2002	DBLP DOI BibTeX RDF
26	Adam R. Klivans	On the Derandomization of Constant Depth Circuits.	RANDOM-APPROX	2001	DBLP DOI BibTeX RDF
26	Johan Håstad	Which NP-Hard Optimization Problems Admit Non-trivial Efficient Approximation Algorithms?	ICALP	2000	DBLP DOI BibTeX RDF
26	Michael Elkin, David Peleg	The Hardness of Approximating Spanner Problems.	STACS	2000	DBLP DOI BibTeX RDF
21	Ola Svensson	Conditional hardness of precedence constrained scheduling on identical machines.	STOC	2010	DBLP DOI BibTeX RDF	scheduling, approximation, inapproximability
21	Dániel Marx	Completely Inapproximable Monotone and Antimonotone Parameterized Problems.	CCC	2010	DBLP DOI BibTeX RDF	parameterized comlexity, approximation, fixed-parameter tractability, inapproximability
21	Jan Arpe, Bodo Manthey	Approximability of Minimum AND-Circuits.	Algorithmica	2009	DBLP DOI BibTeX RDF	Approximation algorithms, Circuit design, Inapproximability
21	Hans-Joachim Böckenhauer, Juraj Hromkovic, Tobias Mömke, Peter Widmayer	On the Hardness of Reoptimization.	SOFSEM	2008	DBLP DOI BibTeX RDF	reoptimization, approximation algorithms, inapproximability
21	Pi-Rong Sheu, Shan-Tai Chen	On the Hardness of Approximating the Multicast Delay Variation Problem.	IEEE Trans. Computers	2007	DBLP DOI BibTeX RDF	inter-destination delay variation, NP-complete, NP-hard, multicast routing, Inapproximability
21	Per Austrin	Balanced max 2-sat might not be the hardest.	STOC	2007	DBLP DOI BibTeX RDF	Max 2-Sat, inapproximability, unique games conjecture
21	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
21	Binwu Zhang, Jianzhong Zhang 0001, Yong He	The Center Location Improvement Problem Under the Hamming Distance.	J. Comb. Optim.	2005	DBLP DOI BibTeX RDF	center location problem, Hamming distance, inapproximability
21	Oleg A. Prokopyev, Panos M. Pardalos	On Approximability of Boolean Formula Minimization.	J. Comb. Optim.	2004	DBLP DOI BibTeX RDF	minimum formula size problem, minimum circuit size problem, combinatorial optimization, approximation, inapproximability, Boolean formulas, Boolean circuits
21	Sanjoy Dasgupta, Wee Sun Lee, Philip M. Long	A Theoretical Analysis of Query Selection for Collaborative Filtering.	Mach. Learn.	2003	DBLP DOI BibTeX RDF	approximation algorithms, recommender systems, collaborative filtering, inapproximability, membership queries
18	Guoliang Qiu 0001, Jiaheng Wang 0002	Inapproximability of counting independent sets in linear hypergraphs.	Inf. Process. Lett.	2024	DBLP DOI BibTeX RDF
18	Karthik C. S., Pasin Manurangsi	On Inapproximability of Reconfiguration Problems: PSPACE-Hardness and some Tight NP-Hardness Results.	Electron. Colloquium Comput. Complex.	2024	DBLP BibTeX RDF
18	Shuichi Hirahara, Naoto Ohsaka	Probabilistically Checkable Reconfiguration Proofs and Inapproximability of Reconfiguration Problems.	Electron. Colloquium Comput. Complex.	2024	DBLP BibTeX RDF
18	Jérémi Do Dinh, Alexandros Hollender	Tight Inapproximability of Nash Equilibria in Public Goods Games.	CoRR	2024	DBLP DOI BibTeX RDF
18	Shuichi Hirahara, Naoto Ohsaka	Probabilistically Checkable Reconfiguration Proofs and Inapproximability of Reconfiguration Problems.	CoRR	2024	DBLP DOI BibTeX RDF
18	Naoto Ohsaka	Tight Inapproximability of Target Set Reconfiguration.	CoRR	2024	DBLP DOI BibTeX RDF
18	Jamie Tucker-Foltz	Inapproximability of Unique Games in Fixed-Point Logic with Counting.	Log. Methods Comput. Sci.	2024	DBLP DOI BibTeX RDF
18	Alexander Meiburg	Inapproximability of Positive Semidefinite Permanents and Quantum State Tomography.	Algorithmica	2023	DBLP DOI BibTeX RDF
18	Pavel Dvorák, Andreas Emil Feldmann, Ashutosh Rai 0001, Pawel Rzazewski	Parameterized Inapproximability of Independent Set in H-Free Graphs.	Algorithmica	2023	DBLP DOI BibTeX RDF
18	Venkatesan Guruswami, Xuandi Ren, Sai Sandeep	Baby PIH: Parameterized Inapproximability of Min CSP.	Electron. Colloquium Comput. Complex.	2023	DBLP BibTeX RDF
18	Venkatesan Guruswami, Bingkai Lin, Xuandi Ren, Yican Sun, Kewen Wu 0001	Parameterized Inapproximability Hypothesis under ETH.	Electron. Colloquium Comput. Complex.	2023	DBLP BibTeX RDF
18	Henry L. Fleischmann, Kyrylo Karlov, Karthik C. S., Ashwin Padaki, Stepan Zharkov	Inapproximability of Maximum Diameter Clustering for Few Clusters.	CoRR	2023	DBLP DOI BibTeX RDF
18	Alexander Kozachinskiy	Inapproximability of sufficient reasons for decision trees.	CoRR	2023	DBLP DOI BibTeX RDF
18	Karthik C. S., Pasin Manurangsi	On Inapproximability of Reconfiguration Problems: PSPACE-Hardness and some Tight NP-Hardness Results.	CoRR	2023	DBLP DOI BibTeX RDF
18	Venkatesan Guruswami, Xuandi Ren, Sai Sandeep	Baby PIH: Parameterized Inapproximability of Min CSP.	CoRR	2023	DBLP DOI BibTeX RDF
18	Venkatesan Guruswami, Bingkai Lin, Xuandi Ren, Yican Sun, Kewen Wu 0001	Parameterized Inapproximability Hypothesis under ETH.	CoRR	2023	DBLP DOI BibTeX RDF
18	Vijay Bhattiprolu, Mrinal Kanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, Madhur Tulsiani	Inapproximability of Matrix p → q Norms.	SIAM J. Comput.	2023	DBLP DOI BibTeX RDF
18	Dongjing Miao, Pengfei Zhang, Jianzhong Li 0001, Ye Wang, Zhipeng Cai 0001	Approximation and inapproximability results on computing optimal repairs.	VLDB J.	2023	DBLP DOI BibTeX RDF
18	Jean Cardinal, Raphael Steiner	Inapproximability of Shortest Paths on Perfect Matching Polytopes.	IPCO	2023	DBLP DOI BibTeX RDF
18	Pasin Manurangsi	Improved Inapproximability of VC Dimension and Littlestone's Dimension via (Unbalanced) Biclique.	ITCS	2023	DBLP DOI BibTeX RDF
18	Argyrios Deligkas, John Fearnley, Alexandros Hollender, Themistoklis Melissourgos	Tight Inapproximability for Graphical Games.	AAAI	2023	DBLP DOI BibTeX RDF
18	Huck Bennett, Mahdi Cheraghchi, Venkatesan Guruswami, João Ribeiro 0002	Parameterized Inapproximability of the Minimum Distance Problem over All Fields and the Shortest Vector Problem in All ℓp Norms.	STOC	2023	DBLP DOI BibTeX RDF
18	Pál András Papp, Georg Anegg, Albert-Jan Nicholas Yzelman	Partitioning Hypergraphs is Hard: Models, Inapproximability, and Applications.	SPAA	2023	DBLP DOI BibTeX RDF
18	Naoto Ohsaka	Some Inapproximability Results of MAP Inference and Exponentiated Determinantal Point Processes.	J. Artif. Intell. Res.	2022	DBLP DOI BibTeX RDF
18	Huck Bennett, Mahdi Cheraghchi, Venkatesan Guruswami, João Ribeiro 0002	Parameterized Inapproximability of the Minimum Distance Problem over all Fields and the Shortest Vector Problem in all ℓp Norms.	Electron. Colloquium Comput. Complex.	2022	DBLP BibTeX RDF
18	Argyrios Deligkas, John Fearnley, Alexandros Hollender, Themistoklis Melissourgos	Pure-Circuit: Strong Inapproximability for PPAD.	CoRR	2022	DBLP DOI BibTeX RDF
18	Guoliang Qiu 0001, Jiaheng Wang	Inapproximability of counting independent sets in linear hypergraphs.	CoRR	2022	DBLP DOI BibTeX RDF
18	Argyrios Deligkas, John Fearnley, Alexandros Hollender, Themistoklis Melissourgos	Constant Inapproximability for PPA.	CoRR	2022	DBLP BibTeX RDF
18	Pál András Papp, Georg Anegg, A. N. Yzelman	Partitioning Hypergraphs is Hard: Models, Inapproximability, and Applications.	CoRR	2022	DBLP DOI BibTeX RDF
18	Argyrios Deligkas, John Fearnley, Alexandros Hollender, Themistoklis Melissourgos	Tight Inapproximability for Graphical Games.	CoRR	2022	DBLP DOI BibTeX RDF
18	Pasin Manurangsi	Improved Inapproximability of VC Dimension and Littlestone's Dimension via (Unbalanced) Biclique.	CoRR	2022	DBLP DOI BibTeX RDF
18	Huck Bennett, Mahdi Cheraghchi, Venkatesan Guruswami, João Ribeiro 0002	Parameterized Inapproximability of the Minimum Distance Problem over all Fields and the Shortest Vector Problem in all p Norms.	CoRR	2022	DBLP DOI BibTeX RDF