Search results for "approximability"

Hits ?▲	Authors	Title	Venue	Year	Link
16	Holger Dell, Eun Jung Kim 0002, Michael Lampis, Valia Mitsou, Tobias Mömke	Complexity and Approximability of Parameterized MAX-CSPs.	IPEC	2015	DBLP DOI BibTeX RDF
16	Evgeny R. Gafarov, Alexander A. Lazarev, Frank Werner 0001	Approximability results for the resource-constrained project scheduling problem with a single type of resources.	Ann. Oper. Res.	2014	DBLP DOI BibTeX RDF
16	Nhan-Tam Nguyen, Trung Thanh Nguyen 0004, Magnus Roos, Jörg Rothe	Computational complexity and approximability of social welfare optimization in multiagent resource allocation.	Auton. Agents Multi Agent Syst.	2014	DBLP DOI BibTeX RDF
16	Mikael Gast, Mathias Hauptmann	Approximability of the vertex cover problem in power-law graphs.	Theor. Comput. Sci.	2014	DBLP DOI BibTeX RDF
16	Zhixiang Chen 0001, Bin Fu, Randy Goebel, Guohui Lin, Weitian Tong, Jinhui Xu 0001, Boting Yang, Zhiyu Zhao, Binhai Zhu	On the approximability of the exemplar adjacency number problem for genomes with gene repetitions.	Theor. Comput. Sci.	2014	DBLP DOI BibTeX RDF
16	Martin Olsen, Anastasios Viglas	On the approximability of the link building problem.	Theor. Comput. Sci.	2014	DBLP DOI BibTeX RDF
16	Edouard Bonnet, Vangelis Th. Paschos	Parameterized (in)approximability of subset problems.	Oper. Res. Lett.	2014	DBLP DOI BibTeX RDF
16	Cristina Bazgan, Morgan Chopin, André Nichterlein, Florian Sikora	Parameterized approximability of maximizing the spread of influence in networks.	J. Discrete Algorithms	2014	DBLP DOI BibTeX RDF
16	Bhaskar DasGupta, Nasim Mobasheri	On optimal approximability results for computing the strong metric dimension.	CoRR	2014	DBLP BibTeX RDF
16	Miikka Hilke, Christoph Lenzen 0001, Jukka Suomela	Local Approximability of Minimum Dominating Set on Planar Graphs.	CoRR	2014	DBLP BibTeX RDF
16	Adam Kasperski, Adam Kurpisz, Pawel Zielinski 0001	Approximability of the robust representatives selection problem.	CoRR	2014	DBLP BibTeX RDF
16	Rafail Ostrovsky, Will Rosenbaum	It's Not Easy Being Three: The Approximability of Three-Dimensional Stable Matching Problems.	CoRR	2014	DBLP BibTeX RDF
16	Ágnes Cseh, David F. Manlove	Stable marriage and roommates problems with restricted edges: complexity and approximability.	CoRR	2014	DBLP BibTeX RDF
16	Xujin Chen, Xiaodong Hu 0001, Changjun Wang	Approximability of the Minimum Weighted Doubly Resolving Set Problem.	CoRR	2014	DBLP BibTeX RDF
16	Neil Olver, F. Bruce Shepherd	Approximability of Robust Network Design.	Math. Oper. Res.	2014	DBLP DOI BibTeX RDF
16	Stefanie Kosuch	Approximability of the two-stage stochastic knapsack problem with discretely distributed weights.	Discret. Appl. Math.	2014	DBLP DOI BibTeX RDF
16	Frank Gurski, Magnus Roos	Binary linear programming solutions and non-approximability for control problems in voting systems.	Discret. Appl. Math.	2014	DBLP DOI BibTeX RDF
16	Sergio Bermudo, Henning Fernau	Computing the differential of a graph: Hardness, approximability and exact algorithms.	Discret. Appl. Math.	2014	DBLP DOI BibTeX RDF
16	André Berger, Alexander Grigoriev, Ruben van der Zwaan	Complexity and approximability of the k-way vertex cut.	Networks	2014	DBLP DOI BibTeX RDF
16	Takehiro Ito, Erik D. Demaine	Approximability of the subset sum reconfiguration problem.	J. Comb. Optim.	2014	DBLP DOI BibTeX RDF
16	Thang N. Dinh, Yilin Shen, Dung T. Nguyen 0002, My T. Thai	On the approximability of positive influence dominating set in social networks.	J. Comb. Optim.	2014	DBLP DOI BibTeX RDF
16	William Cruz-Santos, Guillermo Morales-Luna	Approximability of Optimization Problems through Adiabatic Quantum Computation		2014	DOI RDF
16	Parinya Chalermsook, Sandy Heydrich, Eugenia Holm, Andreas Karrenbauer	Nearly Tight Approximability Results for Minimum Biclique Cover and Partition.	ESA	2014	DBLP DOI BibTeX RDF
16	Miikka Hilke, Christoph Lenzen 0001, Jukka Suomela	Brief announcement: local approximability of minimum dominating set on planar graphs.	PODC	2014	DBLP DOI BibTeX RDF
16	Sayan Bhattacharya, Parinya Chalermsook, Kurt Mehlhorn, Adrian Neumann	New Approximability Results for the Robust k-Median Problem.	SWAT	2014	DBLP DOI BibTeX RDF
16	Stefano Beretta 0001, Riccardo Dondi	Gene Tree Correction by Leaf Removal and Modification: Tractability and Approximability.	CiE	2014	DBLP DOI BibTeX RDF
16	Kazuya Haraguchi, Hirotaka Ono 0001	Approximability of Latin Square Completion-Type Puzzles.	FUN	2014	DBLP DOI BibTeX RDF
16	Xujin Chen, Changjun Wang	Approximability of the Minimum Weighted Doubly Resolving Set Problem.	COCOON	2014	DBLP DOI BibTeX RDF
16	Adrian Bock, Laura Sanità	On the approximability of two capacitated vehicle routing problems.	Electron. Notes Discret. Math.	2013	DBLP DOI BibTeX RDF
16	Valentin E. Brimkov	Approximability issues of guarding a set of segments.	Int. J. Comput. Math.	2013	DBLP DOI BibTeX RDF
16	Attila Benko, György Dósa, Zsolt Tuza	Bin covering with a general profit function: approximability results.	Central Eur. J. Oper. Res.	2013	DBLP DOI BibTeX RDF
16	Trung Thanh Nguyen 0004, Magnus Roos, Jörg Rothe	A survey of approximability and inapproximability results for social welfare optimization in multiagent resource allocation.	Ann. Math. Artif. Intell.	2013	DBLP DOI BibTeX RDF
16	Vladimir G. Deineko, Gerhard J. Woeginger	Complexity and in-approximability of a selection problem in robust optimization.	4OR	2013	DBLP DOI BibTeX RDF
16	Riccardo Dondi, Giancarlo Mauri, Italo Zoppis	The l-Diversity problem: Tractability and approximability.	Theor. Comput. Sci.	2013	DBLP DOI BibTeX RDF
16	Dimitris Bertsimas, Vineet Goyal	On the approximability of adjustable robust convex optimization under uncertainty.	Math. Methods Oper. Res.	2013	DBLP DOI BibTeX RDF
16	Mathias Hauptmann	On the approximability of Dense Steiner Problems.	J. Discrete Algorithms	2013	DBLP DOI BibTeX RDF
16	Adrian Dumitrescu, Minghui Jiang 0001	On the approximability of covering points by lines and related problems.	CoRR	2013	DBLP BibTeX RDF
16	Kamiel Cornelissen, Ruben Hoeksma, Bodo Manthey, N. S. Narayanaswamy, C. S. Rahul 0001	Approximability of Connected Factors.	CoRR	2013	DBLP BibTeX RDF
16	Edouard Bonnet, Vangelis Th. Paschos	Parameterized (in)approximability of subset problems.	CoRR	2013	DBLP BibTeX RDF
16	Piotr Skowron 0001, Piotr Faliszewski, Arkadii M. Slinko	Achieving Fully Proportional Representation: Approximability Results.	CoRR	2013	DBLP BibTeX RDF
16	Christian Knauer, Stefan König 0003, Daniel Werner	Fixed Parameter Complexity and Approximability of Norm Maximization.	CoRR	2013	DBLP BibTeX RDF
16	Cristina Bazgan, Morgan Chopin, André Nichterlein, Florian Sikora	Parameterized Approximability of Maximizing the Spread of Influence in Networks	CoRR	2013	DBLP BibTeX RDF
16	Sayan Bhattacharya, Parinya Chalermsook, Kurt Mehlhorn, Adrian Neumann	New Approximability Results for the Robust k-Median Problem.	CoRR	2013	DBLP BibTeX RDF
16	Yuichi Asahiro, Eiji Miyano, Toshihide Murata, Hirotaka Ono 0001	Optimal approximability of bookmark assignments.	Discret. Appl. Math.	2013	DBLP DOI BibTeX RDF
16	Ferdinando Cicalese, Martin Milanic, Ugo Vaccaro	On the approximability and exact algorithms for vector domination and related problems in graphs.	Discret. Appl. Math.	2013	DBLP DOI BibTeX RDF
16	Imed Kacem, Vangelis Th. Paschos	Weighted completion time minimization on a single-machine with a fixed non-availability interval: Differential approximability.	Discret. Optim.	2013	DBLP DOI BibTeX RDF
16	Paola Bonizzoni, Riccardo Dondi, Yuri Pirola	Maximum Disjoint Paths on Edge-Colored Graphs: Approximability and Tractability.	Algorithms	2013	DBLP DOI BibTeX RDF
16	Clemens Thielen, Stephan Westphal	Complexity and approximability of the maximum flow problem with minimum quantities.	Networks	2013	DBLP DOI BibTeX RDF
16	Dima Blokh, Danny Segev, Roded Sharan	The Approximability of Shortest Path-Based Graph Orientations of Protein-Protein Interaction Networks.	J. Comput. Biol.	2013	DBLP DOI BibTeX RDF
16	Jan Vondrák	Symmetry and Approximability of Submodular Maximization Problems.	SIAM J. Comput.	2013	DBLP DOI BibTeX RDF
16	Alberto Caprara, Margarida Carvalho, Andrea Lodi 0001, Gerhard J. Woeginger	A Complexity and Approximability Study of the Bilevel Knapsack Problem.	IPCO	2013	DBLP DOI BibTeX RDF
16	Klaus Jansen, Lars Prädel	New Approximability Results for Two-Dimensional Bin Packing.	SODA	2013	DBLP DOI BibTeX RDF
16	Ryan O'Donnell, Yuan Zhou 0007	Approximability and proof complexity.	SODA	2013	DBLP DOI BibTeX RDF
16	Alina Ene, Jan Vondrák, Yi Wu 0002	Local Distribution and the Symmetry Gap: Approximability of Multiway Partitioning Problems.	SODA	2013	DBLP DOI BibTeX RDF
16	Tarek Richard Besold, Robert Robere	When Almost Is Not Even Close: Remarks on the Approximability of HDTP.	AGI	2013	DBLP DOI BibTeX RDF
16	Kamiel Cornelissen, Ruben Hoeksma, Bodo Manthey, N. S. Narayanaswamy, C. S. Rahul 0001	Approximability of Connected Factors.	WAOA	2013	DBLP DOI BibTeX RDF
16	Hans-Joachim Böckenhauer, Lucia Keller	On the Approximability of Splitting-SAT in 2-CNF Horn Formulas.	IWOCA	2013	DBLP DOI BibTeX RDF
16	Anupam Gupta 0001, Satyen Kale, Viswanath Nagarajan, Rishi Saket, Baruch Schieber	The Approximability of the Binary Paintshop Problem.	APPROX-RANDOM	2013	DBLP DOI BibTeX RDF
16	Cristina Bazgan, Morgan Chopin, André Nichterlein, Florian Sikora	Parameterized Approximability of Maximizing the Spread of Influence in Networks.	COCOON	2013	DBLP DOI BibTeX RDF
16	Piotr Krzysztof Skowron, Piotr Faliszewski, Arkadii M. Slinko	Fully Proportional Representation as Resource Allocation: Approximability Results.	IJCAI	2013	DBLP BibTeX RDF
16	Richard Schmied	On Approximability of Bounded Degree Instances of Selected Optimization Problems.		2013	RDF
16	Mikael Gast	Approximability of Combinatorial Optimization Problems on Power Law Networks.		2013	RDF
16	Johan Håstad, Andrei A. Krokhin, Dániel Marx	The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 12451).	Dagstuhl Reports	2012	DBLP DOI BibTeX RDF
16	Markus Bläser, Holger Dell, Mahmoud Fouz	Complexity and Approximability of the Cover Polynomial.	Comput. Complex.	2012	DBLP DOI BibTeX RDF
16	Venkatesan Guruswami, Yuan Zhou 0007	Tight Bounds on the Approximability of Almost-Satisfiable Horn SAT and Exact Hitting Set.	Theory Comput.	2012	DBLP DOI BibTeX RDF
16	Steven Kelk, Leo van Iersel, Nela Lekic, Simone Linz, Céline Scornavacca, Leen Stougie	Cycle Killer...Qu'est-ce que c'est? On the Comparative Approximability of Hybridization Number and Directed Feedback Vertex Set.	SIAM J. Discret. Math.	2012	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.	Artif. Intell.	2012	DBLP DOI BibTeX RDF
16	Elliot Anshelevich, Deeparnab Chakrabarty, Ameya Hate, Chaitanya Swamy	Approximability of the Firefighter Problem - Computing Cuts over Time.	Algorithmica	2012	DBLP DOI BibTeX RDF
16	Jun Hosoda, Juraj Hromkovic, Taisuke Izumi, Hirotaka Ono 0001, Monika Steinová, Koichi Wada 0001	On the approximability and hardness of minimum topic connected overlay and its special instances.	Theor. Comput. Sci.	2012	DBLP DOI BibTeX RDF
16	Laurent Bulteau, Guillaume Fertin, Minghui Jiang 0001, Irena Rusu	Tractability and approximability of maximal strip recovery.	Theor. Comput. Sci.	2012	DBLP DOI BibTeX RDF
16	Minghui Jiang 0001	Approximability of constrained LCS.	J. Comput. Syst. Sci.	2012	DBLP DOI BibTeX RDF
16	Mikael Gast, Mathias Hauptmann	Approximability of the Vertex Cover Problem in Power Law Graphs	CoRR	2012	DBLP BibTeX RDF
16	Piotr Krzysztof Skowron, Piotr Faliszewski, Arkadii M. Slinko	Proportional Representation as Resource Allocation: Approximability Results	CoRR	2012	DBLP BibTeX RDF
16	Ryan O'Donnell, Yuan Zhou 0007	Approximability and proof complexity	CoRR	2012	DBLP BibTeX RDF
16	Omid Amini, David Peleg, Stéphane Pérennes, Ignasi Sau, Saket Saurabh 0001	On the approximability of some degree-constrained subgraph problems.	Discret. Appl. Math.	2012	DBLP DOI BibTeX RDF
16	Kazuo Iwama	Approximability of Stable Matching Problems.	WALCOM	2012	DBLP DOI BibTeX RDF
16	Nhan-Tam Nguyen, Trung Thanh Nguyen 0004, Magnus Roos, Jörg Rothe	Complexity and approximability of social welfare optimization in multiagent resource allocation.	AAMAS	2012	DBLP BibTeX RDF
16	Vadim Azhmyakov, Félix A. Miranda-Villatoro	Approximability and Variational Description of the Zeno Behavior in Affine Switched Systems.	ADHS	2012	DBLP DOI BibTeX RDF
16	Nhan-Tam Nguyen, Trung Thanh Nguyen 0004, Jörg Rothe	Complexity and Approximability of Egalitarian Nash Product Social Welfare Optimization in Multiagent Resource Allocation.	STAIRS	2012	DBLP DOI BibTeX RDF
16	Shalev Ben-David, Elyot Grant, Will Ma, Malcolm Sharpe	The Approximability and Integrality Gap of Interval Stabbing and Independence Problems.	CCCG	2012	DBLP BibTeX RDF
16	Mourad El Ouali, Gerold Jäger	The b-Matching Problem in Hypergraphs: Hardness and Approximability.	COCOA	2012	DBLP DOI BibTeX RDF
16	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
16	Zhixiang Chen 0001, Bin Fu, Binhai Zhu	Erratum: The Approximability of the Exemplar Breakpoint Distance Problem.	FAW-AAIM	2012	DBLP DOI BibTeX RDF
16	Bruno Escoffier, Jérôme Monnot, Vangelis Th. Paschos, Mingyu Xiao 0001	New Results on Polynomial Inapproximability and Fixed Parameter Approximability of edge dominating set.	IPEC	2012	DBLP DOI BibTeX RDF
16	Monika Steinová	Measuring hardness of complex problems: Approximability and exact algorithms.		2012	RDF
16	Michael Elberfeld, Vineet Bafna, Iftah Gamzu, Alexander Medvedovsky, Danny Segev, Dana Silverbush, Uri Zwick, Roded Sharan	On the Approximability of Reachability-Preserving Network Orientations.	Internet Math.	2011	DBLP DOI BibTeX RDF
16	Vadim Azhmyakov, Marco Tulio Angulo	Applications of the strong approximability property to a class of affine switched systems and to relaxed differential equations with affine structure.	Int. J. Syst. Sci.	2011	DBLP DOI BibTeX RDF
16	Zachary Friggstad, Mohammad R. Salavatipour	Approximability of Packing Disjoint Cycles.	Algorithmica	2011	DBLP DOI BibTeX RDF
16	David Pritchard, Deeparnab Chakrabarty	Approximability of Sparse Integer Programs.	Algorithmica	2011	DBLP DOI BibTeX RDF
16	Adam Kasperski, Pawel Zielinski 0001	On the approximability of robust spanning tree problems.	Theor. Comput. Sci.	2011	DBLP DOI BibTeX RDF
16	Valentin E. Brimkov, Andrew Leach, Jimmy Wu, Michael Mastroianni	On the Approximability of a Geometric Set Cover Problem.	Electron. Colloquium Comput. Complex.	2011	DBLP BibTeX RDF
16	Marcel R. Ackermann, Johannes Blömer, Christoph Scholz 0001	Hardness and Non-Approximability of Bregman Clustering Problems.	Electron. Colloquium Comput. Complex.	2011	DBLP BibTeX RDF
16	Patrik Floréen, Marja Hassinen, Joel Kaasinen, Petteri Kaski, Topi Musto, Jukka Suomela	Local Approximability of Max-Min and Min-Max Linear Programs.	Theory Comput. Syst.	2011	DBLP DOI BibTeX RDF
16	Steven Kelk, Leo van Iersel, Nela Lekic, Simone Linz, Céline Scornavacca, Leen Stougie	Cycle killer... qu'est-ce que c'est? On the comparative approximability of hybridization number and directed feedback vertex set.	CoRR	2011	DBLP BibTeX RDF
16	Tomoyuki Yamakami	Optimization, Randomized Approximability, and Boolean Constraint Satisfaction Problems	CoRR	2011	DBLP BibTeX RDF
16	Jun Hosoda, Juraj Hromkovic, Taisuke Izumi, Hirotaka Ono 0001, Monika Steinová, Koichi Wada 0001	On the Approximability and Hardness of Minimum Topic Connected Overlay and Its Special Instances	CoRR	2011	DBLP BibTeX RDF
16	N. S. Narayanaswamy, Swapnoneel Roy	On Approximability of Block Sorting	CoRR	2011	DBLP BibTeX RDF
16	Jan Vondrák	Symmetry and approximability of submodular maximization problems	CoRR	2011	DBLP BibTeX RDF
16	Christoph Ambühl, Monaldo Mastrolilli, Nikolaus Mutsanas, Ola Svensson	On the Approximability of Single-Machine Scheduling with Precedence Constraints.	Math. Oper. Res.	2011	DBLP DOI BibTeX RDF
16	Giulia Galbiati, Romeo Rizzi, Edoardo Amaldi	On the approximability of the minimum strictly fundamental cycle basis problem.	Discret. Appl. Math.	2011	DBLP DOI BibTeX RDF