On Some Tighter Inapproximability Results

No abstract is available for this paper.

• Publication year

  1998

• Venue

  Electron. Colloquium Comput. Complex.

• Publication date

  1998-06-01

• Fields of study

  Mathematics, Computer Science

• Identifiers

  No identifiers available.

• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Clique Is Hard To Approximate Within

  2000cited by this paper
• A 3/2-approximation algorithm for sorting by reversals

  1998cited by this paper
• Clique Is Hard to Approximate within N 1?

  1997cited by this paper
• Faster and simpler algorithm for sorting signed permutations by reversals

  1997cited by this paper
• Sorting by reversals is difficult

  1997cited by this paper
• Clique is hard to approximate within n/sup 1-/spl epsiv//

  1996cited by this paper
• Gadgets, approximation, and linear programming

  1996cited by this paper
• Probabilistic checking of proofs and hardness of approximation problems

  1995cited by this paper
• Approximating the value of two power proof systems, with applications to MAX 2SAT and MAX DICUT

  1995cited by this paper
• A compendium of NP optimization problems

  1994cited by this paper
• Approximating maximum independent set in bounded degree graphs

  1994cited by this paper
• .879-approximation algorithms for MAX CUT and MAX 2SAT

  1994cited by this paper
• Genome rearrangements and sorting by reversals

  1993cited by this paper
• Proof verification and hardness of approximation problems

  1992cited by this paper
• Optimization, approximation, and complexity classes

  1991cited by this paper
• On the Complexity of Approximating the Independent Set Problem

  1989cited by this paper
• Bounds for sorting by prefix reversal

  1979cited by this paper

• On the complexity of the Maker-Breaker happy vertex game

  2026cites this paper
• Maximizing the Margin between Desirable and Undesirable Elements in a Covering Problem

  2025influential citation
• Flanked Transposition Distance for Two Strings

  2025cites this paper
• Simultaneous Network Design with Restricted Link Usage

  2025cites this paper
• Hardness of Hypergraph Edge Modification Problems

  2025cites this paper
• Canonical cuts of path powers

  2024cites this paper
• Packing Krs in bounded degree graphs

  2024cites this paper
• Benchmarking a heuristic Floquet adiabatic algorithm for the Max-Cut problem

  2024cites this paper
• Partial Temporal Vertex Cover with Bounded Activity Intervals

  2024cites this paper
• Packing Krs in bounded degree graphs

  2022cites this paper
• Improved Combinatorial Approximation Algorithms for MAX CUT in Sparse Graphs

  2022cites this paper
• Simultaneous Contests with Equal Sharing Allocation of Prizes: Computational Complexity and Price of Anarchy

  2022cites this paper
• APX-Hardness of the Minimum Vision Points Problem

  2022influential citation
• Neural Maximum Independent Set

  2021cites this paper
• Partial order alignment by adjacencies and breakpoints

  2021cites this paper
• Approximation Metatheorems for Classes with Bounded Expansion

  2021cites this paper
• Complexity of Maximum Cut on Interval Graphs

  2020cites this paper
• A (1.4+ϵ)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(1.4 + \epsilon )$$\end{document}-approximation algorithm for

  2020influential citation
• The Quantum Approximate Optimization Algorithm

  2020cites this paper
• Maximum Stacking Base Pairs: Hardness and Approximation by Nonlinear Linear Programming-Rounding

  2020cites this paper
• Data inference from encrypted databases: a multi-dimensional order-preserving matching approach

  2020cites this paper
• InstaHide's Sample Complexity When Mixing Two Private Images

  2020cites this paper
• Maximum cut on interval graphs of interval count five is NP-complete

  2020influential citation
• Maximum Cut on Interval Graphs of Interval Count Four is NP-Complete

  2020cites this paper
• Optimizing Reachability Sets in Temporal Graphs by Delaying

  2020influential citation
• Improved (In-)Approximability Bounds for d-Scattered Set

  2019influential citation
• Sorting Signed Permutations by Inverse Tandem Duplication Random Losses

  2019cites this paper
• Restricted assignment scheduling with resource constraints

  2019cites this paper
• Listing k-cliques in Sparse Real-World Graphs*

  2018influential citation
• Multi-Commodity Flow with In-Network Processing

  2018cites this paper
• An approximation algorithm for genome sorting by reversals to recover all adjacencies

  2018cites this paper
• Computing the family-free DCJ similarity

  2018cites this paper
• On the approximability of Time Disjoint Walks

  2018influential citation
• Machine Learning Applied to Sorting Permutations by Reversals and Transpositions

  2017influential citation
• Algorithms for Computing the Family-Free Genomic Similarity Under DCJ

  2017cites this paper
• On the Maximum Crossing Number

  2017cites this paper
• At the roots of dictionary compression: string attractors

  2017influential citation
• Algorithms and methods for large-scale genome rearrangements identification

  2017cites this paper
• A (1.4 + ε)-approximation algorithm for the 2-{Max-Duo} problem

  2017cites this paper
• Weak Coverage of a Rectangular Barrier

  2017cites this paper
• Symmetric Interdiction for Matching Problems

  2017cites this paper
• Triangle packing in (sparse) tournaments: approximation and kernelization

  2017cites this paper
• Competitive algorithms for multistage online scheduling

  2017cites this paper
• Greed is Good for Deterministic Scale-Free Networks

  2016cites this paper
• Approximation of barter exchanges with cycle length constraints

  2016cites this paper
• Approximation Complexity of Max-Cut on Power Law Graphs

  2016cites this paper
• The SCJ Small Parsimony Problem for Weighted Gene Adjacencies

  2016cites this paper
• Successor rules for flipping pancakes and burnt pancakes

  2016cites this paper
• On judicious bipartitions of graphs

  2016cites this paper
• Minimum Common String Partition Problem

  2016cites this paper
• On the Complexity of Weighted Greedy Matchings

  2016cites this paper
• On judicious partitions of graphs

  2016cites this paper
• An Experimental Investigation on the Pancake Problem

  2015cites this paper
• Maximum Weighted Independent Sets with a Budget

  2015cites this paper
• Towards Better Inapproximability Bounds for TSP: A Challenge of Global Dependencies

  2015cites this paper
• Corruption Detection on Networks

  2015cites this paper
• Approximability of TSP on Power Law Graphs

  2015cites this paper
• Rearranging Two Dimensional Arrays by Prefix Reversals

  2015cites this paper
• Size-Constrained Weighted Set Cover

  2015cites this paper
• Comparative genomics : Multiple genome rearrangement and efficient algorithm development by

  2015cites this paper
• A STUDY OF THE BICLIQUE EDGE PARTITION AND COVER PROBLEMS

  2015cites this paper
• Merging Query Results From Local Search Engines for Georeferenced Objects

  2014cites this paper
• The Harassed Waitress Problem

  2014cites this paper
• Simultaneous bayesian auctions and computational complexity

  2014cites this paper
• Finding the smallest binarization of a CFG is NP-hard

  2014cites this paper
• On judicious bipartitions of graphs Jie Ma

  2014cites this paper
• Resource Optimization of Non-Additive Utility Functions in Localized SC-FDMA Systems

  2014cites this paper
• Algorithm engineering for a quantum annealing platform

  2014cites this paper
• Approximation hardness of graphic TSP on cubic graphs

  2013influential citation
• Approximability of Combinatorial Optimization Problems on Power Law Networks

  2013cites this paper
• Improved Inapproximability Results for the Shortest Superstring and Related Problems

  2013cites this paper
• Complexity results for rainbow matchings

  2013cites this paper
• On some polynomially solvable cases and approximate algorithms in the optimal communication tree construction problem

  2013cites this paper
• On the approximability of covering points by lines and related problems

  2013cites this paper
• New Inapproximability Bounds for TSP

  2013influential citation
• Approximability of Combinatorial Optimization Problems on Power Law Networks

  2013cites this paper
• Improved Inapproximability Results for the Shortest Superstring and the Bounded Metric TSP

  2013cites this paper
• On Approximability of Bounded Degree Instances of Selected Optimization Problems

  2013influential citation
• Survey on Fingerprint Classification Methods for Biological Sequences

  2013cites this paper
• Mining Biological Networks for Similar Patterns

  2012cites this paper
• 2 The Banking Network Model 2 . 1 Rationale Behind the Model

  2012influential citation
• The Robust Set Problem: Parameterized Complexity and Approximation

  2012cites this paper
• A note on anti-coordination and social interactions

  2012influential citation
• Optimal social choice functions: a utilitarian view

  2012influential citation
• Inapproximability of (1,2)-Exemplar Distance

  2012influential citation
• Improved Approximation Lower Bounds for Vertex Cover on Power Law Graphs and Some Generalizations

  2012cites this paper
• Applications of heuristic search on phylogeny reconstruction problems

  2012cites this paper
• Maximum Directed Cuts in Graphs with Degree Constraints

  2012cites this paper
• A note on anti-coordination and social interactions

  2012cites this paper
• Introduction to the Minimum Rainbow Subgraph problem

  2012cites this paper
• On the complexity of the highway problem

  2012cites this paper
• Introduction to the MINIMUM RAINBOW SUBGRAPH problem

  2012cites this paper
• On Approximation Lower Bounds for TSP with Bounded Metrics

  2012cites this paper
• Maximum Directed Cuts in Graphs with Degree Constraints

  2011cites this paper
• E(cid:14)cient Ampli(cid:12)ers and Bounded Degree Optimization

  2011cites this paper
• Improved Lower Bounds for the Shortest Superstring and Related Problems

  2011influential citation
• Charge and reduce: A fixed-parameter algorithm for String-to-String Correction

  2011influential citation
• Enforcing Efficient Equilibria in Network Design Games via Subsidies

  2011cites this paper
• A comparative study on biological networks: alignment and structural properties

  2011cites this paper
• Wireless Sensor Network's Lifetime Maximization Problem in Case of Given Set of Covers

  2011cites this paper