Search results for "Apx"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
79	Sounaka Mishra, Kripasindhu Sikdar	On the Hardness of Approximating Some NP-optimization Problems Related to Minimum Linear Ordering Problem.	IFIP TCS	2000	DBLP DOI BibTeX RDF	NP-optimization problems, Minimaximal and maximinimal NP-optimization problems, L-reduction, Approximation algorithms, Hardness of approximation, APX-hardness
79	Sascha Ott	Lower Bounds for Approximating Shortest Superstrings over an Alphabet of Size 2.	WG	1999	DBLP DOI BibTeX RDF	Superstrings, lower bounds, approximability, APX-hardness
79	Pierluigi Crescenzi, Luca Trevisan	On Approximation Scheme Preserving Reducability and Its Applications.	FSTTCS	1994	DBLP DOI BibTeX RDF
67	Cristina Bazgan, Bruno Escoffier, Vangelis Th. Paschos	Poly-APX- and PTAS-Completeness in Standard and Differential Approximation.	ISAAC	2004	DBLP DOI BibTeX RDF
54	Omid Amini, David Peleg, Stéphane Pérennes, Ignasi Sau, Saket Saurabh 0001	Degree-Constrained Subgraph Problems: Hardness and Approximation Results.	WAOA	2008	DBLP DOI BibTeX RDF	Degree-Constrained Subgraphs, Apx, Excluded Minor, Approximation Algorithms, Hardness of Approximation, PTAS
54	Euripides Markou, Stathis Zachos, Christodoulos Fragoudakis	Maximizing the Guarded Boundary of an Art Gallery Is APX-Complete.	CIAC	2003	DBLP DOI BibTeX RDF
53	Omid Amini, Stéphane Pérennes, Ignasi Sau	Hardness and Approximation of Traffic Grooming.	ISAAC	2007	DBLP DOI BibTeX RDF	SONET ADM, Approximation Algorithms, Optical Networks, PTAS, inapproximability, Traffic Grooming, APX-hardness
41	Magnús M. Halldórsson, Roger Wattenhofer	Wireless Communication Is in APX.	ICALP (1)	2009	DBLP DOI BibTeX RDF
41	Chienwen Wu	Mining Top-K Frequent Closed Itemsets Is Not in APX.	PAKDD	2006	DBLP DOI BibTeX RDF
40	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
40	Bruno Escoffier, Laurent Gourvès, Jérôme Monnot	Complexity and Approximation Results for the Connected Vertex Cover Problem.	WG	2007	DBLP DOI BibTeX RDF	Connected vertex cover, APX-complete, approximation algorithm, planar graphs, bipartite graphs, chordal graphs
39	Christopher Ré, Dan Suciu	The trichotomy of HAVING queries on a probabilistic database.	VLDB J.	2009	DBLP DOI BibTeX RDF	Safe plans, Probabilistic databases, Query evaluation, Semirings, Sampling algorithms
39	Bernhard Fuchs	On the Hardness of Range Assignment Problems.	CIAC	2006	DBLP DOI BibTeX RDF
28	Salomon Bendayan, Joseph Cheriyan, Kevin K. H. Cheung	Unconstrained traveling tournament problem is APX-complete.	Oper. Res. Lett.	2023	DBLP DOI BibTeX RDF
28	Jingyang Zhao 0001, Mingyu Xiao 0001	The APX-hardness of the Traveling Tournament Problem.	CoRR	2023	DBLP DOI BibTeX RDF
28	Debajyoti Mondal, Angelin Jemima Rajasingh, N. Parthiban, Indra Rajasingh	APX-hardness and approximation for the k-burning number problem.	Theor. Comput. Sci.	2022	DBLP DOI BibTeX RDF
28	Salomon Bendayan, Joseph Cheriyan, Kevin K. H. Cheung	Unconstrained Traveling Tournament Problem is APX-complete.	CoRR	2022	DBLP DOI BibTeX RDF
28	Mayank Chaturvedi, Bengt J. Nilsson	APX-Hardness of the Minimum Vision Points Problem.	CoRR	2022	DBLP DOI BibTeX RDF
28	Arthur Lee, Bruce Xu	Classifying Approximation Algorithms: Understanding the APX Complexity Class.	CoRR	2021	DBLP BibTeX RDF
28	Debajyoti Mondal, N. Parthiban, V. Kavitha 0003, Indra Rajasingh	APX-Hardness and Approximation for the k-Burning Number Problem.	WALCOM	2021	DBLP DOI BibTeX RDF
28	Anne Condon, Monir Hajiaghayi, Chris Thachuk	Predicting Minimum Free Energy Structures of Multi-Stranded Nucleic Acid Complexes Is APX-Hard.	DNA	2021	DBLP DOI BibTeX RDF
28	Bogdan Armaselu	An APX for the Maximum-Profit Routing Problem with Variable Supply.	CoRR	2020	DBLP BibTeX RDF
28	Debajyoti Mondal, N. Parthiban, V. Kavitha 0003, Indra Rajasingh	APX-Hardness and Approximation for the k-Burning Number Problem.	CoRR	2020	DBLP BibTeX RDF
28	Jen Beeston, Christopher Power, Paul A. Cairns, Mark C. Barlet	Accessible Player Experiences (APX): The Players.	ICCHP (1)	2018	DBLP DOI BibTeX RDF
28	Euiwoong Lee	APX-hardness of maximizing Nash social welfare with indivisible items.	Inf. Process. Lett.	2017	DBLP DOI BibTeX RDF
28	Euiwoong Lee	APX-Hardness of Maximizing Nash Social Welfare with Indivisible Items.	CoRR	2015	DBLP BibTeX RDF
28	N. S. Narayanaswamy, Swapnoneel Roy	Block Sorting Is APX-Hard.	CIAC	2015	DBLP DOI BibTeX RDF
28	Timothy M. Chan, Elyot Grant	Exact algorithms and APX-hardness results for geometric packing and covering problems.	Comput. Geom.	2014	DBLP DOI BibTeX RDF
28	Alexander Pilz	Flip distance between triangulations of a planar point set is APX-hard.	Comput. Geom.	2014	DBLP DOI BibTeX RDF
28	Nabil H. Mustafa, Rajiv Raman 0001, Saurabh Ray	Settling the APX-Hardness Status for Geometric Set Cover.	FOCS	2014	DBLP DOI BibTeX RDF
28	Lei Chen 0007, Weiming Zeng, Changhong Lu	NP-completeness and APX-completeness of restrained domination in graphs.	Theor. Comput. Sci.	2012	DBLP DOI BibTeX RDF
28	Paul S. Bonsma	Max-leaves spanning tree is APX-hard for cubic graphs.	J. Discrete Algorithms	2012	DBLP DOI BibTeX RDF
28	Minghui Jiang 0001	Clique in 3-track interval graphs is APX-hard	CoRR	2012	DBLP BibTeX RDF
28	Elyot Grant, Timothy M. Chan	Exact Algorithms and APX-Hardness Results for Geometric Set Cover.	CCCG	2011	DBLP BibTeX RDF
28	Raffaele Bruno 0001, Vania Conan, Stéphane Rousseau	Maximizing the number of accepted flows in TDMA-based wireless ad hoc networks is APX-complete	CoRR	2009	DBLP BibTeX RDF
28	Paul S. Bonsma	Max-Leaves Spanning Tree is APX-hard for Cubic Graphs	CoRR	2009	DBLP BibTeX RDF
28	Christodoulos Fragoudakis, Euripides Markou, Stathis Zachos	Maximizing the guarded boundary of an Art Gallery is APX-complete.	Comput. Geom.	2007	DBLP DOI BibTeX RDF
28	Paola Bonizzoni, Gianluca Della Vedova, Riccardo Dondi	Anonymizing Binary Tables is APX-hard	CoRR	2007	DBLP BibTeX RDF
28	Mirela Damian, Sriram V. Pemmaraju	APX-hardness of domination problems in circle graphs.	Inf. Process. Lett.	2006	DBLP DOI BibTeX RDF
28	Bruno Escoffier, Vangelis Th. Paschos	Completeness in approximation classes beyond APX.	Theor. Comput. Sci.	2006	DBLP DOI BibTeX RDF
28	Cristina Bazgan, Bruno Escoffier, Vangelis Th. Paschos	Completeness in standard and differential approximation classes: Poly-(D)APX- and (D)PTAS-completeness.	Theor. Comput. Sci.	2005	DBLP DOI BibTeX RDF
28	Vineet Bafna, Sorin Istrail, Giuseppe Lancia, Romeo Rizzi	Polynomial and APX-hard cases of the individual haplotyping problem.	Theor. Comput. Sci.	2005	DBLP DOI BibTeX RDF
28	Björn Brodén, Mikael Hammar, Bengt J. Nilsson	Guarding lines and 2-link polygons is apx-hard.	CCCG	2001	DBLP BibTeX RDF
28	Paola Alimonti, Viggo Kann	Some APX-completeness results for cubic graphs.	Theor. Comput. Sci.	2000	DBLP DOI BibTeX RDF
28	Viggo Kann, Jens Lagergren, Alessandro Panconesi	Approximability of Maximum Splitting of k-Sets and Some Other Apx-Complete Problems.	Inf. Process. Lett.	1996	DBLP DOI BibTeX RDF
27	Maxim Sviridenko, Gerhard J. Woeginger	Approximability and in-approximability results for no-wait shop scheduling.	FOCS	2000	DBLP DOI BibTeX RDF	in-approximability results, no-wait shop scheduling, makespan criterion, computational complexity, approximability, processor scheduling, polynomial time approximation scheme, polynomial approximation, APX-hard
26	Rohit Khandekar, Tracy Kimbrel, Konstantin Makarychev, Maxim Sviridenko	On Hardness of Pricing Items for Single-Minded Bidders.	APPROX-RANDOM	2009	DBLP DOI BibTeX RDF
26	Basile Couëtoux, Laurent Gourvès, Jérôme Monnot, Orestis Telelis	On Labeled Traveling Salesman Problems.	ISAAC	2008	DBLP DOI BibTeX RDF
26	Rudi Cilibrasi, Leo van Iersel, Steven Kelk, John Tromp	The Complexity of the Single Individual SNP Haplotyping Problem.	Algorithmica	2007	DBLP DOI BibTeX RDF
26	Gaurav Sharma 0002, Ness B. Shroff, Ravi R. Mazumdar	Maximum Weighted Matching with Interference Constraints.	PerCom Workshops	2006	DBLP DOI BibTeX RDF
26	Nikhil Bansal 0001, Amit Chakrabarti, Amir Epstein, Baruch Schieber	A quasi-PTAS for unsplittable flow on line graphs.	STOC	2006	DBLP DOI BibTeX RDF	scheduling, approximation algorithms, resource allocation, approximation scheme, unsplittable flow
26	Khaled M. Elbassioni, Irit Katriel, Martin Kutz, Meena Mahajan	Simultaneous Matchings.	ISAAC	2005	DBLP DOI BibTeX RDF
26	Miroslav Chlebík, Janka Chlebíková	Approximation hardness of optimization problems in intersection graphs of d-dimensional boxes.	SODA	2005	DBLP BibTeX RDF
26	Moses Charikar, Venkatesan Guruswami, Anthony Wirth	Clustering with Qualitative Information.	FOCS	2003	DBLP DOI BibTeX RDF
26	Giorgio Ausiello, Cristina Bazgan, Marc Demange, Vangelis Th. Paschos	Completeness in Differential Approximation Classes.	MFCS	2003	DBLP DOI BibTeX RDF
26	Hans-Joachim Böckenhauer, Dirk Bongartz, Juraj Hromkovic, Ralf Klasing, Guido Proietti, Sebastian Seibert, Walter Unger	On the Hardness of Constructing Minimal 2-Connected Spanning Subgraphs in Complete Graphs with Sharpened Triangle Inequality.	FSTTCS	2002	DBLP DOI BibTeX RDF	minimum-cost biconnected spanning subgraph, Approximation algorithm, inapproximability, augmentation
26	David Fernández-Baca, Jens Lagergren	On the Approximability of the Steiner Tree Problem in Phylogeny.	ISAAC	1996	DBLP DOI BibTeX RDF
26	James O. Bondi	A microcoded real-time executive for numeric support nodes distributed within embedded networks.	MICRO	1988	DBLP BibTeX RDF
13	Michael Lampis, Valia Mitsou	The Ferry Cover Problem.	Theory Comput. Syst.	2009	DBLP DOI BibTeX RDF	Wolf-goat-cabbage puzzle, Approximation algorithms, Graph algorithms, Vertex cover, Transportation problems
13	Stefano Benati, Romeo Rizzi	The optimal statistical median of a convex set of arrays.	J. Glob. Optim.	2009	DBLP DOI BibTeX RDF	Median optimization, Statistical median and quantile optimization, Branch&bound algorithms, Global optimization, Robust statistics
13	Minghui Jiang 0001	Inapproximability of Maximal Strip Recovery.	ISAAC	2009	DBLP DOI BibTeX RDF
13	Laurent Bulteau, Guillaume Fertin, Irena Rusu	Maximal Strip Recovery Problem with Gaps: Hardness and Approximation Algorithms.	ISAAC	2009	DBLP DOI BibTeX RDF	comparative maps, genome comparison, synteny blocks, approximation algorithms, algorithmic complexity
13	Cristina Bazgan, Basile Couëtoux, Zsolt Tuza	Covering a Graph with a Constrained Forest (Extended Abstract).	ISAAC	2009	DBLP DOI BibTeX RDF
13	Khaled M. Elbassioni, Rajiv Raman 0001, Saurabh Ray, René Sitters	On Profit-Maximizing Pricing for the Highway and Tollbooth Problems.	SAGT	2009	DBLP DOI BibTeX RDF
13	Riccardo Dondi, Guillaume Fertin, Stéphane Vialette	Maximum Motif Problem in Vertex-Colored Graphs.	CPM	2009	DBLP DOI BibTeX RDF
13	Yossi Azar, Benjamin E. Birnbaum, Anna R. Karlin, C. Thach Nguyen	On Revenue Maximization in Second-Price Ad Auctions.	ESA	2009	DBLP DOI BibTeX RDF
13	Eric McDermid	A 3/2-Approximation Algorithm for General Stable Marriage.	ICALP (1)	2009	DBLP DOI BibTeX RDF
13	Nir Ailon, Edo Liberty	Correlation Clustering Revisited: The "True" Cost of Error Minimization Problems.	ICALP (1)	2009	DBLP DOI BibTeX RDF
13	Marek Cygan, Marcin Pilipczuk	Exact and Approximate Bandwidth.	ICALP (1)	2009	DBLP DOI BibTeX RDF
13	Yossi Azar, Aleksander Madry, Thomas Moscibroda, Debmalya Panigrahi, Aravind Srinivasan	Maximum Bipartite Flow in Networks with Adaptive Channel Width.	ICALP (2)	2009	DBLP DOI BibTeX RDF
13	Li Liu 0001, Hao Li, Junling Wang, Lian Li 0003, Caihong Li	Heuristics for Mobile Object Tracking Problem in Wireless Sensor Networks.	FAW	2009	DBLP DOI BibTeX RDF
13	Paola Bonizzoni, Gianluca Della Vedova, Riccardo Dondi	The k-Anonymity Problem Is Hard.	FCT	2009	DBLP DOI BibTeX RDF
13	Piotr Berman, Bhaskar DasGupta, Marek Karpinski	Approximating Transitive Reductions for Directed Networks.	WADS	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	Ashkan Aazami, Joseph Cheriyan, Krishnam Raju Jampani	Approximation Algorithms and Hardness Results for Packing Element-Disjoint Steiner Trees in Planar Graphs.	APPROX-RANDOM	2009	DBLP DOI BibTeX RDF
13	John Abraham, Zhixiang Chen 0001, Richard H. Fowler, Bin Fu, Binhai Zhu	On the Approximability of Some Haplotyping Problems.	AAIM	2009	DBLP DOI BibTeX RDF
13	Tim Nonner, Alexander Souza	Latency Constrained Aggregation in Chain Networks Admits a PTAS.	AAIM	2009	DBLP DOI BibTeX RDF
13	Xin Chen 0037, Lan Liu 0001, Zheng Liu, Tao Jiang 0001	On the minimum common integer partition problem.	ACM Trans. Algorithms	2008	DBLP DOI BibTeX RDF	approximation algorithm, combinatorial optimization, NP-hard, computational biology, Subset sum, integer partition
13	Vladimir G. Deineko, Peter Jonsson, Mikael Klasson, Andrei A. Krokhin	The approximability of MAX CSP with fixed-value constraints.	J. ACM	2008	DBLP DOI BibTeX RDF	Complexity of approximation, maximum constraint satisfaction, dichotomy, Monge properties, supermodularity
13	Adrian Kosowski, Alfredo Navarra, Maria Cristina Pinotti	Connectivity in Multi-interface Networks.	TGC	2008	DBLP DOI BibTeX RDF	multi-interface network, approximation algorithm, wireless network, Energy saving
13	Magnús M. Halldórsson, Guy Kortsarz, Maxim Sviridenko	Min Sum Edge Coloring in Multigraphs Via Configuration LP.	IPCO	2008	DBLP DOI BibTeX RDF	Edge Scheduling, Configuration LP, Approximation Algorithms
13	Rohit Khandekar, Guy Kortsarz, Vahab S. Mirrokni, Mohammad R. Salavatipour	Two-Stage Robust Network Design with Exponential Scenarios.	ESA	2008	DBLP DOI BibTeX RDF
13	René A. Sitters	Approximability of Average Completion Time Scheduling on Unrelated Machines.	ESA	2008	DBLP DOI BibTeX RDF
13	Yossi Azar, Benjamin E. Birnbaum, Anna R. Karlin, Claire Mathieu, C. Thach Nguyen	Improved Approximation Algorithms for Budgeted Allocations.	ICALP (1)	2008	DBLP DOI BibTeX RDF
13	Ioannis Caragiannis, Gianpiero Monaco	A 6/5-Approximation Algorithm for the Maximum 3-Cover Problem.	MFCS	2008	DBLP DOI BibTeX RDF
13	Ning Chen 0005, Arpita Ghosh, Sergei Vassilvitskii	Optimal envy-free pricing with metric substitutability.	EC	2008	DBLP DOI BibTeX RDF	envy-free pricing, algorithms
13	Hans L. Bodlaender, Richard B. Tan, Thomas C. van Dijk, Jan van Leeuwen	Integer Maximum Flow in Wireless Sensor Networks with Energy Constraint.	SWAT	2008	DBLP DOI BibTeX RDF
13	Thomas Erlebach, Erik Jan van Leeuwen	Domination in Geometric Intersection Graphs.	LATIN	2008	DBLP DOI BibTeX RDF
13	Hans-Joachim Böckenhauer, Juraj Hromkovic, Tobias Mömke, Peter Widmayer	On the Hardness of Reoptimization.	SOFSEM	2008	DBLP DOI BibTeX RDF	reoptimization, approximation algorithms, inapproximability
13	Eui-woong Lee, David Buchfuhrer, Lachlan L. H. Andrew, Ao Tang, Steven H. Low	Progress on pricing with peering.	CISS	2008	DBLP DOI BibTeX RDF
13	Michael Krivelevich, Zeev Nutov, Mohammad R. Salavatipour, Jacques Verstraëte, Raphael Yuster	Approximation algorithms and hardness results for cycle packing problems.	ACM Trans. Algorithms	2007	DBLP DOI BibTeX RDF	Cycle packing, edge-disjoint, approximation algorithms, hardness of approximation, integrality gap
13	Paola Bonizzoni, Gianluca Della Vedova, Riccardo Dondi, Guillaume Fertin, Raffaella Rizzi, Stéphane Vialette	Exemplar Longest Common Subsequence.	IEEE ACM Trans. Comput. Biol. Bioinform.	2007	DBLP DOI BibTeX RDF	combinatorial algorithms, comparative genomics, Longest common subsequence, algorithm design and analysis, analysis of algorithms and problem complexity
13	Lap Chi Lau	An Approximate Max-Steiner-Tree-Packing Min-Steiner-Cut Theorem*.	Comb.	2007	DBLP DOI BibTeX RDF	Mathematics Subject Classification (2000): 05C05, 68R10, 05C70, 68W25, 05C40
13	Joseph Naor, Hadas Shachnai, Tami Tamir	Real-Time Scheduling with a Budget.	Algorithmica	2007	DBLP DOI BibTeX RDF
13	Luca Allulli, Roberto Baldoni, Luigi Laura, Sara Tucci Piergiovanni	On the Complexity of Removing Z-Cycles from a Checkpoints and Communication Pattern.	IEEE Trans. Computers	2007	DBLP DOI BibTeX RDF	Z-cycles, progressive retry, online versus offline analysis, Distributed computing, checkpointing, competitive analysis, NP-complete problem
13	Gregorio Malajovich, Klaus Meer	Computing Minimal Multi-Homogeneous Bezout Numbers Is Hard.	Theory Comput. Syst.	2007	DBLP DOI BibTeX RDF
13	Toshimasa Ishii	Greedy Approximation for Source Location Problem with Vertex-Connectivity Requirements in Undirected Graphs.	ISAAC	2007	DBLP DOI BibTeX RDF
13	Kazuo Iwama, Shuichi Miyazaki, Naoya Yamauchi	A 1.875: approximation algorithm for the stable marriage problem.	SODA	2007	DBLP BibTeX RDF
13	Chayant Tantipathananandh, Tanya Y. Berger-Wolf, David Kempe 0001	A framework for community identification in dynamic social networks.	KDD	2007	DBLP DOI BibTeX RDF	community identification, dynamic social networks
13	Ralf Klasing, Adrian Kosowski, Alfredo Navarra	Cost Minimisation in Multi-interface Networks.	NET-COOP	2007	DBLP DOI BibTeX RDF