Approximations of Weighted Independent Set and Hereditary Subset Problems
Journal of Graph Algorithms and ApplicationsPublished 1 January 2000Open access
Magnús M. Halldórsson
Citations155
SJR quartileQ2
SJR score0.43
SNIP0.70
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
The focus of this study is to clarify the approximability of the important versions of the maximum independent set problem, and to apply, where possible, the technique to related hereditary subgraph and subset problem. We report improved performance ratios for the Independent Set problem in weighted general graphs, weighted bounded-degree graphs, and in sparse graphs. Other problems with better than previously reported ratios include Weighted Set Packing, Longest Subsequence, Maximum Independent Sequence, and Independent Set in hypergraphs.
Keywords
Computer ScienceEngineering
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.
IEEE Transactions on Information TheoryOn the Shannon capacity of a graph
1,658 Citations1979László Lovász
It is proved that the Shannon zero-error capacity of the pentagon is \sqrt{5} and a well-characterized, and in a sense easily computable, function is introduced which bounds the capacity from above and equals the capacity in a large number of cases.
Artificial IntelligenceCoalition structure generation with worst case guarantees
743 Citations1999Tüomas Sandholm, Kate Larson +3 more
Journal of the ACMApproximate graph coloring by semidefinite programming
429 Citations1998David R. Karger, Rajeev Motwani +1 more
BIT Numerical MathematicsApproximating maximum independent sets by excluding subgraphs
363 Citations1992Ravi B. Boppana, Magnús M. Halldórsson
Open Scholarship Institutional Repository (Washington University in St. Louis)An Algorithm for Optimal Winner Determination in Combinatorial Auctions
328 Citations1999Tüomas Sandholm
The algorithm allows combinatorial auctions to scale up to significantly larger numbers of items and bids than prior approaches to optimal winner determination by capitalizing on the fact that the space of bids is necessarily sparsely populated in practice.
Discrete Applied MathematicsEfficient bounds for the stable set, vertex cover and set packing problems
274 Citations1983Dorit S. Hochbaum
A collection of efficient algorithms that deliver approximate solution to the weighted stable set, vertex cover and set packing problems and guarantee bounds on the ratio of the heuristic Solution to the optimal solution.
Lecture notes in computer scienceThe approximation of maximum subgraph problems
170 Citations1993Carsten Lund, Mihalis Yannakakis
It is shown that the problem to find the maximum number of nodes inducing a subgraph that satisfies a desired property π on directed or undirected graphs that is nontrivial and hereditary on induced subgraphs is hard to approximate.
Optimal solutions for multi-unit combinatorial auctions
150 Citations2000Rica Gonen, Daniel Lehmann
This work investigates the use of Branch-and-Bound techniques: they require both a way to bound from above the value of the best allocation and a good criterion to decide which bids are to be tried first.
Mathematical ProgrammingApproximating the independence number via theϑ-function
138 Citations1998Noga Alon, Nabil Kahalé
An approximation algorithm for the independence number of a graph that improves the best known previous algorithm of Boppana and Halldorsson that finds an independent set of size Ω(m1/(k−1)) in such a graph.
Derandomizing semidefinite programming based approximation algorithms
67 Citations2002Sanjeev Mahajan, H. Ramesh
This paper gives techniques to derandomize the above class of randomized algorithms, thus obtaining polynomial time deterministic algorithms with the same approximation ratios for the above problems.
Randomized graph products, chromatic numbers, and Lovasz j-function
66 Citations1995Uriel Feige
It is proved that for somec>0, there exists an infinite family of graphs such that vartheta (G) > α (G), where n denotes the number of vertices in a graph and this disproves a known conjecture regarding the ϑ function.
Theoretical Computer ScienceOn the approximation of largest common subtrees and largest common point sets
64 Citations2000Tatsuya Akutsu, Magnús M. Halldórsson
It is shown that approximating the problems within a factor of ne is NP-complete, while a general search algorithm which approximates both problems withina factor of O(n/log n) is presented.
Discrete Applied MathematicsIndependent sets with domination constraints
64 Citations2000Magnús M. Halldórsson, Jan Kratochvı́l +1 more
Applications of Set Covering, Set Packing and Set Partitioning Models: A Survey
62 Citations1998R. R. Vemuganti
Symposium on Discrete AlgorithmsImproved approximation algorithms for the vertex cover problem in graphs and hypergraphs
62 Citations2000Eran Halperin
Lecture notes in computer scienceOn approximation properties of the Independent set problem for degree 3 graphs
31 Citations1995Piotr Berman, Toshihiro Fujito
Nordic journal of computingImproved approximations of independent sets in bounded-degree graphs via subgraph removal
30 Citations1994Magnús M. Halldórsson, Jaikumar Radhakrishnan
Lecture notes in computer scienceApproximations of Weighted Independent Set and Hereditary Subset Problems
24 Citations1999Magnús M. Halldórsson
Improved performance ratios are reported in bounded-degree graphs, inductive graphs, and general graphs, as well as for the unweighted problem in sparse graphs, as well as for the unweighted problem in sparse graphs.
Heuristics for finding large independent sets, with applications to coloring semi-random graphs
23 Citations2002Uriel Feige, Joe Kilian
It is shown that when p<(1-/spl epsiv/) In n/|S|, an independent set of size |S| cannot be recovered, unless NP/spl sube/BPP, and heuristics that with high probability recover S are designed.
Lecture notes in computer scienceApproximating maximum independent sets in uniform hypergraphs
19 Citations1998Thomas Hofmeister, Hanno Lefmann
For fixed k≥2, the problems of approximating the independence number and the chromatic number of k-uniform hypergraphs on n vertices are considered and for both problems polynomial time approximation algorithms with approximation ratios O(n/(log(k-1) n)2) are described.
SIAM Journal on Discrete MathematicsGeneralized Chromatic Numbers of Random Graphs
12 Citations1992Edward R. Scheinerman
The-chromatic number of a graph G is defined to be the least integer k such that $V( G )$ admits a partition into k subsets each of which induce a member of $\mathcal{P}$.