Search results for "Inapproximability"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
3	Zhixiang Chen, 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
3	Thomas Erlebach, Alexander Hall	NP-Hardness of Broadcast Scheduling and Inapproximability of Single-Source Unsplittable Min-Cost Flow.	J. Scheduling	2004	DBLP DOI BibTeX RDF	approximation algorithm, NP-complete, inapproximability, resource augmentation, broadcast scheduling
3	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
2	Zhou Xu, 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
2	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
2	Venkatesan Guruswami, Rajsekar Manokaran, Prasad Raghavendra	Beating the Random Ordering is Hard: Inapproximability of Maximum Acyclic Subgraph.	FOCS	2008	DBLP DOI BibTeX RDF
2	Jirí Matousek, Anastasios Sidiropoulos	Inapproximability for Metric Embeddings into R^d.	FOCS	2008	DBLP DOI BibTeX RDF
2	Kord Eickmeyer, Martin Grohe, Magdalena Grüber	Approximation of Natural W[P]-Complete Minimisation Problems Is Hard.	IEEE Conference on Computational Complexity	2008	DBLP DOI BibTeX RDF	derandomisation, parameterized complexity, inapproximability
2	Hermann Gruber, Markus Holzer	Inapproximability of Nondeterministic State and Transition Complexity Assuming P=!NP.	Developments in Language Theory	2007	DBLP DOI BibTeX RDF
2	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
2	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
2	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
2	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
2	Xujin Chen, Xiaodong Hu, 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
2	Subhash Khot	Guest column: inapproximability results via Long Code based PCPs.	SIGACT News	2005	DBLP DOI BibTeX RDF
2	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
2	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
2	Jin-yi Cai, Hong Zhu	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
2	Spyros Angelopoulos	Order-Preserving Transformations and Greedy-Like Algorithms.	WAOA	2004	DBLP DOI BibTeX RDF	inapproximability results, facility location, dominating set, Priority algorithms
2	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
2	Oded Regev	Improved Inapproximability of Lattice and Coding Problems with Preprocessing.	IEEE Conference on Computational Complexity	2003	DBLP DOI BibTeX RDF
2	Thomas Erlebach, Alexander Hall	NP-hardness of broadcast scheduling and inapproximability of single-source unsplittable min-cost flow.	SODA	2002	DBLP DOI BibTeX RDF
2	Stephan Eidenbenz	Optimum Inapproximability Results for Finding Minimum Hidden Guard Sets in Polygons and Terrains.	SWAT	2002	DBLP DOI BibTeX RDF
2	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
2	Stephan Eidenbenz, Christoph Stamm, Peter Widmayer	Inapproximability Results for Guarding Polygons and Terrains.	Algorithmica	2001	DBLP DOI BibTeX RDF
2	Michael Elkin, David Peleg	Strong Inapproximability of the Basic k-Spanner Problem.	ICALP	2000	DBLP DOI BibTeX RDF
2	Christian Schindelhauer	On the inapproximability of broadcasting time.	APPROX	2000	DBLP DOI BibTeX RDF
2	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
2	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
2	Christopher Umans	On the Complexity and Inapproximability of Shortest Implicant Problems.	ICALP	1999	DBLP DOI BibTeX RDF
2	Johan Håstad	Some Recent Strong Inapproximability Results.	SWAT	1998	DBLP DOI BibTeX RDF
2	Liming Cai, David W. Juedes, Iyad A. Kanj	The Inapproximability of Non NP-hard Optimization Problems.	ISAAC	1998	DBLP DOI BibTeX RDF
2	Stephan Eidenbenz	Inapproximability Results for Guarding Polygons without Holes.	ISAAC	1998	DBLP DOI BibTeX RDF
2	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
1	Daniele Micciancio	Inapproximability of the Shortest Vector Problem: Toward a Deterministic Reduction.	Electronic Colloquium on Computational Complexity (ECCC)	2012	DBLP BibTeX RDF
1	Andreas Galanis, Daniel Stefankovic, Eric Vigoda	Inapproximability of the Partition Function for the Antiferromagnetic Ising and Hard-Core Models	CoRR	2012	DBLP BibTeX RDF
1	Venkatesan Guruswami, Prasad Raghavendra, Rishi Saket, Yi Wu	Bypassing UGC from some optimal geometric inapproximability results.	SODA	2012	DBLP BibTeX RDF
1	Ravishankar Krishnaswamy, Maxim Sviridenko	Inapproximability of the multi-level uncapacitated facility location problem.	SODA	2012	DBLP BibTeX RDF
1	Trung Thanh Nguyen 0004, Magnus Roos, Jörg Rothe	A Survey of Approximability and Inapproximability Results for Social Welfare Optimization in Multiagent Resource Allocation.	ISAIM	2012	DBLP BibTeX RDF
1	Laurent Bulteau, Minghui Jiang	Inapproximability of (1, 2)-Exemplar Distance.	ISBRA	2012	DBLP DOI BibTeX RDF
1	Chunmei Liu, Yinglei Song	Parameterized complexity and inapproximability of dominating set problem in chordal and near chordal graphs.	J. Comb. Optim.	2011	DBLP DOI BibTeX RDF
1	Minghui Jiang	Inapproximability of maximal strip recovery.	Theor. Comput. Sci.	2011	DBLP DOI BibTeX RDF
1	Christina Büsing, Sebastian Stiller	Line planning, path constrained network flow and inapproximability.	Networks	2011	DBLP DOI BibTeX RDF
1	Per Austrin, Subhash Khot, Muli Safra	Inapproximability of Vertex Cover and Independent Set in Bounded Degree Graphs.	Theory of Computing	2011	DBLP DOI BibTeX RDF
1	Marwane Bouznif, Rodolphe Giroudeau	Inapproximability and Polynomial-Time Approximation Algorithm for UET Tasks on Structured Processor Networks.	Adv. Operations Research	2011	DBLP DOI BibTeX RDF
1	Andreas Galanis, Qi Ge, Daniel Stefankovic, Eric Vigoda, Linji Yang	Improved Inapproximability Results for Counting Independent Sets in the Hard-Core Model	CoRR	2011	DBLP BibTeX RDF
1	Per Austrin, Toniann Pitassi, Yu Wu	Inapproximability of Treewidth, One-Shot Pebbling, and Related Layout Problems	CoRR	2011	DBLP BibTeX RDF
1	Per Austrin, Mark Braverman, Eden Chlamtac	Inapproximability of NP-Complete Variants of Nash Equilibrium	CoRR	2011	DBLP BibTeX RDF
1	Christoph Ambühl, Monaldo Mastrolilli, Ola Svensson	Inapproximability Results for Maximum Edge Biclique, Minimum Linear Arrangement, and Sparsest Cut.	SIAM J. Comput.	2011	DBLP DOI BibTeX RDF
1	Oded Goldreich	Using the FGLSS-Reduction to Prove Inapproximability Results for Minimum Vertex Cover in Hypergraphs.	Studies in Complexity and Cryptography	2011	DBLP DOI BibTeX RDF
1	Mourad El Ouali, Antje Fretwurst, Anand Srivastav	Inapproximability of b-Matching in k-Uniform Hypergraphs.	WALCOM	2011	DBLP DOI BibTeX RDF
1	Andreas Galanis, Qi Ge, Daniel Stefankovic, Eric Vigoda, Linji Yang	Improved Inapproximability Results for Counting Independent Sets in the Hard-Core Model.	APPROX-RANDOM	2011	DBLP DOI BibTeX RDF
1	Per Austrin, Mark Braverman, Eden Chlamtac	Inapproximability of NP-Complete Variants of Nash Equilibrium.	APPROX-RANDOM	2011	DBLP DOI BibTeX RDF
1	Yuichi Yoshida	Optimal constant-time approximation algorithms and (unconditional) inapproximability results for every bounded-degree CSP.	STOC	2011	DBLP DOI BibTeX RDF
1	Keqin Li	Inapproximability Results for Wavelength Assignment in WDM Optical Networks.	Informatica, Lith. Acad. Sci.	2010	DBLP BibTeX RDF
1	Varun Gupta, Mor Harchol-Balter, J. G. Dai, Bert Zwart	On the inapproximability of M/G/K: why two moments of job size distribution are not enough.	Queueing Syst.	2010	DBLP DOI BibTeX RDF
1	Venkatesan Guruswami, Prasad Raghavendra, Rishi Saket, Yi Wu	Bypassing UGC from some optimal geometric inapproximability results.	Electronic Colloquium on Computational Complexity (ECCC)	2010	DBLP BibTeX RDF
1	Yuichi Yoshida	Optimal Constant-Time Approximation Algorithms and (Unconditional) Inapproximability Results for Every Bounded-Degree CSP.	Electronic Colloquium on Computational Complexity (ECCC)	2010	DBLP BibTeX RDF
1	Tomoko Izumi, Taisuke Izumi, Hirotaka Ono, Koichi Wada	Approximability and inapproximability of the minimum certificate dispersal problem.	Theor. Comput. Sci.	2010	DBLP DOI BibTeX RDF
1	Wenbin Chen 0002, Dengpan Yin, Zhengzhang Chen	Inapproximability results for equations over infinite groups.	Theor. Comput. Sci.	2010	DBLP DOI BibTeX RDF
1	Hideaki Otsuki, Tomio Hirata	Inapproximability of the Minimum Biclique Edge Partition Problem.	IEICE Transactions	2010	DBLP BibTeX RDF
1	Matthew Andrews, Julia Chuzhoy, Venkatesan Guruswami, Sanjeev Khanna, Kunal Talwar, Lisa Zhang	Inapproximability of Edge-Disjoint Paths and low congestion routing on undirected graphs.	Combinatorica	2010	DBLP DOI BibTeX RDF
1	Per Austrin	Improved Inapproximability For Submodular Maximization	CoRR	2010	DBLP BibTeX RDF
1	Ali Çivril, Malik Magdon-Ismail	Exponential Inapproximability of Selecting a Maximum Volume Sub-matrix	CoRR	2010	DBLP BibTeX RDF
1	Yuichi Yoshida	Optimal Constant-Time Approximation Algorithms and (Unconditional) Inapproximability Results for Every Bounded-Degree CSP	CoRR	2010	DBLP BibTeX RDF
1	Per Austrin	Towards Sharp Inapproximability for Any 2-CSP.	SIAM J. Comput.	2010	DBLP DOI BibTeX RDF
1	Minghui Jiang	Inapproximability of Maximal Strip Recovery: II.	FAW	2010	DBLP DOI BibTeX RDF
1	David Buchfuhrer, Shaddin Dughmi, Hu Fu, Robert Kleinberg, Elchanan Mossel, Christos H. Papadimitriou, Michael Schapira, Yaron Singer, Christopher Umans	Inapproximability for VCG-Based Combinatorial Auctions.	SODA	2010	DBLP BibTeX RDF
1	Jeff Edmonds, Anastasios Sidiropoulos, Anastasios Zouzias	Inapproximability for Planar Embedding Problems.	SODA	2010	DBLP BibTeX RDF
1	Venkatesan Guruswami, Rishi Saket	On the Inapproximability of Vertex Cover on k-Partite k-Uniform Hypergraphs.	ICALP	2010	DBLP DOI BibTeX RDF
1	Nikhil Bansal, Subhash Khot	Inapproximability of Hypergraph Vertex Cover and Applications to Scheduling Problems.	ICALP	2010	DBLP DOI BibTeX RDF
1	Yilin Shen, Dung T. Nguyen, My T. Thai	On the Hardness and Inapproximability of Optimization Problems on Power Law Graphs.	COCOA	2010	DBLP DOI BibTeX RDF
1	Per Austrin	Improved Inapproximability for Submodular Maximization.	APPROX-RANDOM	2010	DBLP DOI BibTeX RDF
1	Ola Svensson	Conditional hardness of precedence constrained scheduling on identical machines.	STOC	2010	DBLP DOI BibTeX RDF	scheduling, approximation, inapproximability
1	Dániel Marx	Completely Inapproximable Monotone and Antimonotone Parameterized Problems.	IEEE Conference on Computational Complexity	2010	DBLP DOI BibTeX RDF	parameterized comlexity, approximation, fixed-parameter tractability, inapproximability
1	Venkatesan Guruswami, Ali Kemal Sinop	Improved Inapproximability Results for Maximum k-Colorable Subgraph.	Electronic Colloquium on Computational Complexity (ECCC)	2009	DBLP BibTeX RDF
1	Kevin Dick, Christopher Umans	Improved inapproximability factors for some Sigma2p minimization problems.	Electronic Colloquium on Computational Complexity (ECCC)	2009	DBLP BibTeX RDF
1	Yury L. Orlovich, Valery S. Gordon, Dominique de Werra	On the inapproximability of independent domination in 2P3-free perfect graphs.	Theor. Comput. Sci.	2009	DBLP DOI BibTeX RDF
1	Bin Fu, Yumei Huo, Hairong Zhao	Exponential inapproximability and FPTAS for scheduling with availability constraints.	Theor. Comput. Sci.	2009	DBLP DOI BibTeX RDF
1	Yuval Lando, Zeev Nutov	Inapproximability of survivable networks.	Theor. Comput. Sci.	2009	DBLP DOI BibTeX RDF
1	Leslie Ann Goldberg, Mark Jerrum	Inapproximability of the Tutte polynomial of a planar graph	CoRR	2009	DBLP BibTeX RDF
1	Elchanan Mossel, Christos H. Papadimitriou, Michael Schapira, Yaron Singer	VC v. VCG: Inapproximability of Combinatorial Auctions via Generalizations of the VC Dimension	CoRR	2009	DBLP BibTeX RDF
1	Minghui Jiang	Inapproximability of maximal strip recovery	CoRR	2009	DBLP BibTeX RDF
1	Venkatesan Guruswami, Ali Kemal Sinop	Improved Inapproximability Results for Maximum k-Colorable Subgraph	CoRR	2009	DBLP BibTeX RDF
1	Evangelos Kranakis, Danny Krizanc, Lata Narayanan, Kun Xu	Inapproximability of the Perimeter Defense Problem.	CCCG	2009	DBLP BibTeX RDF
1	Venkatesan Guruswami, Ali Kemal Sinop	Improved Inapproximability Results for Maximum k-Colorable Subgraph.	APPROX-RANDOM	2009	DBLP DOI BibTeX RDF
1	Minghui Jiang	Inapproximability of Maximal Strip Recovery.	ISAAC	2009	DBLP DOI BibTeX RDF
1	Per Austrin, Subhash Khot, Muli Safra	Inapproximability of Vertex Cover and Independent Set in Bounded Degree Graphs.	IEEE Conference on Computational Complexity	2009	DBLP DOI BibTeX RDF
1	Jan Arpe, Bodo Manthey	Approximability of Minimum AND-Circuits.	Algorithmica	2009	DBLP DOI BibTeX RDF	Approximation algorithms, Circuit design, Inapproximability
1	Arnab Bhattacharyya, Elena Grigorescu, Kyomin Jung, Sofya Raskhodnikova, David P. Woodruff	Transitive-closure spanners.	SODA	2009	DBLP DOI BibTeX RDF
1	Ioannis Caragiannis, Jason A. Covey, Michal Feldman, Christopher M. Homan, Christos Kaklamanis, Nikos Karanikolas, Ariel D. Procaccia, Jeffrey S. Rosenschein	On the approximability of Dodgson and Young elections.	SODA	2009	DBLP DOI BibTeX RDF
1	Florian Diedrich, Klaus Jansen	Improved approximation algorithms for scheduling with fixed jobs.	SODA	2009	DBLP DOI BibTeX RDF
1	Khaled M. Elbassioni, Rajiv Raman, Saurabh Ray, René Sitters	On the approximability of the maximum feasible subsystem problem with 0/1-coefficients.	SODA	2009	DBLP DOI BibTeX RDF
1	Ryan O'Donnell, Yi Wu	3-bit dictator testing: 1 vs. 5/8.	SODA	2009	DBLP DOI BibTeX RDF
1	Michele Flammini, Alberto Marchetti-Spaccamela, Gianpiero Monaco, Luca Moscardelli, Shmuel Zaks	On the complexity of the regenerator placement problem in optical networks.	SPAA	2009	DBLP DOI BibTeX RDF	approximation algorithms, complexity, optical networks, wavelength division multiplexing (wdm), regenerators
1	Ryan O'Donnell, Yi Wu	Conditional hardness for satisfiable 3-CSPs.	STOC	2009	DBLP DOI BibTeX RDF	khot's, satisfiable 3-CSPs, hardness of approximation, PCP
1	Erik D. Demaine, Mohammad Taghi Hajiaghayi, Hamid Mahini, Amin S. Sayedi-Roshkhar, Shayan Oveis Gharan, Morteza Zadimoghaddam	Minimizing movement.	ACM Transactions on Algorithms	2009	DBLP DOI BibTeX RDF	pebble placement, graphs, Motion planning, Euclidean plane
1	Erik Saule, Denis Trystram	Multi-users scheduling in parallel systems.	IPDPS	2009	DBLP DOI BibTeX RDF
1	Tim Nonner, Alexander Souza	A 5/3-Approximation Algorithm for Joint Replenishment with Deadlines.	COCOA	2009	DBLP DOI BibTeX RDF
1	Florian Diedrich, Klaus Jansen, Ulrich M. Schwarz, Denis Trystram	A Survey on Approximation Algorithms for Scheduling with Machine Unavailability.	Algorithmics of Large and Complex Networks	2009	DBLP DOI BibTeX RDF