Search results for "inapproximability"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
18	Guy Kindler, Ryan O'Donnell, Subhash Khot, Elchanan Mossel	Optimal Inapproximability Results for MAX-CUT and Other 2-Variable CSPs?	Electron. Colloquium Comput. Complex.	2005	DBLP BibTeX RDF
18	Henry C. Lin, Tim Roughgarden, Éva Tardos, Asher Walkover	Braess's Paradox, Fibonacci Numbers, and Exponential Inapproximability.	ICALP	2005	DBLP DOI BibTeX RDF
18	Subhash Khot, Richard J. Lipton, Evangelos Markakis, Aranyak Mehta	Inapproximability Results for Combinatorial Auctions with Submodular Utility Functions.	WINE	2005	DBLP DOI BibTeX RDF
18	Virginia Vassilevska	Explicit Inapproximability Bounds for the Shortest Superstring Problem.	MFCS	2005	DBLP DOI BibTeX RDF
18	Bhaskar DasGupta, Sergio Ferrarini, Uthra Gopalakrishnan, Nisha Raj Paryani	Inapproximability Results for the Lateral Gene Transfer Problem.	ICTCS	2005	DBLP DOI BibTeX RDF
18	Venkatesan Guruswami	Inapproximability Results for Set Splitting and Satisfiability Problems with No Mixed Clauses.	Algorithmica	2004	DBLP DOI BibTeX RDF	Set splitting, Hardness of approximations, PCP, Gadgets
18	Lars Engebretsen, Jonas Holmerin, Alexander Russell	Inapproximability results for equations over finite groups.	Theor. Comput. Sci.	2004	DBLP DOI BibTeX RDF
18	Gerhard J. Woeginger	Inapproximability results for no-wait job shop scheduling.	Oper. Res. Lett.	2004	DBLP DOI BibTeX RDF
18	Uriel Feige, Daniele Micciancio	The inapproximability of lattice and coding problems with preprocessing.	J. Comput. Syst. Sci.	2004	DBLP DOI BibTeX RDF
18	Luca Trevisan	Inapproximability of Combinatorial Optimization Problems	Electron. Colloquium Comput. Complex.	2004	DBLP BibTeX RDF
18	Oded Regev 0001	Improved Inapproximability of Lattice and Coding Problems With Preprocessing.	IEEE Trans. Inf. Theory	2004	DBLP DOI BibTeX RDF
18	Luca Trevisan	Inapproximability of Combinatorial Optimization Problems	CoRR	2004	DBLP BibTeX RDF
18	Jianzhong Zhang 0001, Xiaoguang Yang, Mao-cheng Cai	Inapproximability and a polynomially solvable special case of a network improvement problem.	Eur. J. Oper. Res.	2004	DBLP DOI BibTeX RDF
18	Michael Elkin, Guy Kortsarz	Logarithmic inapproximability of the radio broadcast problem.	J. Algorithms	2004	DBLP DOI BibTeX RDF
18	Nikhil Bansal 0001, Maxim Sviridenko	New approximability and inapproximability results for 2-dimensional Bin Packing.	SODA	2004	DBLP BibTeX RDF
18	Subhash Khot, Guy Kindler, Elchanan Mossel, Ryan O'Donnell	Optimal Inapproximability Results for Max-Cut and Other 2-Variable CSPs?	FOCS	2004	DBLP DOI BibTeX RDF
18	Michael Elkin, Guy Kortsarz	Polylogarithmic Inapproximability of the Radio Broadcast Problem.	APPROX-RANDOM	2004	DBLP DOI BibTeX RDF
18	Janka Chlebíková, Miroslav Chlebík	Inapproximability results for bounded variants of optimization problems	Electron. Colloquium Comput. Complex.	2003	DBLP BibTeX RDF
18	Miroslav Chlebík, Janka Chlebíková	Inapproximability Results for Bounded Variants of Optimization Problems.	FCT	2003	DBLP DOI BibTeX RDF
18	Eran Halperin, Robert Krauthgamer	Polylogarithmic inapproximability.	STOC	2003	DBLP DOI BibTeX RDF	integrality ratio, polylogarithmic approximation, approximation algorithms, Steiner tree, hardness of approximation
18	Johan Håstad	Inapproximability Some history and some open problems.	CCC	2003	DBLP DOI BibTeX RDF
18	Jonas Holmerin, Subhash Khot	A Strong Inapproximability Gap for a Generalization of Minimum Bisection.	CCC	2003	DBLP DOI BibTeX RDF
18	Stephan J. Eidenbenz	Inapproximability of finding maximum hidden sets on polygons and terrains.	Comput. Geom.	2002	DBLP DOI BibTeX RDF
18	Liming Cai, David W. Juedes, Iyad A. Kanj	The inapproximability of non-NP-hard optimization problems.	Theor. Comput. Sci.	2002	DBLP DOI BibTeX RDF
18	Lars Engebretsen, Jonas Holmerin, Alexander Russell	Inapproximability Results for Equations over Finite Groups	Electron. Colloquium Comput. Complex.	2002	DBLP BibTeX RDF
18	Lars Engebretsen, Jonas Holmerin, Alexander Russell	Inapproximability Results for Equations over Finite Groups.	ICALP	2002	DBLP DOI BibTeX RDF
18	Jonas Holmerin	Improved Inapproximability Results for Vertex Cover on k -Uniform Hypergraphs.	ICALP	2002	DBLP DOI BibTeX RDF
18	Magnús M. Halldórsson, Kazuo Iwama, Shuichi Miyazaki, Yasufumi Morita	Inapproximability Results on Stable Marriage Problems.	LATIN	2002	DBLP DOI BibTeX RDF
18	Uriel Feige, Daniele Micciancio	The Inapproximability of Lattice and Coding Problems with Preprocessing.	CCC	2002	DBLP DOI BibTeX RDF
18	Oded Goldreich 0001	Using the FGLSS-reduction to Prove Inapproximability Results for Minimum Vertex Cover in Hypergraphs.	Electron. Colloquium Comput. Complex.	2001	DBLP BibTeX RDF
18	Bin Ma 0002, Lusheng Wang 0001	On the Inapproximability of Disjoint Paths and Minimum Steiner Forest with Bandwidth Constraints.	J. Comput. Syst. Sci.	2000	DBLP DOI BibTeX RDF
18	Aravind Srinivasan	The value of strong inapproximability results for clique.	STOC	2000	DBLP DOI BibTeX RDF	P vs. NP, inapproximabilit, packing integer programs, approximation algorithms, random sampling, independent set, clique
18	Venkatesan Guruswami	Inapproximability results for set splitting and satisfiability problems with no mixed clauses.	APPROX	2000	DBLP DOI BibTeX RDF
18	Piotr Berman, Marek Karpinski	On Some Tighter Inapproximability Results, Further Improvements	Electron. Colloquium Comput. Complex.	1998	DBLP BibTeX RDF
18	Piotr Berman, Marek Karpinski	On Some Tighter Inapproximability Results	Electron. Colloquium Comput. Complex.	1998	DBLP BibTeX RDF
18	Stephan J. Eidenbenz, Christoph Stamm, Peter Widmayer	Positioning Guards at Fixed Height Above a Terrain - An Optimum Inapproximability Result.	ESA	1998	DBLP DOI BibTeX RDF
18	Stephan J. Eidenbenz, Christoph Stamm, Peter Widmayer	Inapproximability of some art gallery problems.	CCCG	1998	DBLP BibTeX RDF
18	Johan Håstad	Some optimal inapproximability results	Electron. Colloquium Comput. Complex.	1997	DBLP BibTeX RDF
18	Johan Håstad	Some Optimal Inapproximability Results.	STOC	1997	DBLP DOI BibTeX RDF
13	Florian Diedrich, Klaus Jansen	Improved approximation algorithms for scheduling with fixed jobs.	SODA	2009	DBLP DOI BibTeX RDF
13	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
13	Ryan O'Donnell, Yi Wu 0002	3-bit dictator testing: 1 vs. 5/8.	SODA	2009	DBLP DOI BibTeX RDF
13	Khaled M. Elbassioni, Rajiv Raman 0001, Saurabh Ray, René Sitters	On the approximability of the maximum feasible subsystem problem with 0/1-coefficients.	SODA	2009	DBLP DOI BibTeX RDF
13	Erik D. Demaine, MohammadTaghi Hajiaghayi, Dániel Marx	Minimizing Movement: Fixed-Parameter Tractability.	ESA	2009	DBLP DOI BibTeX RDF
13	Erik Saule, Denis Trystram	Multi-users scheduling in parallel systems.	IPDPS	2009	DBLP DOI BibTeX RDF
13	Tim Nonner, Alexander Souza	A 5/3-Approximation Algorithm for Joint Replenishment with Deadlines.	COCOA	2009	DBLP DOI BibTeX RDF
13	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
13	Ryan O'Donnell, Yi Wu 0002	Conditional hardness for satisfiable 3-CSPs.	STOC	2009	DBLP DOI BibTeX RDF	khot's, satisfiable 3-CSPs, hardness of approximation, PCP
13	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
13	Daniel Berend, Steven Skiena, Yochai Twitto	Combinatorial dominance guarantees for problems with infeasible solutions.	ACM Trans. Algorithms	2008	DBLP DOI BibTeX RDF	Computation complexity, approximation algorithms, algorithms analysis, dominance analysis
13	Julia Chuzhoy, Anupam Gupta 0001, Joseph Naor, Amitabh Sinha	On the approximability of some network design problems.	ACM Trans. Algorithms	2008	DBLP DOI BibTeX RDF	cost-distance, fixed charge network flow, priority Steiner tree, network design, Hardness of approximation
13	Ning Chen	On the approximability of influence in social networks.	SODA	2008	DBLP BibTeX RDF
13	Julia Kempe, Hirotada Kobayashi, Keiji Matsumoto, Ben Toner, Thomas Vidick	Entangled Games are Hard to Approximate.	FOCS	2008	DBLP DOI BibTeX RDF
13	Patrik Floréen, Petteri Kaski, Topi Musto, Jukka Suomela	Approximating max-min linear programs with local algorithms.	IPDPS	2008	DBLP DOI BibTeX RDF
13	Shachar Lovett, Roy Meshulam, Alex Samorodnitsky	Inverse conjecture for the gowers norm is false.	STOC	2008	DBLP DOI BibTeX RDF	gowers norm, multivariate polynomials, low degree tests
13	Pavol Hell, André Raspaud, Juraj Stacho	On Injective Colourings of Chordal Graphs.	LATIN	2008	DBLP DOI BibTeX RDF
13	Thomas Erlebach, Erik Jan van Leeuwen	Domination in Geometric Intersection Graphs.	LATIN	2008	DBLP DOI BibTeX RDF
13	Leszek Gasieniec, David Peleg, Qin Xin 0001	Faster communication in known topology radio networks.	Distributed Comput.	2007	DBLP DOI BibTeX RDF	Broadcasting, Gossiping, Radio networks
13	Alexander Grigoriev, Maxim Sviridenko, Marc Uetz	Machine scheduling with resource dependent processing times.	Math. Program.	2007	DBLP DOI BibTeX RDF	Mathematics Subject Classification (2000) 90B35, 68Q25, 68M20
13	Mohammad Taghi Hajiaghayi, Guy Kortsarz, Vahab S. Mirrokni, Zeev Nutov	Power optimization for connectivity problems.	Math. Program.	2007	DBLP DOI BibTeX RDF
13	Ahuva Mu'alem, Michael Schapira	Setting lower bounds on truthfulness: extended abstract.	SODA	2007	DBLP BibTeX RDF
13	Patrick Briest, Piotr Krysta	Buying cheap is expensive: hardness of non-parametric multi-product pricing.	SODA	2007	DBLP BibTeX RDF
13	Michael Dom, Jiong Guo, Rolf Niedermeier	Approximability and Parameterized Complexity of Consecutive Ones Submatrix Problems.	TAMC	2007	DBLP DOI BibTeX RDF
13	Eden Chlamtac	Approximation Algorithms Using Hierarchies of Semidefinite Programming Relaxations.	FOCS	2007	DBLP DOI BibTeX RDF
13	Yuval Lando, Zeev Nutov	On Minimum Power Connectivity Problems.	ESA	2007	DBLP DOI BibTeX RDF
13	Alexander Grigoriev, Joyce van Loon, Maxim Sviridenko, Marc Uetz, Tjark Vredeveld	Bundle Pricing with Comparable Items.	ESA	2007	DBLP DOI BibTeX RDF
13	Gaëlle Brevier, Romeo Rizzi, Stéphane Vialette	Pattern Matching in Protein-Protein Interaction Graphs.	FCT	2007	DBLP DOI BibTeX RDF
13	Marc J. van Kreveld, Maarten Löffler, Rodrigo I. Silveira	Optimization for First Order Delaunay Triangulations.	WADS	2007	DBLP DOI BibTeX RDF
13	Jon Feldman, S. Muthukrishnan 0001, Martin Pál, Clifford Stein 0001	Budget optimization in search-based advertising auctions.	EC	2007	DBLP DOI BibTeX RDF	optimization, auctions, sponsored search, bidding
13	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
13	Yuichi Asahiro, Jesper Jansson 0001, Eiji Miyano, Hirotaka Ono 0001, Kouhei Zenmyo	Approximation Algorithms for the Graph Orientation Minimizing the Maximum Weighted Outdegree.	AAIM	2007	DBLP DOI BibTeX RDF
13	Benjamin Hummel, Sven Kosub	Acyclic type-of-relationship problems on the internet: an experimental analysis.	Internet Measurement Conference	2007	DBLP DOI BibTeX RDF	algorithms, inter-domain routing, as relationships
13	Shuchi Chawla 0001, Robert Krauthgamer, Ravi Kumar 0001, Yuval Rabani, D. Sivakumar 0001	On the Hardness of Approximating Multicut and Sparsest-Cut.	Comput. Complex.	2006	DBLP DOI BibTeX RDF	68Q17, Subject classification
13	Noga Alon, Dana Moshkovitz, Shmuel Safra	Algorithmic construction of sets for k-restrictions.	ACM Trans. Algorithms	2006	DBLP DOI BibTeX RDF	k-restriction, almost k-wise independence, generalized hashing, splitter, Set-Cover, Derandomization, group testing
13	Ioannis Caragiannis, Christos Kaklamanis, Panagiotis Kanellopoulos	Energy-Efficient Wireless Network Design.	Theory Comput. Syst.	2006	DBLP DOI BibTeX RDF
13	Virginia Vassilevska, Ryan Williams 0001, Shan Leung Maverick Woo	Confronting hardness using a hybrid approach.	SODA	2006	DBLP DOI BibTeX RDF
13	Bhaskar DasGupta, Germán Andres Enciso, Eduardo D. Sontag, Yi Zhang 0002	Algorithmic and Complexity Results for Decompositions of Biological Networks into Monotone Subsystems.	WEA	2006	DBLP DOI BibTeX RDF
13	Christopher Umans	Optimization Problems in the Polynomial-Time Hierarchy.	TAMC	2006	DBLP DOI BibTeX RDF
13	Danny Segev, Gil Segev 0001	Approximate k-Steiner Forests Via the Lagrangian Relaxation Technique with Internal Preprocessing.	ESA	2006	DBLP DOI BibTeX RDF
13	Thomas Erlebach, Alexander Hall, Linda S. Moonen, Alessandro Panconesi, Frits C. R. Spieksma, Danica Vukadinovic	Robustness of the Internet at the Topology and Routing Level.	Research Results of the DICS Program	2006	DBLP DOI BibTeX RDF
13	Alexander A. Ageev, Alexander V. Kononov	Approximation Algorithms for Scheduling Problems with Exact Delays.	WAOA	2006	DBLP DOI BibTeX RDF
13	Howard J. Karloff, Subhash Khot, Aranyak Mehta, Yuval Rabani	On earthmover distance, metric labeling, and 0-extension.	STOC	2006	DBLP DOI BibTeX RDF
13	Moses Charikar, Konstantin Makarychev, Yury Makarychev	Near-optimal algorithms for unique games.	STOC	2006	DBLP DOI BibTeX RDF	unique games, approximation algorithms, semidefinite programming, constraint satisfaction problems
13	Gruia Calinescu, Adrian Dumitrescu, János Pach	Reconfigurations in Graphs and Grids.	LATIN	2006	DBLP DOI BibTeX RDF
13	Iannis Tourlakis	New Lower Bounds for Vertex Cover in the Lovasz-Schrijver Hierarchy.	CCC	2006	DBLP DOI BibTeX RDF
13	Alexander Grigoriev, Maxim Sviridenko, Marc Uetz	Unrelated Parallel Machine Scheduling with Resource Dependent Processing Times.	IPCO	2005	DBLP DOI BibTeX RDF
13	Mohammad Taghi Hajiaghayi, Guy Kortsarz, Vahab S. Mirrokni, Zeev Nutov	Power Optimization for Connectivity Problems.	IPCO	2005	DBLP DOI BibTeX RDF
13	Julia Chuzhoy, Anupam Gupta 0001, Joseph Naor, Amitabh Sinha	On the approximability of some network design problems.	SODA	2005	DBLP BibTeX RDF
13	François Nicolas, Eric Rivals	Hardness of Optimal Spaced Seed Design.	CPM	2005	DBLP DOI BibTeX RDF
13	Matthew Andrews, Julia Chuzhoy, Sanjeev Khanna, Lisa Zhang	Hardness of the Undirected Edge-Disjoint Paths Problem with Congestion.	FOCS	2005	DBLP DOI BibTeX RDF
13	Chandra Chekuri, Martin Pál	A Recursive Greedy Algorithm for Walks in Directed Graphs.	FOCS	2005	DBLP DOI BibTeX RDF
13	Elchanan Mossel, Ryan O'Donnell, Krzysztof Oleszkiewicz	Noise stability of functions with low in.uences invariance and optimality.	FOCS	2005	DBLP DOI BibTeX RDF
13	Leszek Gasieniec, David Peleg, Qin Xin 0001	Faster communication in known topology radio networks.	PODC	2005	DBLP DOI BibTeX RDF	algorithms, broadcasting, planar graphs, gossiping, radio networks
13	Yossi Azar, Amir Epstein	The Hardness of Network Design for Unsplittable Flow with Selfish Users.	WAOA	2005	DBLP DOI BibTeX RDF
13	Iannis Tourlakis	Towards Optimal Integrality Gaps for Hypergraph Vertex Cover in the Lovász-Schrijver Hierarchy.	APPROX-RANDOM	2005	DBLP DOI BibTeX RDF
13	Xujin Chen, Xiao-Dong Hu 0001, Tianping Shuai	Routing and Coloring for Maximal Number of Trees.	COCOON	2005	DBLP DOI BibTeX RDF
13	Shuchi Chawla 0001, Robert Krauthgamer, Ravi Kumar 0001, Yuval Rabani, D. Sivakumar 0001	On the Hardness of Approximating Multicut and Sparsest-Cut.	CCC	2005	DBLP DOI BibTeX RDF
13	Xujin Chen, Xiao-Dong Hu 0001, Xiaohua Jia	Complexity of Minimal Tree Routing and Coloring.	AAIM	2005	DBLP DOI BibTeX RDF
13	Jianer Chen, Fenghui Zhang	On Product Covering in Supply Chain Models: Natural Complete Problems for W[3] and W[4].	AAIM	2005	DBLP DOI BibTeX RDF
13	Rajgopal Kannan, S. Sitharama Iyengar	Game-theoretic models for reliable path-length and energy-constrained routing with data aggregation in wireless sensor networks.	IEEE J. Sel. Areas Commun.	2004	DBLP DOI BibTeX RDF