Search results for "approximability"

Hits ?▲	Authors	Title	Venue	Year	Link
16	Dimitris Fotakis 0001, Panagiotis Kostopanagiotis, Vasileios Nakos, Georgios Piliouras, Stratis Skoulakis	On the Approximability of Multistage Min-Sum Set Cover.	ICALP	2021	DBLP DOI BibTeX RDF
16	Jean Cardinal, Justin Dallant, John Iacono	Approximability of (Simultaneous) Class Cover for Boxes.	CCCG	2021	DBLP BibTeX RDF
16	Erwin Pesch, Katarzyna Anna Kuzmicz	Non-approximability of the single crane container transhipment problem.	Int. J. Prod. Res.	2020	DBLP DOI BibTeX RDF
16	S. Rasoul Etesami 0001	Complexity and Approximability of Optimal Resource Allocation and Nash Equilibrium over Networks.	SIAM J. Optim.	2020	DBLP DOI BibTeX RDF
16	Holger Boche, Rafael F. Schaefer, H. Vincent Poor	Shannon meets Turing: Non-computability and non-approximability of the finite state channel capacity.	Commun. Inf. Syst.	2020	DBLP DOI BibTeX RDF
16	Mahmood Ettehad, Simon Foucart	Approximability models and optimal system identification.	Math. Control. Signals Syst.	2020	DBLP DOI BibTeX RDF
16	Miriam Backens, Leslie Ann Goldberg	Holant Clones and the Approximability of Conservative Holant Problems.	ACM Trans. Algorithms	2020	DBLP DOI BibTeX RDF
16	Praveen Kalarickel Ramakrishnan, Mirco Raffetto	Well Posedness and Finite Element Approximability of Three-Dimensional Time-Harmonic Electromagnetic Problems Involving Rotating Axisymmetric Objects.	Symmetry	2020	DBLP DOI BibTeX RDF
16	Geoffrey Solano, Guillaume Blin, Mathieu Raffinot, Jhoirene B. Clemente, Jaime Caro	On the Approximability of the Minimum Weight $t$-partite Clique Problem.	J. Graph Algorithms Appl.	2020	DBLP DOI BibTeX RDF
16	Kaveh Khoshkhah, Mehdi Khosravian Ghadikolaei, Jérôme Monnot, Florian Sikora	Weighted Upper Edge Cover: Complexity and Approximability.	J. Graph Algorithms Appl.	2020	DBLP DOI BibTeX RDF
16	Michael Yu. Khachay, Katherine Neznakhina	Complexity and approximability of the Euclidean generalized traveling salesman problem in grid clusters.	Ann. Math. Artif. Intell.	2020	DBLP DOI BibTeX RDF
16	Refael Hassin, R. Ravi 0001, F. Sibel Salman, Danny Segev	The Approximability of Multiple Facility Location on Directed Networks with Random Arc Failures.	Algorithmica	2020	DBLP DOI BibTeX RDF
16	Robert Chiang, Kanstantsin Pashkovich	On the Approximability of the Stable Matching Problem with Ties of Size Two.	Algorithmica	2020	DBLP DOI BibTeX RDF
16	Yann Disser, David Weckbecker	Unified greedy approximability beyond submodular maximization.	CoRR	2020	DBLP 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.	CoRR	2020	DBLP 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.	CoRR	2020	DBLP BibTeX RDF
16	Natalie Collina, S. Matthew Weinberg	On the (in)-approximability of Bayesian Revenue Maximization for a Combinatorial Buyer.	CoRR	2020	DBLP 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.	CoRR	2020	DBLP 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.	CoRR	2020	DBLP BibTeX RDF
16	Vincent Cohen-Addad, Karthik C. S., Euiwoong Lee	On Approximability of Clustering Problems Without Candidate Centers.	CoRR	2020	DBLP BibTeX RDF
16	Steffen Borgwardt, Cornelius Brand, Andreas Emil Feldmann, Martin Koutecký	A Note on the Approximability of Deepest-Descent Circuit Steps.	CoRR	2020	DBLP BibTeX RDF
16	Eleni Bakali, Aggeliki Chalki, Aris Pagourtzis	Characterizations and approximability of hard counting classes below #P.	CoRR	2020	DBLP BibTeX RDF
16	Louis Dublois, Tesshu Hanaka, Mehdi Khosravian Ghadikolaei, Michael Lampis, Nikolaos Melissinos	(In)approximability of Maximum Minimal FVS.	CoRR	2020	DBLP BibTeX RDF
16	Simon Foucart	Instances of Computational Optimal Recovery: Refined Approximability Models.	CoRR	2020	DBLP BibTeX RDF
16	Holger Boche, Rafael F. Schaefer, H. Vincent Poor	Shannon Meets Turing: Non-Computability and Non-Approximability of the Finite State Channel Capacity.	CoRR	2020	DBLP BibTeX RDF
16	Maria-Florina Balcan, Tuomas Sandholm, Ellen Vitercik	Refined bounds for algorithm configuration: The knife-edge of dual class approximability.	CoRR	2020	DBLP BibTeX RDF
16	Ralph Abboud, Ismail Ilkan Ceylan, Radoslav Dimitrov	On the Approximability of Weighted Model Integration on DNF Structures.	CoRR	2020	DBLP BibTeX RDF
16	Yen Hung Chen	Approximability results for the p-centdian and the converse centdian problems.	CoRR	2020	DBLP BibTeX RDF
16	Jochen Könemann, Kanstantsin Pashkovich, Natig Tofigzade	On the Approximability of the Stable Matching Problem with Ties of Constant Size up to the Integrality Gap.	CoRR	2020	DBLP BibTeX RDF
16	Yacine Al-Najjar, Walid Ben-Ameur, Jeremie Leguay	On the Approximability of Robust Network Design.	CoRR	2020	DBLP BibTeX RDF
16	Chulhee Yun, Yin-Wen Chang, Srinadh Bhojanapalli, Ankit Singh Rawat, Sashank J. Reddi, Sanjiv Kumar	$O(n)$ Connections are Expressive Enough: Universal Approximability of Sparse Transformers.	CoRR	2020	DBLP BibTeX RDF
16	Mohammad Reza Kazemi 0001, Ali Mohades, Payam Khanteimouri	On approximability of minimum color-spanning ball in high dimensions.	Discret. Appl. Math.	2020	DBLP DOI BibTeX RDF
16	Cristina Bazgan, Ljiljana Brankovic, Katrin Casel, Henning Fernau	Domination chain: Characterisation, classical complexity, parameterised complexity and approximability.	Discret. Appl. Math.	2020	DBLP DOI BibTeX RDF
16	Louis Dublois, Tesshu Hanaka, Mehdi Khosravian Ghadikolaei, Michael Lampis, Nikolaos Melissinos	(In)approximability of Maximum Minimal FVS.	ISAAC	2020	DBLP DOI BibTeX RDF
16	Daniel Lokshtanov, M. S. Ramanujan 0001, Saket Saurabh 0001, Meirav Zehavi	Parameterized Complexity and Approximability of Directed Odd Cycle Transversal.	SODA	2020	DBLP DOI BibTeX RDF
16	Yuma Tamura, Takehiro Ito, Xiao Zhou 0001	Approximability of the Independent Feedback Vertex Set Problem for Bipartite Graphs.	WALCOM	2020	DBLP DOI BibTeX RDF
16	Eleni Bakali, Aggeliki Chalki, Aris Pagourtzis	Characterizations and Approximability of Hard Counting Classes Below $\#\mathsf {P}$.	TAMC	2020	DBLP DOI BibTeX RDF
16	Natalie Collina, S. Matthew Weinberg	On the (in-)approximability of Bayesian Revenue Maximization for a Combinatorial Buyer.	EC	2020	DBLP DOI BibTeX RDF
16	Peter Damaschke	Two Robots Patrolling on a Line: Integer Version and Approximability.	IWOCA	2020	DBLP DOI BibTeX RDF
16	Chulhee Yun, Yin-Wen Chang, Srinadh Bhojanapalli, Ankit Singh Rawat, Sashank J. Reddi, Sanjiv Kumar	O(n) Connections are Expressive Enough: Universal Approximability of Sparse Transformers.	NeurIPS	2020	DBLP BibTeX RDF
16	Ralph Abboud, Ismail Ilkan Ceylan, Radoslav Dimitrov	On the Approximability of Weighted Model Integration on DNF Structures.	KR	2020	DBLP DOI BibTeX RDF
16	Neng Huang, Aaron Potechin	On the Approximability of Presidential Type Predicates.	APPROX-RANDOM	2020	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.	APPROX-RANDOM	2020	DBLP DOI BibTeX RDF
16	Vincent Fagnon, Imed Kacem, Giorgio Lucarelli, Bertrand Simon 0001	Scheduling on Hybrid Platforms: Improved Approximability Window.	LATIN	2020	DBLP DOI BibTeX RDF
16	Yuichi Asahiro, Hiroshi Eto, Tesshu Hanaka, Guohui Lin, Eiji Miyano, Ippei Terabaru	Graph Classes and Approximability of the Happy Set Problem.	COCOON	2020	DBLP DOI BibTeX RDF
16	Jin-Yi Cai, Tianyu Liu 0002, Pinyan Lu, Jing Yu	Approximability of the Eight-Vertex Model.	CCC	2020	DBLP DOI BibTeX RDF
16	Maria-Florina Balcan, Tuomas Sandholm, Ellen Vitercik	Refined bounds for algorithm configuration: The knife-edge of dual class approximability.	ICML	2020	DBLP BibTeX RDF
16	Raghunath Reddy Madireddy, Apurva Mudgal	Approximability and hardness of geometric hitting set with axis-parallel rectangles.	Inf. Process. Lett.	2019	DBLP DOI BibTeX RDF
16	Paz Carmi, Anil Maheshwari, Saeed Mehrabi 0001, Luís Fernando Schultz Xavier da Silveira	Approximability of covering cells with line segments.	Theor. Comput. Sci.	2019	DBLP DOI BibTeX RDF
16	Tung-Wei Kuo	On the approximability and hardness of the minimum connected dominating set with routing cost constraint.	Theor. Comput. Sci.	2019	DBLP DOI BibTeX RDF
16	Kaveh Khoshkhah, Mehdi Khosravian Ghadikolaei, Jérôme Monnot, Dirk Oliver Theis	Complexity and approximability of extended Spanning Star Forest problems in general and complete graphs.	Theor. Comput. Sci.	2019	DBLP DOI BibTeX RDF
16	Neng Huang, Aaron Potechin	On the Approximability of Presidential Type Predicates.	CoRR	2019	DBLP BibTeX RDF
16	Vincent Fagnon, Imed Kacem, Giorgio Lucarelli, Bertrand Simon 0001	Scheduling on Hybrid Platforms: Improved Approximability Window.	CoRR	2019	DBLP BibTeX RDF
16	Ioannis Katsikarelis, Michael Lampis, Vangelis Th. Paschos	Improved (In-)Approximability Bounds for d-Scattered Set.	CoRR	2019	DBLP BibTeX RDF
16	Katharina Dannenberg, Jesper Jansson 0001, Andrzej Lingas, Eva-Marta Lundell	The approximability of maximum rooted triplets consistency with fan triplets and forbidden triplets.	Discret. Appl. Math.	2019	DBLP DOI BibTeX RDF
16	Diogo Poças, Jeffery I. Zucker	Approximability in the GPAC.	Log. Methods Comput. Sci.	2019	DBLP DOI BibTeX RDF
16	Grant Schoenebeck, Biaoshuai Tao	Beyond Worst-case (In)approximability of Nonsubmodular Influence Maximization.	ACM Trans. Comput. Theory	2019	DBLP DOI BibTeX RDF
16	Michael Karkulik, Jens Markus Melenk	H-matrix approximability of inverses of discretizations of the fractional Laplacian.	Adv. Comput. Math.	2019	DBLP DOI BibTeX RDF
16	Wei Yu 0011, Zhaohui Liu 0001	Better approximability results for min-max tree/cycle/path cover problems.	J. Comb. Optim.	2019	DBLP DOI BibTeX RDF
16	Kameng Nip, Zhenbo Wang	On the approximability of the two-phase knapsack problem.	J. Comb. Optim.	2019	DBLP DOI BibTeX RDF
16	Mattia D'Emidio, Luca Forlizzi, Daniele Frigioni, Stefano Leucci 0001, Guido Proietti	Hardness, approximability, and fixed-parameter tractability of the clustered shortest-path tree problem.	J. Comb. Optim.	2019	DBLP DOI BibTeX RDF
16	Jin-Yi Cai, Tianyu Liu 0002, Pinyan Lu	Approximability of the Six-vertex Model.	SODA	2019	DBLP DOI BibTeX RDF
16	Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, Madhur Tulsiani	Approximability of p → q Matrix Norms: Generalized Krivine Rounding and Hypercontractive Hardness.	SODA	2019	DBLP DOI BibTeX RDF
16	Kaveh Khoshkhah, Mehdi Khosravian Ghadikolaei, Jérôme Monnot, Florian Sikora	Weighted Upper Edge Cover: Complexity and Approximability.	WALCOM	2019	DBLP DOI BibTeX RDF
16	Kaveh Khoshkhah, Mehdi Khosravian Ghadikolaei, Jérôme Monnot, Florian Sikora	Correction to: Weighted Upper Edge Cover: Complexity and Approximability.	WALCOM	2019	DBLP DOI BibTeX RDF
16	Yaonan Jin, Weian Li, Qi Qi 0003	On the Approximability of Simple Mechanisms for MHR Distributions.	WINE	2019	DBLP DOI BibTeX RDF
16	Huanyang Zheng, Ning Wang 0018, Jie Wu 0001	Non-Submodularity and Approximability: Influence Maximization in Online Social Networks.	WOWMOM	2019	DBLP DOI BibTeX RDF
16	Yousef M. Alhamdan, Alexander V. Kononov	Approximability and Inapproximability for Maximum k-Edge-Colored Clustering Problem.	CSR	2019	DBLP DOI BibTeX RDF
16	Ioannis Katsikarelis, Michael Lampis, Vangelis Th. Paschos	Improved (In-)Approximability Bounds for d-Scattered Set.	WAOA	2019	DBLP DOI BibTeX RDF
16	Yu Bai 0017, Tengyu Ma 0001, Andrej Risteski	Approximability of Discriminators Implies Diversity in GANs.	ICLR (Poster)	2019	DBLP BibTeX RDF
16	Yukun Ding, Jinglan Liu, Jinjun Xiong, Yiyu Shi 0001	On the Universal Approximability and Complexity Bounds of Quantized ReLU Neural Networks.	ICLR (Poster)	2019	DBLP BibTeX RDF
16	Majid Khonji, Ashkan Jasour, Brian C. Williams	Approximability of Constant-horizon Constrained POMDP.	IJCAI	2019	DBLP DOI BibTeX RDF
16	Ali Aouad, Vivek F. Farias, Retsef Levi, Danny Segev	The Approximability of Assortment Optimization Under Ranking Preferences.	Oper. Res.	2018	DBLP DOI BibTeX RDF
16	Martin Grohe, Venkatesan Guruswami, Stanislav Zivný	The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 18231).	Dagstuhl Reports	2018	DBLP DOI BibTeX RDF
16	Samuel Fiorini, R. Krithika 0001, N. S. Narayanaswamy, Venkatesh Raman 0001	Approximability of Clique Transversal in Perfect Graphs.	Algorithmica	2018	DBLP DOI BibTeX RDF
16	Dimitri Watel, Alain Faye	Taxi-sharing: Parameterized complexity and approximability of the dial-a-ride problem with money as an incentive.	Theor. Comput. Sci.	2018	DBLP DOI BibTeX RDF
16	Li-Hsuan Chen, Dun-Wei Cheng, Sun-Yuan Hsieh, Ling-Ju Hung, Ralf Klasing, Chia-Wei Lee, Bang Ye Wu	Approximability and inapproximability of the star p-hub center problem with parameterized triangle inequality.	J. Comput. Syst. Sci.	2018	DBLP DOI BibTeX RDF
16	Felix Bauckholt, Kanstantsin Pashkovich, Laura Sanità	On the approximability of the stable marriage problem with one-sided ties.	CoRR	2018	DBLP BibTeX RDF
16	Alexandre M. Bayen, Jesse Goodman, Eugene Vinitsky	On the Approximability of Time Disjoint Walks.	CoRR	2018	DBLP BibTeX RDF
16	Flavien Breuvart	Refining Properties of Filter Models: Sensibility, Approximability and Reducibility.	CoRR	2018	DBLP BibTeX RDF
16	Paz Carmi, Anil Maheshwari, Saeed Mehrabi 0001, Luís Fernando Schultz Xavier da Silveira	Approximability of Covering Cells with Line Segments.	CoRR	2018	DBLP BibTeX RDF
16	Jin-Yi Cai, Tianyu Liu 0002, Pinyan Lu, Jing Yu	Approximability of the Eight-vertex Model.	CoRR	2018	DBLP BibTeX RDF
16	Miriam Backens, Leslie Ann Goldberg	Holant clones and the approximability of conservative holant problems.	CoRR	2018	DBLP BibTeX RDF
16	Yu Bai 0017, Tengyu Ma 0001, Andrej Risteski	Approximability of Discriminators Implies Diversity in GANs.	CoRR	2018	DBLP BibTeX RDF
16	Riccardo Dondi, Giancarlo Mauri, Florian Sikora, Italo Zoppis	Covering with Clubs: Complexity and Approximability.	CoRR	2018	DBLP BibTeX RDF
16	Kaveh Khoshkhah, Mehdi Khosravian Ghadikolaei, Jérôme Monnot, Florian Sikora	Weighted Upper Edge Cover: Complexity and Approximability.	CoRR	2018	DBLP BibTeX RDF
16	Robert Chiang, Kanstantsin Pashkovich	On the approximability of the stable matching problem with ties of size two.	CoRR	2018	DBLP BibTeX RDF
16	Diogo Poças, Jeffery I. Zucker	Approximability in the GPAC.	CoRR	2018	DBLP BibTeX RDF
16	Mattia D'Emidio, Luca Forlizzi, Daniele Frigioni, Stefano Leucci 0001, Guido Proietti	Hardness, Approximability, and Fixed-Parameter Tractability of the Clustered Shortest-Path Tree Problem.	CoRR	2018	DBLP BibTeX RDF
16	Yukun Ding, Jinglan Liu, Yiyu Shi 0001	On the Universal Approximability of Quantized ReLU Neural Networks.	CoRR	2018	DBLP BibTeX RDF
16	Borzou Rostami, André B. Chassein, Michael Hopf, Davide Frey, Christoph Buchheim, Federico Malucelli, Marc Goerigk	The quadratic shortest path problem: complexity, approximability, and solution methods.	Eur. J. Oper. Res.	2018	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.	Discret. Optim.	2018	DBLP DOI BibTeX RDF
16	Marin Bougeret, Guillerme Duvillié, Rodolphe Giroudeau	Approximability and exact resolution of the multidimensional binary vector assignment problem.	J. Comb. Optim.	2018	DBLP DOI BibTeX RDF
16	Giorgio Ausiello, Vangelis Th. Paschos	Reductions That Preserve Approximability.	Handbook of Approximation Algorithms and Metaheuristics (1)	2018	DBLP DOI BibTeX RDF
16	Zdenek Dvorák 0001, Ken-ichi Kawarabayashi	Additive Non-Approximability of Chromatic Number in Proper Minor-Closed Classes.	ICALP	2018	DBLP DOI BibTeX RDF
16	Lintao Ye, Sandip Roy 0002, Shreyas Sundaram	On the Complexity and Approximability of Optimal Sensor Selection for Kalman Filtering.	ACC	2018	DBLP DOI BibTeX RDF
16	Holger Boche, Volker Pohl	On the Approximability of the Hilbert Transform.	ISIT	2018	DBLP DOI BibTeX RDF
16	Tung-Wei Kuo	On the Approximability and Hardness of the Minimum Connected Dominating Set with Routing Cost Constraint.	ALGOSENSORS	2018	DBLP DOI BibTeX RDF
16	Riccardo Dondi, Giancarlo Mauri, Florian Sikora, Italo Zoppis	Covering with Clubs: Complexity and Approximability.	IWOCA	2018	DBLP DOI BibTeX RDF
16	Alexandre M. Bayen, Jesse Goodman, Eugene Vinitsky	On the Approximability of Time Disjoint Walks.	COCOA	2018	DBLP DOI BibTeX RDF