- Steiner Tree Approximation via Iterative Randomized Rounding
2013/02/01 by Jarosław Byrka, Fabrizio Grandoni, Thomas Rothvoß +2 · 23 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Approximation algorithm #Binary tree #Combinatorics #Complexity and Algorithms in Graphs #Computer science #Discrete mathematics #Iterative method #K-ary tree #Linear programming #Linear programming relaxation #Machine Learning and Algorithms #Mathematical optimization #Mathematics #Minimum spanning tree #Randomized rounding #Relaxation (psychology) #Rounding #Sequence (biology) #Steiner tree problem #Tree (set theory) #Tree structure #k-minimum spanning tree
- An improved LP-based approximation for steiner tree
2010/06/05 by Jarosław Byrka, Fabrizio Grandoni, Thomas Rothvoß +1 · 1 citation
Computer Science · Engineering · Mathematics · #Complexity and Algorithms in Graphs #VLSI and FPGA Design Techniques #Advanced Graph Theory Research #Steiner tree problem #Rounding #Combinatorics #k-minimum spanning tree #Approximation algorithm #Mathematics #Linear programming relaxation #Tree (set theory) #Minimum spanning tree #Randomized rounding #Spanning tree #Relaxation (psychology) #Discrete mathematics #Sequence (biology) #Graph #K-ary tree #Mathematical optimization #Tree structure #Computer science #Linear programming #Binary tree
- Dependent rounding and its applications to approximation algorithms
2006/05/01 by Rajiv Gandhi, Samir Khuller, Srinivasan Parthasarathy +1 · 39 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Algorithm #Approximation algorithm #Bipartite graph #Complexity and Algorithms in Graphs #Computer science #Graph #Mathematical optimization #Mathematics #Maximization #Optimization and Search Problems #Randomized algorithm #Randomized rounding #Rounding #Scheduling (production processes) #Theoretical computer science #Vertex cover
- A new rounding procedure for the assignment problem with applications to dense graph arrangement problems
2002/03/01 by Sanjeev Arora, Alan Frieze, Haim Kaplan · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Approximation algorithm #Betweenness centrality #Combinatorics #Complexity and Algorithms in Graphs #Computer science #Discrete mathematics #Graph #Inequality #Linear inequality #Matching (statistics) #Mathematical analysis #Mathematics #Maximum cut #Optimization and Search Problems #Quadratic equation #Randomized rounding #Rounding #Time complexity #Triangle inequality