litlas
ログインアカウント作成

Polynomial Time Approximation Schemes for Dense Instances of NP-Hard Problems

著者: Sanjeev Arora, David R. Karger, Marek Karpinski - ACM Symposium on Theory of Computing, STOC 1995 被引用: 203

Article Polynomial time approximation schemes for dense instances of NP-hard problems Share on Authors: Sanjeev Arora Princeton University Princeton UniversityView Profile , David Karger MIT Laboratory for Computer Science, AT&T Bell Laboratories MIT Laboratory for Computer Science, AT&T Bell LaboratoriesView Profile , Marek Karpinski University of Bonn University of BonnView Profile Authors Info & Claims STOC '95: Proceedings of the twenty-seventh annual ACM symposium on Theory of computingMay 1995 Pages 284–293https://doi.org/10.1145/225058.225140Online:29 May 1995Publication History 120citation1,159DownloadsMetricsTotal Citations120Total Downloads1,159Last 12 Months4Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Finding k Cuts withinTwice the OptimalFinding k Cuts within Twice the OptimalProof Verification andHardness of…Proof Verification and Hardness of Approximation ProblemsOn the Approximation ofMaximum SatisfiabilityOn the Approximation of Maximum SatisfiabilityA Chernoff Bound forRandom Walks on Expande…A Chernoff Bound for Random Walks on Expander GraphsThe Complexity ofMultiterminal CutsThe Complexity of Multiterminal Cuts878-approximationAlgorithms for MAX CUT…878-approximation Algorithms for MAX CUT and MAX 2SATImproved ApproximationAlgorithms for Maximum…Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite ProgrammingAproximating the Valueof Two Prover Proof…Aproximating the Value of Two Prover Proof Systems, With Applications to MAX 2SAT and MAX DICUTThe Regularity Lemma andApproximation Schemes…The Regularity Lemma and Approximation Schemes for Dense ProblemsMAX-CUT has a randomizedapproximation scheme in…MAX-CUT has a randomized approximation scheme in dense graphsA CompleteClassification of the…A Complete Classification of the Approximability of Maximization Problems Derived from Boolean Constraint SatisfactionClique is hard toapproximate within n1−εClique is hard to approximate within n1−εImproved ApproximationAlgorithms for MAX k-CU…Improved Approximation Algorithms for MAX k-CUT and MAX BISECTIONThe Regularity Lemma andApproximation Schemes…The Regularity Lemma and Approximation Schemes for Dense ProblemsA New Rounding Procedurefor the Assignment…A New Rounding Procedure for the Assignment Problem with Applications to Dense Graph Arrangement ProblemsTowards a SyntacticCharacterization of PTASTowards a Syntactic Characterization of PTASImprovedNon-Approximability…Improved Non-Approximability Results for Minimum Vertex Cover with Density ConstraintsPolynomial TimeApproximation Schemes…Polynomial Time Approximation Schemes for Some Dense Instances of NP-Hard Optimization ProblemsImproved approximationalgorithms for MAXk-CUT…Improved approximation algorithms for MAXk-CUT and MAX BISECTIONThe Approximability ofNP-hard ProblemsThe Approximability of NP-hard ProblemsAn ImprovedApproximation Algorithm…An Improved Approximation Algorithm for MULTIWAY CUTComplexity of findingdense subgraphsComplexity of finding dense subgraphsEnergy Minimization viaGraph Cuts: Settling…Energy Minimization via Graph Cuts: Settling What is PossibleSpectral AlgorithmsSpectral AlgorithmsPolynomial TimeApproximation Schemes…Polynomial Time Approximation Schemes for Dense Instances of NP-Hard Problems過去の参考文献中心の論文この論文を引用する論文古い新しい

ノードをクリックするとフォーカスを固定、空白をクリックすると本論文に戻ります。ホバーで一時的にプレビューできます。各ノードのページはタイトルから開けます。