Search results for "Hardness of approximation"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
2	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
2	Julia Chuzhoy, Sanjeev Khanna	Polynomial flow-cut gaps and hardness of directed cut problems.	J. ACM	2009	DBLP DOI BibTeX RDF	Directed multicut, hardness of approximation, sparsest cut
2	Julia Chuzhoy, Sanjeev Khanna	Polynomial flow-cut gaps and hardness of directed cut problems.	STOC	2007	DBLP DOI BibTeX RDF	concurrent flow, directed multicut, directed sparsest cut, flow-cut gaps, hardness of approximation, multicommodity flow
2	Ashkan Aazami, Michael D. Stilp	Approximation Algorithms and Hardness for Domination with Propagation.	APPROX-RANDOM	2007	DBLP DOI BibTeX RDF	Power Dominating Set, Approximation Algorithms, Integer Programming, Planar Graphs, Greedy Algorithms, Dominating Set, Hardness of Approximation, PTAS
2	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
2	Patricia A. Evans, Andrew D. Smith	Complexity of Approximating Closest Substring Problems.	FCT	2003	DBLP DOI BibTeX RDF	Closest Substring, Approximation algorithms, Hardness of approximation
2	Guy Kortsarz, Robert Krauthgamer, James R. Lee	Hardness of Approximation for Vertex-Connectivity Network-Design Problems.	APPROX	2002	DBLP DOI BibTeX RDF
2	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
1	Leslie Ann Goldberg, Mark Jerrum	The Complexity of Computing the Sign of the Tutte Polynomial (and consequent #P-hardness of Approximation)	CoRR	2012	DBLP BibTeX RDF
1	Sergio Cabello	Hardness of approximation for crossing number	CoRR	2012	DBLP BibTeX RDF
1	A. Karim Abu-Affash	On the euclidean bottleneck full Steiner tree problem.	Symposium on Computational Geometry	2011	DBLP DOI BibTeX RDF
1	Patrick Briest, Parinya Chalermsook, Sanjeev Khanna, Bundit Laekhanukit, Danupon Nanongkai	Improved Hardness of Approximation for Stackelberg Shortest-Path Pricing.	WINE	2010	DBLP DOI BibTeX RDF
1	Patrick Briest, Sanjeev Khanna	Improved Hardness of Approximation for Stackelberg Shortest-Path Pricing	CoRR	2009	DBLP BibTeX RDF
1	Shaddin Dughmi, Hu Fu, Robert Kleinberg	Amplified Hardness of Approximation for VCG-Based Mechanisms	CoRR	2009	DBLP BibTeX RDF
1	Miroslav Chlebík, Janka Chlebíková	Hardness of approximation for orthogonal rectangle packing and covering problems.	J. Discrete Algorithms	2009	DBLP DOI BibTeX RDF
1	Eyal Kushilevitz, Enav Weinreb	On the complexity of communication complexity.	STOC	2009	DBLP DOI BibTeX RDF	protocol tree, lower bounds, communication complexity, hardness of approximation, pseudo random functions
1	Matthew Andrews, Lisa Zhang	Complexity of wavelength assignment in optical network optimization.	IEEE/ACM Trans. Netw.	2009	DBLP DOI BibTeX RDF	approximation algorithms, optical networking, hardness of approximation, routing and wavelength assignment
1	Shankar Kalyanaraman, Christopher Umans	The Complexity of Rationalizing Network Formation.	FOCS	2009	DBLP DOI BibTeX RDF	network formation games, Jackson-Wolinsky model, Inequality-SAT, hardness of approximation
1	Prasad Raghavendra, David Steurer	Integrality Gaps for Strong SDP Relaxations of UNIQUE GAMES.	FOCS	2009	DBLP DOI BibTeX RDF	SDP hierarchies, Sherali-Adams hierarchy, integrality gap construction, approximation algorithms, semidefinite programming, hardness of approximation, unique games conjecture
1	Guy Kortsarz, Zeev Nutov	Approximating Some Network Design Problems with Node Costs.	APPROX-RANDOM	2009	DBLP DOI BibTeX RDF	Node costs, Multicommodity Buy at Bulk, Covering tree, Approximation algorithm, Network design, Hardness of approximation
1	Ryan O'Donnell, Yi Wu	3-bit dictator testing: 1 vs. 5/8.	SODA	2009	DBLP DOI BibTeX RDF
1	Guohua Jin, Luay Nakhleh, Sagi Snir, Tamir Tuller	Parsimony Score of Phylogenetic Networks: Hardness Results and a Linear-Time Heuristic.	IEEE/ACM Trans. Comput. Biology Bioinform.	2009	DBLP DOI BibTeX RDF	hardness and approximation, phylogenetic networks, Maximum parsimony, horizontal gene transfer
1	Andreas Karrenbauer	Matching Techniques Ride to Rescue OLED Displays.	COCOA	2009	DBLP DOI BibTeX RDF
1	Inge Li Gørtz, Viswanath Nagarajan, R. Ravi	Minimum Makespan Multi-vehicle Dial-a-Ride.	ESA	2009	DBLP DOI BibTeX RDF
1	Lasse Kliemann, Anand Srivastav	Experimental Study of Non-oblivious Greedy and Randomized Rounding Algorithms for Hypergraph b-Matching.	SEA	2009	DBLP DOI BibTeX RDF	hypergraph matching, approximation algorithms, greedy algorithms, hybrid algorithms, NP-hard problems, randomized rounding
1	Christopher Ré, Dan Suciu	The trichotomy of HAVING queries on a probabilistic database.	VLDB J.	2009	DBLP DOI BibTeX RDF	Safe plans, Probabilistic databases, Query evaluation, Semirings, Sampling algorithms
1	Tianyan Deng, Daoyun Xu	Hardness of Approximation Algorithms on k-SAT and (k, s)-SAT Problems.	ICYCS	2008	DBLP DOI BibTeX RDF
1	Tanmoy Chakraborty, Julia Chuzhoy, Sanjeev Khanna	Network design for vertex connectivity.	STOC	2008	DBLP DOI BibTeX RDF	approximation algorithms, network design, hardness of approximation, vertex connectivity
1	Ryan O'Donnell, Yi Wu	An optimal sdp algorithm for max-cut, and equally optimal long code tests.	STOC	2008	DBLP DOI BibTeX RDF	semidefinite programming, hardness of approximation, max-cut
1	Matthew Andrews, Lisa Zhang	Almost-tight hardness of directed congestion minimization.	J. ACM	2008	DBLP DOI BibTeX RDF	Hardness of approximation, undirected graphs, congestion minimization
1	Julia Chuzhoy, Anupam Gupta, Joseph Naor, Amitabh Sinha	On the approximability of some network design problems.	ACM Transactions on Algorithms	2008	DBLP DOI BibTeX RDF	cost-distance, fixed charge network flow, priority Steiner tree, network design, Hardness of approximation
1	Omid Amini, David Peleg, Stéphane Pérennes, Ignasi Sau, Saket Saurabh	Degree-Constrained Subgraph Problems: Hardness and Approximation Results.	WAOA	2008	DBLP DOI BibTeX RDF	Degree-Constrained Subgraphs, Apx, Excluded Minor, Approximation Algorithms, Hardness of Approximation, PTAS
1	Jean Cardinal, Samuel Fiorini, Gwenaël Joret	Tight Results on Minimum Entropy Set Cover.	Algorithmica	2008	DBLP DOI BibTeX RDF	Entropy, Greedy algorithm, Hardness of approximation, Set cover
1	Subhash Khot, Richard J. Lipton, Evangelos Markakis, Aranyak Mehta	Inapproximability Results for Combinatorial Auctions with Submodular Utility Functions.	Algorithmica	2008	DBLP DOI BibTeX RDF	Combinatorial auctions, Hardness of approximation, Social welfare, Submodular
1	Ning Chen	On the approximability of influence in social networks.	SODA	2008	DBLP DOI BibTeX RDF
1	Anup Rao	Parallel repetition in projection games and a concentration bound.	STOC	2008	DBLP DOI BibTeX RDF	chsh game, parallel repetition, unique games conjecture
1	Julia Kempe, Hirotada Kobayashi, Keiji Matsumoto, Ben Toner, Thomas Vidick	Entangled Games are Hard to Approximate.	FOCS	2008	DBLP DOI BibTeX RDF
1	Dana Moshkovitz, Ran Raz	Two Query PCP with Sub-Constant Error.	FOCS	2008	DBLP DOI BibTeX RDF
1	Moshe Laifenfeld, Ari Trachtenberg	Identifying Codes and Covering Problems.	IEEE Transactions on Information Theory	2008	DBLP DOI BibTeX RDF
1	Guy Kortsarz, Michael Langberg, Zeev Nutov	Approximating Maximum Subgraphs without Short Cycles.	APPROX-RANDOM	2008	DBLP DOI BibTeX RDF
1	Yuval Lando, Zeev Nutov	Inapproximability of Survivable Networks.	APPROX-RANDOM	2008	DBLP DOI BibTeX RDF
1	Basile Couëtoux, Laurent Gourvès, Jérôme Monnot, Orestis Telelis	On Labeled Traveling Salesman Problems.	ISAAC	2008	DBLP DOI BibTeX RDF
1	Ning Chen, Atri Rudra	Walrasian Equilibrium: Hardness, Approximations and Tractable Instances.	Algorithmica	2008	DBLP DOI BibTeX RDF	Walrasian equilibrium, Single-minded auction, Approximation, NP-hard, Combinatorial auction
1	Benny Applebaum, Yuval Ishai, Eyal Kushilevitz	On Pseudorandom Generators with Linear Stretch in NC0.	Computational Complexity	2008	DBLP DOI BibTeX RDF	Subject classification. 94A60, 68P25
1	Julia Chuzhoy, Venkatesan Guruswami, Sanjeev Khanna, Kunal Talwar	Hardness of routing with congestion in directed graphs.	STOC	2007	DBLP DOI BibTeX RDF	all-or-nothing flow, hardness of approximation, multicommodity flow, edge-disjoint paths, integrality gap, congestion minimization
1	Venkatesan Guruswami, Prasad Raghavendra	A 3-query PCP over integers.	STOC	2007	DBLP DOI BibTeX RDF	sparse linear equations, hardness of approximation, probabilistically checkable proofs, linearity testing
1	Ishay Haviv, Oded Regev	Tensor-based hardness of the shortest vector problem to within almost polynomial factors.	STOC	2007	DBLP DOI BibTeX RDF	lattices, hardness of approximation, tensor product
1	Joseph Cheriyan, Mohammad R. Salavatipour	Packing element-disjoint steiner trees.	ACM Transactions on Algorithms	2007	DBLP DOI BibTeX RDF	element-disjoint, approximation algorithms, Steiner trees, hardness of approximation, Packing
1	Michael Krivelevich, Zeev Nutov, Mohammad R. Salavatipour, Jacques Yuster, Raphael Yuster	Approximation algorithms and hardness results for cycle packing problems.	ACM Transactions on Algorithms	2007	DBLP DOI BibTeX RDF	Cycle packing, edge-disjoint, approximation algorithms, hardness of approximation, integrality gap
1	Refael Hassin, Jérôme Monnot, Danny Segev	Approximation algorithms and hardness results for labeled connectivity problems.	J. Comb. Optim.	2007	DBLP DOI BibTeX RDF	Labeled connectivity, Approximation algorithms, Hardness of approximation
1	Erik D. Demaine, Mohammad Ghodsi, Mohammad Taghi Hajiaghayi, Amin S. Sayedi-Roshkhar, Morteza Zadimoghaddam	Scheduling to minimize gaps and power consumption.	SPAA	2007	DBLP DOI BibTeX RDF	sleep state, multiprocessor scheduling, power minimization
1	Chandra Chekuri, Sanjeev Khanna	Edge-disjoint paths revisited.	ACM Transactions on Algorithms	2007	DBLP DOI BibTeX RDF	multicommodity flow relaxation, approximation algorithm, greedy algorithm, Edge-disjoint paths
1	Parikshit Gopalan, Subhash Khot, Rishi Saket	Hardness of Reconstructing Multivariate Polynomials over Finite Fields.	FOCS	2007	DBLP DOI BibTeX RDF
1	Jonathan A. Kelner, Evdokia Nikolova	On the Hardness and Smoothed Complexity of Quasi-Concave Minimization.	FOCS	2007	DBLP DOI BibTeX RDF
1	Ning Chen, Roee Engelberg, C. Thach Nguyen, Prasad Raghavendra, Atri Rudra, Gyanit Singh	Improved Approximation Algorithms for the Spanning Star Forest Problem.	APPROX-RANDOM	2007	DBLP DOI BibTeX RDF
1	Guohua Jin, Luay Nakhleh, Sagi Snir, Tamir Tuller	A New Linear-Time Heuristic Algorithm for Computing the Parsimony Score of Phylogenetic Networks: Theoretical Bounds and Empirical Performance.	ISBRA	2007	DBLP DOI BibTeX RDF
1	Faisal N. Abu-Khzam, Mohamad A. Rizk, Deema A. Abdallah, Nagiza F. Samatova	The Buffered Work-Pool Approach for Search-Tree Based Optimization Algorithms.	PPAM	2007	DBLP DOI BibTeX RDF
1	Luca Di Gaspero, Johannes Gärtner, Guy Kortsarz, Nysret Musliu, Andrea Schaerf, Wolfgang Slany	The minimum shift design problem.	Annals OR	2007	DBLP DOI BibTeX RDF	Workforce scheduling, Local search, Hybrid algorithms, Greedy heuristics
1	Ananth I. Sundararaj, Manan Sanghi, John R. Lange, Peter A. Dinda	Hardness of Approximation and Greedy Algorithms for the Adaptation Problem in Virtual Environments.	ICAC	2006	DBLP BibTeX RDF
1	K. Murali Krishnan, L. Sunil Chandran	Hardness of Approximation Results for the Problem of Finding the Stopping Distance in Tanner Graphs.	FSTTCS	2006	DBLP DOI BibTeX RDF
1	Matthew Andrews, Lisa Zhang	Logarithmic hardness of the directed congestion minimization problem.	STOC	2006	DBLP DOI BibTeX RDF	directed graphs, hardness of approximation, congestion minimization
1	Julia Chuzhoy, Sanjeev Khanna	Hardness of cut problems in directed graphs.	STOC	2006	DBLP DOI BibTeX RDF	directed multicut, hardness of approximation, sparsest cut
1	Irit Dinur, Elchanan Mossel, Oded Regev	Conditional hardness for approximate coloring.	STOC	2006	DBLP DOI BibTeX RDF	graph coloring, hardness of approximation, unique games conjecture
1	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
1	Oded Regev, Ricky Rosen	Lattice problems and norm embeddings.	STOC	2006	DBLP DOI BibTeX RDF	embedding, lattices, norms, hardness of approximation
1	Matthew Andrews, Lisa Zhang	Logarithmic hardness of the undirected edge-disjoint paths problem.	J. ACM	2006	DBLP DOI BibTeX RDF	Hardness of approximation, undirected graphs, edge-disjoint paths
1	Julia Chuzhoy, Joseph Naor	New hardness results for congestion minimization and machine scheduling.	J. ACM	2006	DBLP DOI BibTeX RDF	resource minimization, scheduling, network routing, Hardness of approximation, congestion minimization
1	Zeev Nutov	Approximating Rooted Connectivity Augmentation Problems.	Algorithmica	2006	DBLP DOI BibTeX RDF	Rooted connectivity, Augmentation problems, Approximation algorithms, Hardness of approximation
1	Irit Dinur, Ehud Friedgut, Guy Kindler, Ryan O'Donnell	On the fourier tails of bounded functions over the discrete cube.	STOC	2006	DBLP DOI BibTeX RDF	boolean functions, Fourier analysis, symmetry-breaking
1	Benny Applebaum, Yuval Ishai, Eyal Kushilevitz	On Pseudorandom Generators with Linear Stretch in NC0.	APPROX-RANDOM	2006	DBLP DOI BibTeX RDF
1	Subhash Khot, Ashok Kumar Ponnuswami	Better Inapproximability Results for MaxClique, Chromatic Number and Min-3Lin-Deletion.	ICALP	2006	DBLP DOI BibTeX RDF
1	David Abraham, Ning Chen, Vijay Kumar, Vahab S. Mirrokni	Assignment Problems in Rental Markets.	WINE	2006	DBLP DOI BibTeX RDF
1	Esther M. Arkin, Michael A. Bender, Sándor P. Fekete, Joseph S. B. Mitchell, Martin Skutella	The Freeze-Tag Problem: How to Wake Up a Swarm ofRobots.	Algorithmica	2006	DBLP DOI BibTeX RDF
1	Elad Hazan, Shmuel Safra, Oded Schwartz	On the complexity of approximating k-set packing.	Computational Complexity	2006	DBLP DOI BibTeX RDF	68Q17, Subject classification
1	Matthew Andrews, Lisa Zhang	Hardness of the undirected congestion minimization problem.	STOC	2005	DBLP DOI BibTeX RDF	hardness of approximation, undirected graphs, congestion minimization
1	Matthew Andrews, Lisa Zhang	Hardness of the undirected edge-disjoint paths problem.	STOC	2005	DBLP DOI BibTeX RDF	hardness of approximation, undirected graphs, edge-disjoint paths
1	Julia Chuzhoy, Sudipto Guha, Eran Halperin, Sanjeev Khanna, Guy Kortsarz, Robert Krauthgamer, Joseph Naor	Asymmetric k-center is log* n-hard to approximate.	J. ACM	2005	DBLP DOI BibTeX RDF	asymmetric k-center, metric k-center, Approximation algorithms, hardness of approximation
1	Subhash Khot	Hardness of approximating the shortest vector problem in lattices.	J. ACM	2005	DBLP DOI BibTeX RDF	Approximation algorithms, cryptography, lattices, hardness of approximation, shortest vector problem
1	Joseph Cheriyan, Adrian Vetta	Approximation algorithms for network design with metric costs.	STOC	2005	DBLP DOI BibTeX RDF	metric costs, approximation algorithms, graph connectivity
1	Noga Alon, Asaf Shapira, Benny Sudakov	Additive Approximation for Edge-Deletion Problems.	FOCS	2005	DBLP DOI BibTeX RDF
1	Matthew Andrews, Julia Chuzhoy, Sanjeev Khanna, Lisa Zhang	Hardness of the Undirected Edge-Disjoint Paths Problem with Congestion.	FOCS	2005	DBLP DOI BibTeX RDF
1	Subhash Khot	On the Unique Games Conjecture.	FOCS	2005	DBLP DOI BibTeX RDF
1	Jiangzhuo Chen, Lujun Jia, Xin Liu, Guevara Noubir, Ravi Sundaram	Minimum energy accumulative routing in wireless networks.	INFOCOM	2005	DBLP DOI BibTeX RDF
1	Viswanath Nagarajan, R. Ravi	Approximation Algorithms for Requirement Cut on Graphs.	APPROX-RANDOM	2005	DBLP DOI BibTeX RDF
1	Vincent Berry, Sylvain Guillemot, François Nicolas, Christophe Paul	On the Approximation of Computing Evolutionary Trees.	COCOON	2005	DBLP DOI BibTeX RDF
1	Lars Engebretsen, Jonas Holmerin	More Efficient Queries in PCPs for NP and Improved Approximation Hardness of Maximum CSP.	STACS	2005	DBLP DOI BibTeX RDF
1	Georg Baier, Ekkehard Köhler, Martin Skutella	The k-Splittable Flow Problem.	Algorithmica	2005	DBLP DOI BibTeX RDF	Max-flow min-cut, Approximation algorithm, Network flow, Unsplittable flow
1	Venkatesan Guruswami, Daniele Micciancio, Oded Regev	The complexity of the covering radius problem.	Computational Complexity	2005	DBLP DOI BibTeX RDF	11H06, 11H31, 68Q25, 94B05, Subject classification. 68Q17
1	Adi Avidor, Uri Zwick	Approximating MIN 2-SAT and MIN 3-SAT.	Theory Comput. Syst.	2005	DBLP DOI BibTeX RDF
1	Guy Kortsarz, Robert Krauthgamer, James R. Lee	Hardness of Approximation for Vertex-Connectivity Network Design Problems.	SIAM J. Comput.	2004	DBLP DOI BibTeX RDF
1	Julia Chuzhoy, Sudipto Guha, Eran Halperin, Sanjeev Khanna, Guy Kortsarz, Joseph Naor	Asymmetric k-center is log* n-hard to approximate.	STOC	2004	DBLP DOI BibTeX RDF	asymmetric k-center, metric k-center, approximation algorithms, hardness of approximation
1	Julia Chuzhoy, Joseph Naor	New hardness results for congestion minimization and machine scheduling.	STOC	2004	DBLP DOI BibTeX RDF	routing, approximation algorithms, hardness of approximation, machine scheduling, congestion minimization
1	Michael Elkin	Unconditional lower bounds on the time-approximation tradeoffs for the distributed minimum spanning tree problem.	STOC	2004	DBLP DOI BibTeX RDF	minimum spanning tree, hardness of approximation
1	Jonas Holmerin, Subhash Khot	A new PCP outer verifier with applications to homogeneous linear equations and max-bisection.	STOC	2004	DBLP DOI BibTeX RDF	max-bisection, hardness of approximation, linear equations, PCPs
1	Venkatesan Guruswami, Daniele Micciancio, Oded Regev	The Complexity of the Covering Radius Problem on Lattices and Codes.	IEEE Conference on Computational Complexity	2004	DBLP DOI BibTeX RDF
1	Uriel Feige, Daniel Reichman	On Systems of Linear Equations with Two Variables per Equation.	APPROX-RANDOM	2004	DBLP DOI BibTeX RDF
1	Joseph Cheriyan, Mohammad R. Salavatipour	Hardness and Approximation Results for Packing Steiner Trees.	ESA	2004	DBLP DOI BibTeX RDF
1	Irit Dinur, Venkatesan Guruswami, Subhash Khot, Oded Regev	A new multilayered PCP and the hardness of hypergraph vertex cover.	STOC	2003	DBLP DOI BibTeX RDF	hypergraph vertex cover, long code, multilayered PCP, hardness of approximation
1	Eran Halperin, Robert Krauthgamer	Polylogarithmic inapproximability.	STOC	2003	DBLP DOI BibTeX RDF	integrality ratio, polylogarithmic approximation, approximation algorithms, Steiner tree, hardness of approximation
1	Chandra Chekuri, Sanjeev Khanna	Edge disjoint paths revisited.	SODA	2003	DBLP DOI BibTeX RDF