Search results for "APX-hard"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
61	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
58	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
40	Rudi Cilibrasi, Leo van Iersel, Steven Kelk, John Tromp	The Complexity of the Single Individual SNP Haplotyping Problem.	Algorithmica	2007	DBLP DOI BibTeX RDF
38	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
36	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
36	N. S. Narayanaswamy, Swapnoneel Roy	Block Sorting Is APX-Hard.	CIAC	2015	DBLP DOI BibTeX RDF
36	Alexander Pilz	Flip distance between triangulations of a planar point set is APX-hard.	Comput. Geom.	2014	DBLP DOI BibTeX RDF
36	Paul S. Bonsma	Max-leaves spanning tree is APX-hard for cubic graphs.	J. Discrete Algorithms	2012	DBLP DOI BibTeX RDF
36	Minghui Jiang 0001	Clique in 3-track interval graphs is APX-hard	CoRR	2012	DBLP BibTeX RDF
36	Paul S. Bonsma	Max-Leaves Spanning Tree is APX-hard for Cubic Graphs	CoRR	2009	DBLP BibTeX RDF
36	Paola Bonizzoni, Gianluca Della Vedova, Riccardo Dondi	Anonymizing Binary Tables is APX-hard	CoRR	2007	DBLP BibTeX RDF
36	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
36	Björn Brodén, Mikael Hammar, Bengt J. Nilsson	Guarding lines and 2-link polygons is apx-hard.	CCCG	2001	DBLP BibTeX RDF
34	Rohit Khandekar, Tracy Kimbrel, Konstantin Makarychev, Maxim Sviridenko	On Hardness of Pricing Items for Single-Minded Bidders.	APPROX-RANDOM	2009	DBLP DOI BibTeX RDF
29	Basile Couëtoux, Laurent Gourvès, Jérôme Monnot, Orestis Telelis	On Labeled Traveling Salesman Problems.	ISAAC	2008	DBLP DOI BibTeX RDF
29	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
29	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
24	Ning Chen 0005, Arpita Ghosh, Sergei Vassilvitskii	Optimal envy-free pricing with metric substitutability.	EC	2008	DBLP DOI BibTeX RDF	envy-free pricing, algorithms
24	Randeep Bhatia, Li (Erran) Li	Characterizing achievable multicast rates in multi-hop wireless networks.	MobiHoc	2005	DBLP DOI BibTeX RDF	optimization, graph theory, mathematical programming, combinatorics
24	Alexander Grigoriev, Gerhard J. Woeginger	Project scheduling with irregular costs: complexity, approximability, and algorithms.	Acta Informatica	2004	DBLP DOI BibTeX RDF
24	Alexander Grigoriev, Gerhard J. Woeginger	Project Scheduling with Irregular Costs: Complexity, Approximability, and Algorithms.	ISAAC	2002	DBLP DOI BibTeX RDF
19	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
19	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
19	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
19	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
19	Paola Bonizzoni, Gianluca Della Vedova, Riccardo Dondi	The k-Anonymity Problem Is Hard.	FCT	2009	DBLP DOI BibTeX RDF
19	Tim Nonner, Alexander Souza	A 5/3-Approximation Algorithm for Joint Replenishment with Deadlines.	COCOA	2009	DBLP DOI BibTeX RDF
19	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
19	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
19	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
19	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
19	Joseph Naor, Hadas Shachnai, Tami Tamir	Real-Time Scheduling with a Budget.	Algorithmica	2007	DBLP DOI BibTeX RDF
19	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
19	Michael Lampis, Valia Mitsou	The Ferry Cover Problem.	FUN	2007	DBLP DOI BibTeX RDF	wolf-goat-cabbage puzzle, approximation algorithms, graph algorithms, vertex cover, transportation problems
19	Ioannis Giotis 0001, Venkatesan Guruswami	Correlation clustering with a fixed number of clusters.	SODA	2006	DBLP DOI BibTeX RDF
19	Bodo Manthey	Approximation Algorithms for Restricted Cycle Covers Based on Cycle Decompositions.	WG	2006	DBLP DOI BibTeX RDF
19	Xin Chen 0037, Lan Liu 0001, Zheng Liu, Tao Jiang 0001	On the Minimum Common Integer Partition Problem.	CIAC	2006	DBLP DOI BibTeX RDF
19	Paola Bonizzoni, Gianluca Della Vedova, Riccardo Dondi, Guillaume Fertin, Stéphane Vialette	Exemplar Longest Common Subsequence.	International Conference on Computational Science (2)	2006	DBLP DOI BibTeX RDF
19	Adrian Kosowski, Michal Malafiejski, Pawel Zylinski	Parallel Processing Subsystems with Redundancy in a Distributed Environment.	PPAM	2005	DBLP DOI BibTeX RDF
19	Chandra Chekuri, Sanjeev Khanna, F. Bruce Shepherd	The all-or-nothing multicommodity flow problem.	STOC	2004	DBLP DOI BibTeX RDF	all-or-nothing multicommodity flow, approximation algorithms, online algorithms, multicommodity flow, oblivious routing, edge disjoint paths
19	Joseph Naor, Hadas Shachnai, Tami Tamir	Real-Time Scheduling with a Budget.	ICALP	2003	DBLP DOI BibTeX RDF
19	Romeo Rizzi, Vineet Bafna, Sorin Istrail, Giuseppe Lancia	Practical Algorithms and Fixed-Parameter Tractability for the Single Individual SNP Haplotyping Problem.	WABI	2002	DBLP DOI BibTeX RDF
19	Magnús M. Halldórsson, Kazuo Iwama, Shuichi Miyazaki, Yasufumi Morita	Inapproximability Results on Stable Marriage Problems.	LATIN	2002	DBLP DOI BibTeX RDF
19	Tatsuya Akutsu, Hiroki Arimura, Shinichi Shimozono	On approximation algorithms for local multiple alignment.	RECOMB	2000	DBLP DOI BibTeX RDF
19	Han Hoogeveen, Martin Skutella, Gerhard J. Woeginger	Preemptive Scheduling with Rejection.	ESA	2000	DBLP DOI BibTeX RDF	in-approximability, Scheduling, computational complexity, approximation algorithm, preemption, worst case ratio
19	Stephan J. Eidenbenz, Christoph Stamm	MAXIMUM CLIQUE and MINIMUM CLIQUE PARTITION in Visibility Graphs.	IFIP TCS	2000	DBLP DOI BibTeX RDF
16	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
16	Minghui Jiang 0001	Inapproximability of Maximal Strip Recovery.	ISAAC	2009	DBLP DOI BibTeX RDF
16	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
16	Riccardo Dondi, Guillaume Fertin, Stéphane Vialette	Maximum Motif Problem in Vertex-Colored Graphs.	CPM	2009	DBLP DOI BibTeX RDF
16	Eric McDermid	A 3/2-Approximation Algorithm for General Stable Marriage.	ICALP (1)	2009	DBLP DOI BibTeX RDF
16	Nir Ailon, Edo Liberty	Correlation Clustering Revisited: The "True" Cost of Error Minimization Problems.	ICALP (1)	2009	DBLP DOI BibTeX RDF
16	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
16	Tim Nonner, Alexander Souza	Latency Constrained Aggregation in Chain Networks Admits a PTAS.	AAIM	2009	DBLP DOI BibTeX RDF
16	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
16	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
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	René A. Sitters	Approximability of Average Completion Time Scheduling on Unrelated Machines.	ESA	2008	DBLP DOI BibTeX RDF
16	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
16	Ioannis Caragiannis, Gianpiero Monaco	A 6/5-Approximation Algorithm for the Maximum 3-Cover Problem.	MFCS	2008	DBLP DOI BibTeX RDF
16	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
16	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
16	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
16	Kazuo Iwama, Shuichi Miyazaki, Naoya Yamauchi	A 1.875: approximation algorithm for the stable marriage problem.	SODA	2007	DBLP BibTeX RDF
16	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
16	Ralf Klasing, Adrian Kosowski, Alfredo Navarra	Cost Minimisation in Multi-interface Networks.	NET-COOP	2007	DBLP DOI BibTeX RDF
16	Jean Cardinal, Erik D. Demaine, Samuel Fiorini, Gwenaël Joret, Stefan Langerman, Ilan Newman, Oren Weimann	The Stackelberg Minimum Spanning Tree Game.	WADS	2007	DBLP DOI BibTeX RDF
16	Iman Hajirasouliha, Hossein Jowhari, Ravi Kumar 0001, Ravi Sundaram	On Completing Latin Squares.	STACS	2007	DBLP DOI BibTeX RDF
16	Roded Sharan, Bjarni V. Halldórsson, Sorin Istrail	Islands of Tractability for Parsimony Haplotyping.	IEEE ACM Trans. Comput. Biol. Bioinform.	2006	DBLP DOI BibTeX RDF	graph algorithms, Biology and genetics, analysis of algorithms and problem complexity
16	Paola Bonizzoni, Gianluca Della Vedova, Riccardo Dondi, Giancarlo Mauri	Fingerprint Clustering with Bounded Number of Missing Values.	CPM	2006	DBLP DOI BibTeX RDF
16	Peter Jonsson, Gustav Nordh	Generalised Integer Programming Based on Logically Defined Relations.	MFCS	2006	DBLP DOI BibTeX RDF
16	Cédric Chauve, Guillaume Fertin, Romeo Rizzi, Stéphane Vialette	Genomes Containing Duplicates Are Hard to Compare.	International Conference on Computational Science (2)	2006	DBLP DOI BibTeX RDF
16	Nikhil Bansal 0001, Don Coppersmith, Baruch Schieber	Minimizing Setup and Beam-On Times in Radiation Therapy.	APPROX-RANDOM	2006	DBLP DOI BibTeX RDF
16	Christoph Ambühl, Uli Wagner 0001	The Clique Problem in Intersection Graphs of Ellipses and Triangles.	Theory Comput. Syst.	2005	DBLP DOI BibTeX RDF
16	Paola Bonizzoni, Gianluca Della Vedova, Riccardo Dondi, Tao Jiang 0001	Correlation Clustering and Consensus Clustering.	ISAAC	2005	DBLP DOI BibTeX RDF
16	Venkatesan Guruswami, Jason D. Hartline, Anna R. Karlin, David Kempe 0001, Claire Kenyon, Frank McSherry	On profit-maximizing envy-free pricing.	SODA	2005	DBLP BibTeX RDF
16	Nikhil Bansal 0001, Andrea Lodi 0001, Maxim Sviridenko	A Tale of Two Dimensional Bin Packing.	FOCS	2005	DBLP DOI BibTeX RDF
16	Guillaume Blin, Guillaume Fertin, Danny Hermelin, Stéphane Vialette	Fixed-Parameter Algorithms for Protein Similarity Search Under mRNA Structure Constraints.	WG	2005	DBLP DOI BibTeX RDF
16	Jason D. Hartline, Vladlen Koltun	Near-Optimal Pricing in Near-Linear Time.	WADS	2005	DBLP DOI BibTeX RDF
16	Roded Sharan, Bjarni V. Halldórsson, Sorin Istrail	Islands of Tractability for Parsimony Haplotyping.	CSB	2005	DBLP DOI BibTeX RDF	approximation algorithm, complexity, fixed parameter tractability, genotype, parsimony, Haplotype inference
16	Nicole Immorlica, Mohammad Mahdian, Vahab S. Mirrokni	Cycle Cover with Short Cycles.	STACS	2005	DBLP DOI BibTeX RDF
16	Tapio Elomaa, Matti Kääriäinen	The Difficulty of Reduced Error Pruning of Leveled Branching Programs.	Ann. Math. Artif. Intell.	2004	DBLP DOI BibTeX RDF	reduced error pruning, approximability, NP-completeness, concept learning, branching programs
16	Martin Jansche	Learning Local Transductions Is Hard.	J. Log. Lang. Inf.	2004	DBLP DOI BibTeX RDF	letter-to-sound rules, rational transductions, machine learning, natural language processing, combinatorial optimization, NP completeness, formal languages, Boolean satisfiability
16	Nikhil Bansal 0001, Maxim Sviridenko	New approximability and inapproximability results for 2-dimensional Bin Packing.	SODA	2004	DBLP BibTeX RDF
16	Thomas Erlebach, Alexander Hall, Alessandro Panconesi, Danica Vukadinovic	Cuts and Disjoint Paths in the Valley-Free Path Model of Internet BGP Routing.	CAAN	2004	DBLP DOI BibTeX RDF
16	Lap Chi Lau	An Approximate Max-Steiner-Tree-Packing Min-Steiner-Cut Theorem.	FOCS	2004	DBLP DOI BibTeX RDF
16	Christoph Ambühl, Andrea E. F. Clementi, Miriam Di Ianni, Nissan Lev-Tov, Angelo Monti, David Peleg, Gianluca Rossi, Riccardo Silvestri	Efficient Algorithms for Low-Energy Bounded-Hop Broadcast in Ad-Hoc Wireless Networks.	STACS	2004	DBLP DOI BibTeX RDF
16	Dotan Emanuel, Amos Fiat	Correlation Clustering - Minimizing Disagreements on Arbitrary Weighted Graphs.	ESA	2003	DBLP DOI BibTeX RDF
16	Hans-Joachim Böckenhauer, Dirk Bongartz, Juraj Hromkovic, Ralf Klasing, Guido Proietti, Sebastian Seibert, Walter Unger	On k-Edge-Connectivity Problems with Sharpened Triangle Inequality.	CIAC	2003	DBLP DOI BibTeX RDF
16	Erik D. Demaine, Nicole Immorlica	Correlation Clustering with Partial Information.	RANDOM-APPROX	2003	DBLP DOI BibTeX RDF
16	Christoph Ambühl, Uli Wagner 0001	On the Clique Problem in Intersection Graphs of Ellipses.	ISAAC	2002	DBLP DOI BibTeX RDF
16	Reuven Bar-Yehuda, Magnús M. Halldórsson, Joseph Naor, Hadas Shachnai, Irina Shapira	Scheduling split intervals.	SODA	2002	DBLP BibTeX RDF
16	Mark de Berg, Joachim Gudmundsson, Matthew J. Katz, Christos Levcopoulos, Mark H. Overmars, A. Frank van der Stappen	TSP with Neighborhoods of Varying Size.	ESA	2002	DBLP DOI BibTeX RDF
16	Isto Aho	On the Approximability of Interactive Knapsack Problems.	SOFSEM	2001	DBLP DOI BibTeX RDF
16	Sebastian Seibert, Walter Unger	The Hardness of Placing Street Names in a Manhattan Type Map.	CIAC	2000	DBLP DOI BibTeX RDF
16	Hadas Shachnai, Tami Tamir	Polynominal time approximation schemes for class-constrained packing problem.	APPROX	2000	DBLP DOI BibTeX RDF
16	Dirk Bongartz	On the Approximation Ratio of the Group-Merge Algorithm for the Shortest Common Suerstring Problem.	SOFSEM	2000	DBLP DOI BibTeX RDF