Search results for "approximability"

Hits ?▲	Authors	Title	Venue	Year	Link
16	Alba Muñoz, Fernando Rubio 0001	Evaluating Genetic Algorithms through the Approximability Hierarchy.	CoRR	2024	DBLP DOI BibTeX RDF
16	Ferdinando Cicalese, Francesca Ugazio	On the complexity and approximability of Bounded access Lempel Ziv coding.	CoRR	2024	DBLP DOI BibTeX RDF
16	Joshua Brakensiek, Neng Huang, Uri Zwick	Tight approximability of MAX 2-SAT and relatives, under UGC.	SODA	2024	DBLP DOI BibTeX RDF
16	Henry L. Fleischmann, Surya Teja Gavva, Karthik C. S.	On Approximability of Steiner Tree in ℓp-metrics.	SODA	2024	DBLP DOI BibTeX RDF
16	Tomer Ezra, Michal Feldman, Maya Schlesinger	On the (In)approximability of Combinatorial Contracts.	ITCS	2024	DBLP DOI BibTeX RDF
16	Antoine Amarilli, Timothy van Bremen, Kuldeep S. Meel	Conjunctive Queries on Probabilistic Graphs: The Limits of Approximability.	ICDT	2024	DBLP DOI BibTeX RDF
16	Zdenek Dvorák 0001, Ken-ichi Kawarabayashi	Additive non-approximability of chromatic number in proper minor-closed classes.	J. Comb. Theory, Ser. B	2023	DBLP DOI BibTeX RDF
16	Marcelo Arenas, Pablo Barceló, Leopoldo E. Bertossi, Mikaël Monet	On the Complexity of SHAP-Score-Based Explanations: Tractability via Knowledge Compilation and Non-Approximability Results.	J. Mach. Learn. Res.	2023	DBLP BibTeX RDF
16	Ioannis Katsikarelis, Michael Lampis, Vangelis Th. Paschos	Improved (In-)Approximability Bounds for d-Scattered Set.	J. Graph Algorithms Appl.	2023	DBLP DOI BibTeX RDF
16	Majid Khonji	Approximability and efficient algorithms for constrained fixed-horizon POMDPs with durative actions.	Artif. Intell.	2023	DBLP DOI BibTeX RDF
16	Yuichi Asahiro, Hiroshi Eto, Tesshu Hanaka, Guohui Lin, Eiji Miyano, Ippei Terabaru	Corrigendum to "Complexity and approximability of the happy set problem" [Theor. Comput. Sci. 866 (2021) 123-144].	Theor. Comput. Sci.	2023	DBLP DOI BibTeX RDF
16	Yuqiao He, Guoliang Qiu 0001, Chihao Zhang 0001	Approximability of the complementarily symmetric Holant problems on cubic graphs.	Theor. Comput. Sci.	2023	DBLP DOI BibTeX RDF
16	Santiago Valdés Ravelo, Cristina G. Fernandes	Complexity and approximability of Minimum Path-Collection Exact Covers.	Theor. Comput. Sci.	2023	DBLP DOI BibTeX RDF
16	Amey Bhangale, Subhash Khot, Dor Minzer	On Approximability of Satisfiable k-CSPs: II.	Electron. Colloquium Comput. Complex.	2023	DBLP BibTeX RDF
16	Amey Bhangale, Subhash Khot, Dor Minzer	On Approximability of Satisfiable k-CSPs: III.	Electron. Colloquium Comput. Complex.	2023	DBLP BibTeX RDF
16	Amey Bhangale, Subhash Khot, Dor Minzer	On Approximability of Satisfiable k-CSPs: IV.	Electron. Colloquium Comput. Complex.	2023	DBLP BibTeX RDF
16	Holger Boche, Rafael F. Schaefer, H. Vincent Poor	Algorithmic Computability and Approximability of Capacity-Achieving Input Distributions.	IEEE Trans. Inf. Theory	2023	DBLP DOI BibTeX RDF
16	Tomer Ezra, Michal Feldman, Maya Schlesinger	On the (In)approximability of Combinatorial Contracts.	CoRR	2023	DBLP DOI BibTeX RDF
16	Tobias Breiten, Bernhard Höveler	On the approximability of Koopman-based operator Lyapunov equations.	CoRR	2023	DBLP DOI BibTeX RDF
16	Panagiotis Aivasiliotis, Aris Pagourtzis	On the Approximability of External-Influence-Driven Problems.	CoRR	2023	DBLP DOI BibTeX RDF
16	Youngkyu Lee, Jongho Park 0002, Chang-Ock Lee	Balanced Group Convolution: An Improved Group Convolution Based on Approximability Estimates.	CoRR	2023	DBLP DOI BibTeX RDF
16	Zhiguo Fu, Tianyu Liu, Xiongxin Yang	Approximability of the Four-Vertex Model.	CoRR	2023	DBLP DOI BibTeX RDF
16	Welverton R. Silva, Fábio Luiz Usberti, Rafael C. S. Schouery	On the approximability and energy-flow modeling of the electric vehicle sharing problem.	CoRR	2023	DBLP DOI BibTeX RDF
16	Thomas Chen, Patricia Muñoz Ewald	Non-approximability of constructive global L2 minimizers by gradient descent in Deep Learning.	CoRR	2023	DBLP DOI BibTeX RDF
16	Sophia Saller, Jana Koehler, Andreas Karrenbauer	A Systematic Review of Approximability Results for Traveling Salesman Problems leveraging the TSP-T3CO Definition Scheme.	CoRR	2023	DBLP DOI BibTeX RDF
16	Amey Bhangale, Subhash Khot, Dor Minzer	On Approximability of Satisfiable k-CSPs: IV.	CoRR	2023	DBLP DOI BibTeX RDF
16	Henry L. Fleischmann, Surya Teja Gavva, Karthik C. S.	On Approximability of Steiner Tree in p-metrics.	CoRR	2023	DBLP DOI BibTeX RDF
16	Antoine Amarilli, Timothy van Bremen, Kuldeep S. Meel	Conjunctive Queries on Probabilistic Graphs: The Limits of Approximability.	CoRR	2023	DBLP DOI BibTeX RDF
16	Joshua Brakensiek, Neng Huang, Uri Zwick	Tight approximability of MAX 2-SAT and relatives, under UGC.	CoRR	2023	DBLP DOI BibTeX RDF
16	Anders Martinsson	On the approximability of the burning number.	CoRR	2023	DBLP DOI BibTeX RDF
16	Tobias Breiten, Bernhard Höveler	On the Approximability of Koopman-Based Operator Lyapunov Equations.	SIAM J. Control. Optim.	2023	DBLP DOI BibTeX RDF
16	Simon Foucart	Full recovery from point values: an optimal algorithm for Chebyshev approximability prior.	Adv. Comput. Math.	2023	DBLP DOI BibTeX RDF
16	Jayanth Bhargav, Mahsa Ghasemi, Shreyas Sundaram	On the Complexity and Approximability of Optimal Sensor Selection for Mixed-Observable Markov Decision Processes.	ACC	2023	DBLP DOI BibTeX RDF
16	Amey Bhangale, Subhash Khot, Dor Minzer	On Approximability of Satisfiable k-CSPs: III.	STOC	2023	DBLP DOI BibTeX RDF
16	Amey Bhangale, Subhash Khot, Dor Minzer	On Approximability of Satisfiable k-CSPs: II.	STOC	2023	DBLP DOI BibTeX RDF
16	Loay Mualem, Moran Feldman	Resolving the Approximability of Offline and Online Non-monotone DR-Submodular Maximization over General Convex Sets.	AISTATS	2023	DBLP BibTeX RDF
16	Martin Grohe, Venkatesan Guruswami, Dániel Marx, Stanislav Zivný	The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 22201).	Dagstuhl Reports	2022	DBLP DOI BibTeX RDF
16	Yen Hung Chen	Approximability results for the $p$-centdian and the converse centdian problems.	Discret. Math. Theor. Comput. Sci.	2022	DBLP DOI BibTeX RDF
16	Hiroshi Eto, Takehiro Ito, Zhilong Liu, Eiji Miyano	Approximability of the Distance Independent Set Problem on Regular Graphs and Planar Graphs.	IEICE Trans. Fundam. Electron. Commun. Comput. Sci.	2022	DBLP DOI BibTeX RDF
16	Chien-Chung Huang, Naonori Kakimura, Simon Mauras, Yuichi Yoshida	Approximability of Monotone Submodular Function Maximization under Cardinality and Matroid Constraints in the Streaming Model.	SIAM J. Discret. Math.	2022	DBLP DOI BibTeX RDF
16	Li-Hsuan Chen, Sun-Yuan Hsieh, Ling-Ju Hung, Ralf Klasing	On the Approximability of the Single Allocation p-Hub Center Problem with Parameterized Triangle Inequality.	Algorithmica	2022	DBLP DOI BibTeX RDF
16	Marinus Gottschau, Marilena Leichter	Minimum Hitting Set of Interval Bundles Problem: Computational Complexity and Approximability.	Algorithmica	2022	DBLP DOI BibTeX RDF
16	Antonis Antonopoulos, Eleni Bakali, Aggeliki Chalki, Aris Pagourtzis, Petros Pantavos, Stathis Zachos	Completeness, approximability and exponential time results for counting problems with easy decision version.	Theor. Comput. Sci.	2022	DBLP DOI BibTeX RDF
16	Xujin Chen, Minming Li, Changjun Wang, Chenhao Wang 0001, Mengqi Zhang, Yingchao Zhao 0001	Mechanisms for dual-role-facility location games: Truthfulness and approximability.	Theor. Comput. Sci.	2022	DBLP DOI BibTeX RDF
16	Louis Dublois, Tesshu Hanaka, Mehdi Khosravian Ghadikolaei, Michael Lampis, Nikolaos Melissinos	(In)approximability of maximum minimal FVS.	J. Comput. Syst. Sci.	2022	DBLP DOI BibTeX RDF
16	Amey Bhangale, Subhash Khot, Dor Minzer	On Approximability of Satisfiable k-CSPs: I.	Electron. Colloquium Comput. Complex.	2022	DBLP BibTeX RDF
16	Chi-Ning Chou, Alexander Golovnev, Amirbehshad Shahrasbi, Madhu Sudan 0001, Santhoshini Velusamy	Sketching Approximability of (Weak) Monarchy Predicates.	Electron. Colloquium Comput. Complex.	2022	DBLP BibTeX RDF
16	Karl Bringmann, Alejandro Cassis, Nick Fischer, Marvin Künnemann	A Structural Investigation of the Approximability of Polynomial-Time Problems.	CoRR	2022	DBLP DOI BibTeX RDF
16	Holger Boche, Rafael F. Schaefer, H. Vincent Poor	Algorithmic Computability and Approximability of Capacity-Achieving Input Distributions.	CoRR	2022	DBLP BibTeX RDF
16	Aleksa Stankovic	Some Results on Approximability of Minimum Sum Vertex Cover.	CoRR	2022	DBLP DOI BibTeX RDF
16	Marten Maack, Simon Pukrop, Anna Rodriguez Rasmussen	(In-)Approximability Results for Interval, Resource Restricted, and Low Rank Scheduling.	CoRR	2022	DBLP DOI BibTeX RDF
16	Simon Foucart	Full Recovery from Point Values: an Optimal Algorithm for Chebyshev Approximability Prior.	CoRR	2022	DBLP DOI BibTeX RDF
16	Chi-Ning Chou, Alexander Golovnev, Amirbehshad Shahrasbi, Madhu Sudan 0001, Santhoshini Velusamy	Sketching Approximability of (Weak) Monarchy Predicates.	CoRR	2022	DBLP DOI BibTeX RDF
16	Loay Mualem, Moran Feldman	Resolving the Approximability of Offline and Online Non-monotone DR-Submodular Maximization over General Convex Sets.	CoRR	2022	DBLP DOI BibTeX RDF
16	Suprovat Ghoshal, Euiwoong Lee	A Characterization of Approximability for Biased CSPs.	CoRR	2022	DBLP BibTeX RDF
16	Andrew James Turner, Ata Kabán	Approximability and Generalisation.	CoRR	2022	DBLP DOI BibTeX RDF
16	Péter Györgyi, Tamás Kis	New complexity and approximability results for minimizing the total weighted completion time on a single machine subject to non-renewable resource constraints.	Discret. Appl. Math.	2022	DBLP DOI BibTeX RDF
16	Markus Faustmann, Jens Markus Melenk, Maryam Parvizi	ℋ-matrix approximability of inverses of FEM matrices for the time-harmonic Maxwell equations.	Adv. Comput. Math.	2022	DBLP DOI BibTeX RDF
16	Alexandre M. Bayen, Jesse Goodman, Eugene Vinitsky	On the approximability of Time Disjoint Walks.	J. Comb. Optim.	2022	DBLP DOI BibTeX RDF
16	Piotr Wojciechowski 0002, K. Subramani 0001, Alvaro Velasquez, Matthew D. Williamson	On the Approximability of Path and Cycle Problems in Arc-Dependent Networks.	CALDAM	2022	DBLP DOI BibTeX RDF
16	Marten Maack, Simon Pukrop, Anna Rodriguez Rasmussen	(In-)Approximability Results for Interval, Resource Restricted, and Low Rank Scheduling.	ESA	2022	DBLP DOI BibTeX RDF
16	Karl Bringmann, Alejandro Cassis, Nick Fischer, Marvin Künnemann	A Structural Investigation of the Approximability of Polynomial-Time Problems.	ICALP	2022	DBLP DOI BibTeX RDF
16	Holger Boche, Rafael F. Schaefer, H. Vincent Poor	Capacity-Achieving Input Distributions: Algorithmic Computability and Approximability.	ISIT	2022	DBLP DOI BibTeX RDF
16	Yann Disser, David Weckbecker	Unified Greedy Approximability Beyond Submodular Maximization.	ISCO	2022	DBLP DOI BibTeX RDF
16	Elisabetta Punta	First and Second Order Sliding Mode Equivalent Signals and Practical Approximability in the Implementation.	VSS	2022	DBLP DOI BibTeX RDF
16	Yacine Al-Najjar, Walid Ben-Ameur, Jérémie Leguay	Approximability of Robust Network Design: The Directed Case.	STACS	2022	DBLP DOI BibTeX RDF
16	Antonios Antoniadis 0001, Sándor Kisfaludi-Bak, Bundit Laekhanukit, Daniel Vaz 0001	On the Approximability of the Traveling Salesman Problem with Line Neighborhoods.	SWAT	2022	DBLP DOI BibTeX RDF
16	Amey Bhangale, Subhash Khot, Dor Minzer	On approximability of satisfiable k-CSPs: I.	STOC	2022	DBLP DOI BibTeX RDF
16	Euiwoong Lee, Suprovat Ghoshal	A characterization of approximability for biased CSPs.	STOC	2022	DBLP DOI BibTeX RDF
16	Aleksa Stankovic	Some Results on Approximability of Minimum Sum Vertex Cover.	APPROX/RANDOM	2022	DBLP DOI BibTeX RDF
16	Chi-Ning Chou, Alexander Golovnev, Amirbehshad Shahrasbi, Madhu Sudan 0001, Santhoshini Velusamy	Sketching Approximability of (Weak) Monarchy Predicates.	APPROX/RANDOM	2022	DBLP DOI BibTeX RDF
16	Ivan Bliznets, Danil Sagunov	Two Generalizations of Proper Coloring: Hardness and Approximability.	COCOON	2022	DBLP DOI BibTeX RDF
16	Martin Frohn	On the approximability of the fixed-tree balanced minimum evolution problem.	Optim. Lett.	2021	DBLP DOI BibTeX RDF
16	Lintao Ye, Nathaniel Woodford, Sandip Roy 0002, Shreyas Sundaram	On the Complexity and Approximability of Optimal Sensor Selection and Attack for Kalman Filtering.	IEEE Trans. Autom. Control.	2021	DBLP DOI BibTeX RDF
16	Yuma Tamura, Takehiro Ito, Xiao Zhou 0001	Approximability of the independent feedback vertex set problem for bipartite graphs.	Theor. Comput. Sci.	2021	DBLP DOI BibTeX RDF
16	Yacine Al-Najjar, Walid Ben-Ameur, Jérémie Leguay	On the approximability of robust network design.	Theor. Comput. Sci.	2021	DBLP DOI BibTeX RDF
16	Yuichi Asahiro, Hiroshi Eto, Tesshu Hanaka, Guohui Lin, Eiji Miyano, Ippei Terabaru	Complexity and approximability of the happy set problem.	Theor. Comput. Sci.	2021	DBLP DOI BibTeX RDF
16	Steffen Borgwardt, Cornelius Brand, Andreas Emil Feldmann, Martin Koutecký	A note on the approximability of deepest-descent circuit steps.	Oper. Res. Lett.	2021	DBLP DOI BibTeX RDF
16	Vaneet Aggarwal, Tian Lan, Suresh Subramaniam 0001, Maotong Xu	On the Approximability of Related Machine Scheduling Under Arbitrary Precedence.	IEEE Trans. Netw. Serv. Manag.	2021	DBLP DOI BibTeX RDF
16	Christer Bäckström, Peter Jonsson, Sebastian Ordyniak	Cost-optimal Planning, Delete Relaxation, Approximability, and Heuristics.	J. Artif. Intell. Res.	2021	DBLP DOI BibTeX RDF
16	Chi-Ning Chou, Alexander Golovnev, Madhu Sudan 0001, Santhoshini Velusamy	Approximability of all finite CSPs in the dynamic streaming setting.	Electron. Colloquium Comput. Complex.	2021	DBLP BibTeX RDF
16	Chi-Ning Chou, Alexander Golovnev, Madhu Sudan 0001, Santhoshini Velusamy	Classification of the streaming approximability of Boolean CSPs.	Electron. Colloquium Comput. Complex.	2021	DBLP BibTeX RDF
16	Sounaka Mishra, B. Arjuna Krishna, Shijin Rajakrishnan	Approximability of open k-monopoly problems.	Theory Comput. Syst.	2021	DBLP DOI BibTeX RDF
16	Jihao Long, Lei Wu	Linear approximability of two-layer neural networks: A comprehensive analysis based on spectral decay.	CoRR	2021	DBLP BibTeX RDF
16	Théophile Chaumont-Frelet, Padtrick Vega	Frequency-explicit approximability estimates for time-harmonic Maxwell's equations.	CoRR	2021	DBLP BibTeX RDF
16	Marcelo Arenas, Pablo Barceló, Leopoldo E. Bertossi, Mikaël Monet	On the Complexity of SHAP-Score-Based Explanations: Tractability via Knowledge Compilation and Non-Approximability Results.	CoRR	2021	DBLP BibTeX RDF
16	Dimitris Fotakis 0001, Panagiotis Kostopanagiotis, Vasileios Nakos, Georgios Piliouras, Stratis Skoulakis	On the Approximability of Multistage Min-Sum Set Cover.	CoRR	2021	DBLP BibTeX RDF
16	Chi-Ning Chou, Alexander Golovnev, Madhu Sudan 0001, Santhoshini Velusamy	Approximability of all finite CSPs in the dynamic streaming setting.	CoRR	2021	DBLP BibTeX RDF
16	Markus Faustmann, Jens Markus Melenk, Maryam Parvizi	$\mathcal{H}$-matrix approximability of inverses of FEM matrices for the time-harmonic Maxwell equations.	CoRR	2021	DBLP BibTeX RDF
16	Joanna Boyland, Michael Hwang, Tarun Prasad, Noah Singer, Santhoshini Velusamy	Closed-form expressions for the sketching approximability of (some) symmetric Boolean CSPs.	CoRR	2021	DBLP BibTeX RDF
16	Chi-Ning Chou, Alexander Golovnev, Madhu Sudan 0001, Santhoshini Velusamy	Classification of the streaming approximability of Boolean CSPs.	CoRR	2021	DBLP BibTeX RDF
16	Jean Cardinal, Justin Dallant, John Iacono	Approximability of (Simultaneous) Class Cover for Boxes.	CoRR	2021	DBLP BibTeX RDF
16	Alba Muñoz, Fernando Rubio 0001	Evaluating genetic algorithms through the approximability hierarchy.	J. Comput. Sci.	2021	DBLP DOI BibTeX RDF
16	Simon Foucart	Instances of computational optimal recovery: Refined approximability models.	J. Complex.	2021	DBLP DOI BibTeX RDF
16	Martijn van Ee	Approximability of the dispersed p→-neighbor k-supplier problem.	Discret. Appl. Math.	2021	DBLP DOI BibTeX RDF
16	Spoorthy Gunda, Pallavi Jain 0001, Daniel Lokshtanov, Saket Saurabh 0001, Prafullkumar Tale	On the Parameterized Approximability of Contraction to Classes of Chordal Graphs.	ACM Trans. Comput. Theory	2021	DBLP DOI BibTeX RDF
16	Santiago Valdés Ravelo	Minimum constellation covers: hardness, approximability and polynomial cases.	J. Comb. Optim.	2021	DBLP DOI BibTeX RDF
16	Xianmin Liu, Yingshu Li, Jianzhong Li 0001, Yuqiang Feng	On the complexity and approximability of repair position selection problem.	J. Comb. Optim.	2021	DBLP DOI BibTeX RDF
16	Vincent Cohen-Addad, Karthik C. S., Euiwoong Lee	On Approximability of Clustering Problems Without Candidate Centers.	SODA	2021	DBLP DOI BibTeX RDF
16	Chi-Ning Chou, Alexander Golovnev, Madhu Sudan 0001, Santhoshini Velusamy	Approximability of all finite CSPs with linear sketches.	FOCS	2021	DBLP DOI BibTeX RDF