Search results for "approximability"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
16	Sylvain Guillemot	Parameterized complexity and approximability of the Longest Compatible Sequence problem.	Discret. Optim.	2011	DBLP DOI BibTeX RDF
16	Mohammad Sadeq Dousti, Rasool Jalili	Milder Definitions of Computational Approximability: The Case of Zero-Knowledge Protocols.	IACR Cryptol. ePrint Arch.	2011	DBLP BibTeX RDF
16	Sascha Grau, Mathias Fischer 0001, Michael Brinkmeier, Günter Schäfer	On Complexity and Approximability of Optimal DoS Attacks on Multiple-Tree P2P Streaming Topologies.	IEEE Trans. Dependable Secur. Comput.	2011	DBLP DOI BibTeX RDF
16	Patrick Briest, Piotr Krysta	Buying Cheap Is Expensive: Approximability of Combinatorial Pricing Problems.	SIAM J. Comput.	2011	DBLP DOI BibTeX RDF
16	Tomoyuki Yamakami	Optimization, Randomized Approximability, and Boolean Constraint Satisfaction Problems.	ISAAC	2011	DBLP DOI BibTeX RDF
16	Stefanie Kosuch	Approximability of the Two-Stage Knapsack problem with discretely distributed weights.	CTW	2011	DBLP BibTeX RDF
16	Deeparnab Chakrabarty, Chandra Chekuri, Sanjeev Khanna, Nitish Korula	Approximability of Capacitated Network Design.	IPCO	2011	DBLP DOI BibTeX RDF
16	Ning Chen 0005, Nick Gravin, Pinyan Lu	On the Approximability of Budget Feasible Mechanisms.	SODA	2011	DBLP DOI BibTeX RDF
16	Venkatesan Guruswami, Yuan Zhou 0007	Tight Bounds on the Approximability of Almost-satisfiable Horn SAT and Exact Hitting Set.	SODA	2011	DBLP DOI BibTeX RDF
16	Amit Kumar 0001, Rajsekar Manokaran, Madhur Tulsiani, Nisheeth K. Vishnoi	On LP-Based Approximability for Strict CSPs.	SODA	2011	DBLP DOI BibTeX RDF
16	Martin Fink 0001, Joachim Spoerhase	Maximum Betweenness Centrality: Approximability and Tractable Cases.	WALCOM	2011	DBLP DOI BibTeX RDF
16	Spyros C. Kontogiannis, Paul G. Spirakis	Approximability of Symmetric Bimatrix Games and Related Experiments.	SEA	2011	DBLP DOI BibTeX RDF
16	Laurent Bulteau, Guillaume Fertin, Minghui Jiang 0001, Irena Rusu	Tractability and Approximability of Maximal Strip Recovery.	CPM	2011	DBLP DOI BibTeX RDF
16	Takehiro Ito, Erik D. Demaine	Approximability of the Subset Sum Reconfiguration Problem.	TAMC	2011	DBLP DOI BibTeX RDF
16	Angsheng Li, Linqing Tang	The Complexity and Approximability of Minimum Contamination Problems.	TAMC	2011	DBLP DOI BibTeX RDF
16	Valentin E. Brimkov	Complexity and Approximability Issues in Combinatorial Image Analysis.	IWCIA	2011	DBLP DOI BibTeX RDF
16	Jun Hosoda, Juraj Hromkovic, Taisuke Izumi, Hirotaka Ono 0001, Monika Steinová, Koichi Wada 0001	On the Approximability of Minimum Topic Connected Overlay and Its Special Instances.	MFCS	2011	DBLP DOI BibTeX RDF
16	Yota Otachi, Toshiki Saitoh, Katsuhisa Yamanaka, Shuji Kijima, Yoshio Okamoto, Hirotaka Ono 0001, Yushi Uno, Koichi Yamazaki	Approximability of the Path-Distance-Width for AT-free Graphs.	WG	2011	DBLP DOI BibTeX RDF
16	Katarína Cechlárová, Eva Jelínková	Approximability of Economic Equilibrium for Housing Markets with Duplicate Houses.	WG	2011	DBLP DOI BibTeX RDF
16	Ferdinando Cicalese, Martin Milanic, Ugo Vaccaro	Hardness, Approximability, and Exact Algorithms for Vector Domination and Total Vector Domination in Graphs.	FCT	2011	DBLP DOI BibTeX RDF
16	Sophie Toulouse	Approximability of the Multiple Stack TSP.	Electron. Notes Discret. Math.	2010	DBLP DOI BibTeX RDF
16	Dries R. Goossens, Sergey Polyakovskiy, Frits C. R. Spieksma, Gerhard J. Woeginger	The approximability of three-dimensional assignment problems with bottleneck objective.	Optim. Lett.	2010	DBLP DOI BibTeX RDF	Bottleneck problem, Multidimensional assignment, Computational complexity, Approximation, Efficient algorithm
16	Liming Cai, Xiuzhen Huang	Fixed-Parameter Approximation: Conceptual Framework and Approximability Results.	Algorithmica	2010	DBLP DOI BibTeX RDF
16	Tomoko Izumi, Taisuke Izumi, Hirotaka Ono 0001, Koichi Wada 0001	Approximability and inapproximability of the minimum certificate dispersal problem.	Theor. Comput. Sci.	2010	DBLP DOI BibTeX RDF
16	Douglas S. Altner, Özlem Ergun, Nelson A. Uhan	The Maximum Flow Network Interdiction Problem: Valid inequalities, integrality gaps, and approximability.	Oper. Res. Lett.	2010	DBLP DOI BibTeX RDF
16	Venkatesan Guruswami, Yuan Zhou 0007	Tight Bounds on the Approximability of Almost-satisfiable Horn SAT and Exact Hitting Set}.	Electron. Colloquium Comput. Complex.	2010	DBLP BibTeX RDF
16	Christian Glaßer, Christian Reitwießner, Heinz Schmitz, Maximilian Witek	Hardness and Approximability in Multi-Objective Optimization.	Electron. Colloquium Comput. Complex.	2010	DBLP BibTeX RDF
16	Peter Jonsson, Gustav Nordh	Approximability of Clausal Constraints.	Theory Comput. Syst.	2010	DBLP DOI BibTeX RDF
16	Gagan Goel, Chinmay Karande, Pushkar Tripathi, Lei Wang 0010	Approximability of combinatorial problems with multi-agent submodular cost functions.	SIGecom Exch.	2010	DBLP DOI BibTeX RDF
16	Martin Fink 0001, Joachim Spoerhase	Maximum Betweenness Centrality: Approximability and Tractable Cases	CoRR	2010	DBLP BibTeX RDF
16	Ning Chen 0005, Nick Gravin, Pinyan Lu	On the Approximability of Budget Feasible Mechanisms	CoRR	2010	DBLP BibTeX RDF
16	Ferdinando Cicalese, Martin Milanic, Ugo Vaccaro	Hardness, approximability, and exact algorithms for vector domination and total vector domination in graphs	CoRR	2010	DBLP BibTeX RDF
16	Sophie Toulouse	Approximability of the Multiple Stack TSP	CoRR	2010	DBLP BibTeX RDF
16	Deeparnab Chakrabarty, Chandra Chekuri, Sanjeev Khanna, Nitish Korula	Approximability of Capacitated Network Design	CoRR	2010	DBLP BibTeX RDF
16	Adam Kasperski, Pawel Zielinski 0001	On the approximability of robust spanning tree problems	CoRR	2010	DBLP BibTeX RDF
16	Stanislaw Gawiejnowicz, Alexander V. Kononov	Complexity and approximability of scheduling resumable proportionally deteriorating jobs.	Eur. J. Oper. Res.	2010	DBLP DOI BibTeX RDF
16	Deeparnab Chakrabarty, Gagan Goel	On the Approximability of Budgeted Allocations and Improved Lower Bounds for Submodular Welfare Maximization and GAP.	SIAM J. Comput.	2010	DBLP DOI BibTeX RDF
16	Minghui Jiang 0001	Approximability of Constrained LCS.	ISAAC (2)	2010	DBLP DOI BibTeX RDF
16	Stefan Canzar, Khaled M. Elbassioni, Amr Elmasry, Rajiv Raman 0001	On the Approximability of the Maximum Interval Constrained Coloring Problem.	ISAAC (2)	2010	DBLP DOI BibTeX RDF
16	Andreas Bley, Jose Neto	Approximability of 3- and 4-Hop Bounded Disjoint Paths Problems.	IPCO	2010	DBLP DOI BibTeX RDF
16	Neil Olver, F. Bruce Shepherd	Approximability of Robust Network Design.	SODA	2010	DBLP DOI BibTeX RDF
16	Raphaël Clifford, Alexandru Popa 0001	(In)approximability Results for Pattern Matching Problems.	Stringology	2010	DBLP BibTeX RDF
16	Pai-Han Huang, Yi Gai, Bhaskar Krishnamachari, Ashwin Sridharan	Subcarrier Allocation in Multiuser OFDM Systems: Complexity and Approximability.	WCNC	2010	DBLP DOI BibTeX RDF
16	Christian Glaßer, Christian Reitwießner, Heinz Schmitz, Maximilian Witek	Approximability and Hardness in Multi-objective Optimization.	CiE	2010	DBLP DOI BibTeX RDF
16	Antonios Antoniadis 0001, Andrzej Lingas	Approximability of Edge Matching Puzzles.	SOFSEM	2010	DBLP DOI BibTeX RDF
16	Qiaoming Han, Abraham P. Punnen	On the Approximability of the Vertex Cover and Related Problems.	AAIM	2010	DBLP DOI BibTeX RDF
16	Yi Wu 0002	The Approximability of Learning and Constraint Satisfaction Problems.		2010	DOI RDF
16	Robert Engström, Tommy Färnqvist, Peter Jonsson, Johan Thapper	Properties of an Approximability-related Parameter on Circular Complete Graphs.	Electron. Notes Discret. Math.	2009	DBLP DOI BibTeX RDF
16	Adam Kasperski, Pawel Zielinski 0001	On the approximability of minmax (regret) network optimization problems.	Inf. Process. Lett.	2009	DBLP DOI BibTeX RDF
16	Ning Chen	On the Approximability of Influence in Social Networks.	SIAM J. Discret. Math.	2009	DBLP DOI BibTeX RDF
16	Sébastien Angibaud, Guillaume Fertin, Irena Rusu, Annelyse Thévenin, Stéphane Vialette	On the Approximability of Comparing Genomes with Duplicates.	J. Graph Algorithms Appl.	2009	DBLP DOI BibTeX RDF
16	Jan Arpe, Bodo Manthey	Approximability of Minimum AND-Circuits.	Algorithmica	2009	DBLP DOI BibTeX RDF	Approximation algorithms, Circuit design, Inapproximability
16	David Pritchard	Approximability of Sparse Integer Programs	CoRR	2009	DBLP BibTeX RDF
16	Haim Avron, Gil Shklarski, Sivan Toledo	On Element SDD Approximability	CoRR	2009	DBLP BibTeX RDF
16	Wenliang Du, David Eppstein, Michael T. Goodrich, George S. Lueker	On the Approximability of Geometric and Geographic Generalization and the Min-Max Bin Covering Problem	CoRR	2009	DBLP BibTeX RDF
16	Spyros C. Kontogiannis, Paul G. Spirakis, Haralampos Tsaknakis	Recent Advances in Approximability of Bimatrix Nash.	Bull. EATCS	2009	DBLP BibTeX RDF
16	Jacek Blazewicz, Edmund K. Burke, Marta Kasprzak, Alexandr Kovalev, Mikhail Y. Kovalyov	On the approximability of the Simplified Partial Digest Problem.	Discret. Appl. Math.	2009	DBLP DOI BibTeX RDF
16	Bodo Manthey	Minimum-weight cycle covers and their approximability.	Discret. Appl. Math.	2009	DBLP DOI BibTeX RDF
16	Sylvain Guillemot, François Nicolas, Vincent Berry, Christophe Paul	On the approximability of the Maximum Agreement SubTree and Maximum Compatible Tree problems.	Discret. Appl. Math.	2009	DBLP DOI BibTeX RDF
16	Andreas Bley	Approximability of unsplittable shortest path routing problems.	Networks	2009	DBLP DOI BibTeX RDF
16	Michael Yu. Khachay, Maria I. Poberii	Complexity and Approximability of Committee Polyhedral Separability of Sets in General Position.	Informatica	2009	DBLP BibTeX RDF
16	Josep Díaz, Maria J. Serna, Paul G. Spirakis, Jacobo Torán	Paradigms for fast parallel approximability (Reprint from 1997).		2009	RDF
16	Nikhil Bansal 0001, Alberto Caprara, Klaus Jansen, Lars Prädel, Maxim Sviridenko	A Structural Lemma in 2-Dimensional Packing, and Its Implications on Approximability.	ISAAC	2009	DBLP DOI BibTeX RDF
16	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
16	Gagan Goel, Chinmay Karande, Pushkar Tripathi, Lei Wang 0010	Approximability of Combinatorial Problems with Multi-agent Submodular Cost Functions.	FOCS	2009	DBLP DOI BibTeX RDF
16	Jan Vondrák	Symmetry and Approximability of Submodular Maximization Problems.	FOCS	2009	DBLP DOI BibTeX RDF	submodular functions. matroids, multilinear extension, approximation algorithms
16	David Pritchard	Approximability of Sparse Integer Programs.	ESA	2009	DBLP DOI BibTeX RDF
16	Wenliang Du, David Eppstein, Michael T. Goodrich, George S. Lueker	On the Approximability of Geometric and Geographic Generalization and the Min-Max Bin Covering Problem.	WADS	2009	DBLP DOI BibTeX RDF
16	Carsten Gutwenger, Petra Mutzel, Bernd Zey	On the Hardness and Approximability of Planar Biconnectivity Augmentation.	COCOON	2009	DBLP DOI BibTeX RDF
16	Xi Chen 0001, Xiaotie Deng	Non-approximability of Bimatrix Nash Equilibria.	Encyclopedia of Algorithms	2008	DBLP DOI BibTeX RDF
16	John Christopher McCabe-Dansted, Geoffrey Pritchard, Arkadii M. Slinko	Approximability of Dodgson's rule.	Soc. Choice Welf.	2008	DBLP DOI BibTeX RDF
16	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
16	Takehiro Ito, Erik D. Demaine, Xiao Zhou 0001, Takao Nishizeki	Approximability of partitioning graphs with supply and demand.	J. Discrete Algorithms	2008	DBLP DOI BibTeX RDF
16	Xujin Chen, Xiaodong Hu 0001, Xiaohua Jia	Inapproximability and approximability of minimal tree routing and coloring.	J. Discrete Algorithms	2008	DBLP DOI BibTeX RDF
16	Anna Bernasconi 0001, Valentina Ciriani, Roberto Cordone	The optimization of kEP-SOPs: Computational complexity, approximability and experiments.	ACM Trans. Design Autom. Electr. Syst.	2008	DBLP DOI BibTeX RDF	multilevel logic synthesis, optimization, approximation algorithm, testing, Automatic synthesis
16	Sébastien Angibaud, Guillaume Fertin, Irena Rusu, Annelyse Thévenin, Stéphane Vialette	On the Approximability of Comparing Genomes with Duplicates	CoRR	2008	DBLP BibTeX RDF
16		On the approximability of the Maximum Agreement SubTree and Maximum Compatible Tree problems	CoRR	2008	DBLP BibTeX RDF
16	Tommy Färnqvist, Peter Jonsson, Johan Thapper	Approximability Distance in the Space of H-Colourability Problems	CoRR	2008	DBLP BibTeX RDF
16	Kristoffer Arnsfelt Hansen, Thomas Dueholm Hansen, Peter Bro Miltersen, Troels Bjerre Sørensen	Approximability and parameterized complexity of minmax values	CoRR	2008	DBLP BibTeX RDF
16	Adam Kasperski, Pawel Zielinski 0001	On the approximability of minmax (regret) network optimization problems	CoRR	2008	DBLP BibTeX RDF
16	Rodolphe Giroudeau, Jean-Claude König	General scheduling non-approximability results in presence of hierarchical communications.	Eur. J. Oper. Res.	2008	DBLP DOI BibTeX RDF
16	Yury L. Orlovich, Gerd Finke, Valery S. Gordon, Igor E. Zverovich	Approximability results for the maximum and minimum maximal induced matching problems.	Discret. Optim.	2008	DBLP DOI BibTeX RDF
16	Erik D. Demaine, Uriel Feige, MohammadTaghi Hajiaghayi, Mohammad R. Salavatipour	Combination Can Be Hard: Approximability of the Unique Coverage Problem.	SIAM J. Comput.	2008	DBLP DOI BibTeX RDF
16	Ning Chen	On the approximability of influence in social networks.	SODA	2008	DBLP BibTeX RDF
16	Sébastien Angibaud, Guillaume Fertin, Irena Rusu	On the Approximability of Comparing Genomes with Duplicates.	WALCOM	2008	DBLP DOI BibTeX RDF	conserved intervals, genome rearrangement, duplicates, breakpoints, adjacencies, common intervals, APX-Hardness
16	Deeparnab Chakrabarty, Gagan Goel	On the Approximability of Budgeted Allocations and Improved Lower Bounds for Submodular Welfare Maximization and GAP.	FOCS	2008	DBLP DOI BibTeX RDF
16	René A. Sitters	Approximability of Average Completion Time Scheduling on Unrelated Machines.	ESA	2008	DBLP DOI BibTeX RDF
16	Kristoffer Arnsfelt Hansen, Thomas Dueholm Hansen, Peter Bro Miltersen, Troels Bjerre Sørensen	Approximability and Parameterized Complexity of Minmax Values.	WINE	2008	DBLP DOI BibTeX RDF
16	Eric Brelsford, Piotr Faliszewski, Edith Hemaspaandra, Henning Schnoor, Ilka Schnoor	Approximability of Manipulating Elections.	AAAI	2008	DBLP BibTeX RDF
16	Emmanuel Hebrard, Barry O'Sullivan, Igor Razgon	A Soft Constraint of Equality: Complexity and Approximability.	CP	2008	DBLP DOI BibTeX RDF
16	Zoran Nikoloski, Sergio Grimbs, Joachim Selbig, Oliver Ebenhöh	Hardness and Approximability of the Inverse Scope Problem.	WABI	2008	DBLP DOI BibTeX RDF	completeness, scope, metabolic networks
16	Giorgio Ausiello, Vangelis Th. Paschos	Reductions That Preserve Approximability.	Handbook of Approximation Algorithms and Metaheuristics	2007	DBLP DOI BibTeX RDF
16	Hans-Joachim Böckenhauer, Luca Forlizzi, Juraj Hromkovic, Joachim Kneis, Joachim Kupke 0002, Guido Proietti, Peter Widmayer	On the Approximability of TSP on Local Modifications of Optimally Solved Instances.	Algorithmic Oper. Res.	2007	DBLP BibTeX RDF
16	Jukka Suomela	Approximability of identifying codes and locating-dominating codes.	Inf. Process. Lett.	2007	DBLP DOI BibTeX RDF
16	David Coudert, Pallab Datta, Stephane Perennes, Hervé Rivano, Marie-Emilie Voge	Shared Risk Resource Group Complexity and Approximability Issues.	Parallel Process. Lett.	2007	DBLP DOI BibTeX RDF
16	Giorgio Bartolini, Elisabetta Punta, Tullio Zolezzi	Approximability Properties for Second-Order Sliding Mode Control Systems.	IEEE Trans. Autom. Control.	2007	DBLP DOI BibTeX RDF
16	André Berger, Takuro Fukunaga, Hiroshi Nagamochi, Ojas Parekh	Approximability of the capacitated b-edge dominating set problem.	Theor. Comput. Sci.	2007	DBLP DOI BibTeX RDF
16	Yijia Chen, Martin Grohe, Magdalena Grüber	On Parameterized Approximability.	Electron. Colloquium Comput. Complex.	2007	DBLP BibTeX RDF
16	Qiaoming Han, Abraham P. Punnen	On the approximability of the vertex cover and related problems	CoRR	2007	DBLP BibTeX RDF
16	Peng Cui 0008	Improved Approximability Result for Test Set with Small Redundancy	CoRR	2007	DBLP BibTeX RDF