Approximating the Maximum Acyclic Subgraph
DSpace@MIT (Massachusetts Institute of Technology)Published 1 January 2000Open access
Alantha Newman
Citations19
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
Abstract
Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2000.
Keywords
Computer Science
Cambridge University Press eBooksRandomized Algorithms
4,069 Citations1995Rajeev Motwani, Prabhakar Raghavan
Algorithms and combinatoricsGeometric Algorithms and Combinatorial Optimization
3,487 Citations1988Martin Grötschel, László Lovász +1 more
This paper presents a meta-modelling framework for estimating the running time of Oracle Algorithms, and some examples show how this framework can be modified for more efficient and scalable solutions to NP-Completeness problems.
Reducibility Among Combinatorial Problems
2,450 Citations2009Richard M. Karp
Throughout the 1960s I worked on combinatorial optimization problems including logic circuit design with Paul Roth and assembly line balancing and the traveling salesman problem with Mike Held, which made me aware of the importance of distinction between polynomial-time and superpolynomial-time solvability.
Mathematical ProgrammingFacets of the linear ordering polytope
173 Citations1985Martin Grötschel, Michael Jünger +1 more
It is shown that various classes of inequalities define facets ofPLOn, e.g. the 3-dicycle inequalities, the simplek-fence inequalities and various Möbius ladder inequalities, and the use of these inequalities in cutting plane approaches to the triangulation problem of input-output matrices is discussed.
Journal of AlgorithmsTight Bounds for the Maximum Acyclic Subgraph Problem
25 Citations1997Bonnie Berger, Peter W. Shor
All graphs without two-cycles contain large acyclic subgraphs, a fact which was not previously known, and polynomial-time and RNC algorithms which, when given any graphGwithout two- cycles, find an acy Cleric subgraph of size at least(1/2+?(1/?(G)))|A|, where G is the maximum degree of G.
Lecture notes in computer scienceThe strongest facets of the acyclic subgraph polytope are unknown
23 Citations1996Michel X. Goemans, L. A. Hall
It is shown that the strength of a relaxation is the maximum of the strengths of the relaxations obtained by simply adding to the trivial relaxation each valid inequality separately, derived from the probabilistic method.