A Deterministic Strongly Polynomial Algorithm for Matrix Scaling and Approximate Permanents

No abstract is available for this paper.

• Publication year

  1998

• Venue

  Symposium on the Theory of Computing

• Publication date

  1998-05-23

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1145/276698.276880
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Private communication

  1999cited by this paper
• The Deeation-innation Method for Certain Semideenite Programming and Maximum Determinant Completion Problems

  1998cited by this paper
• A simple polynomial time algorithm to approximate the permanent within a simply exponential factor

  1997cited by this paper
• Computing Mixed Discriminants, Mixed Volumes, and Permanents

  1997cited by this paper
• On the hardness of computing the permanent of random matrices

  1996cited by this paper
• ON THE COMPLEXITY OF NONNEGATIVE-MATRIX SCALING

  1996cited by this paper
• A Monte-Carlo Algorithm for Estimating the Permanent

  1993cited by this paper
• On the Hardness of Computing the Permanent of Random Matrices (Extended Abstract)

  1992cited by this paper
• A mildly exponential approximation algorithm for the permanent

  1992cited by this paper
• On the scaling of multidimensional matrices

  1989cited by this paper
• Scalings of matrices which have prespecified row sums and column sums via optimization

  1989cited by this paper
• Approximating the Permanent

  1989cited by this paper
• A new approach to the maximum-flow problem

  1988cited by this paper
• Additive decomposition of nonnegative matrices with applications to permanents and scalingt

  1988cited by this paper
• An O(EV log V) Algorithm for Finding a Maximal Weighted Matching in General Graphs

  1986cited by this paper
• Are search and decision programs computationally equivalent?

  1985cited by this paper
• On pairs of multidimensional matrices

  1984cited by this paper
• An analysis of alternative strategies for implementing matching algorithms

  1983cited by this paper
• Methods for Scaling to Doubly Stochastic Form

  1982cited by this paper
• Proof of the van der Waerden conjecture regarding the permanent of a doubly stochastic matrix

  1981cited by this paper
• The solution of van der Waerden's problem for permanents

  1981cited by this paper
• The Complexity of Computing the Permanent

  1979cited by this paper
• On determinants, matchings, and random algorithms

  1979cited by this paper
• Iterative reconstruction algorithms.

  1976cited by this paper
• On the Permanent of a Doubly Stochastic Matrix

  1966cited by this paper
• Rounding errors in algebraic processes

  1964cited by this paper
• A Relationship Between Arbitrary Positive Matrices and Doubly Stochastic Matrices

  1964cited by this paper
• The Statistics of Dimers on a Lattice

  1961cited by this paper
• The statistics of dimers on a lattice: I. The number of dimer arrangements on a quadratic lattice

  1961cited by this paper
• A Note on Approximations to Discrete Probability Distributions

  1959cited by this paper

• mHC-lite: You Don't Need 20 Sinkhorn-Knopp Iterations

  2026influential citation
• Minimally dissipative multi-bit logical operations

  2025cites this paper
• Radial Isotropic Position via an Implicit Newton’s Method

  2025cites this paper
• Phase transition of the Sinkhorn-Knopp algorithm

  2025cites this paper
• Strongly Polynomial Frame Scaling to High Precision

  2024influential citation
• The entries of the Sinkhorn limit of an $m \times n$ matrix

  2024cites this paper
• Accelerating Sinkhorn Algorithm with Sparse Newton Iterations

  2024cites this paper
• A Sinkhorn-type Algorithm for Constrained Optimal Transport

  2024cites this paper
• A note on ubiquity of geometric Brascamp–Lieb data

  2024influential citation
• Bounding the Permanent of a Non-negative Matrix via its Degree- M Bethe and Sinkhorn Permanents

  2023influential citation
• Degree-M Bethe and Sinkhorn Permanent Based Bounds on the Permanent of a Non-Negative Matrix

  2023influential citation
• Interior-point methods on manifolds: theory and applications

  2023cites this paper
• Flows, Scaling, and Entropy Revisited: a Unified Perspective via Optimizing Joint Distributions

  2022cites this paper
• Polynomials with Lorentzian Signature, and Computing Permanents via Hyperbolic Programming

  2022cites this paper
• A Strongly Polynomial Algorithm for Approximate Forster Transforms and Its Application to Halfspace Learning

  2022influential citation
• Computational advantage of quantum random sampling

  2022cites this paper
• Regularized Box-Simplex Games and Dynamic Decremental Bipartite Matching

  2022cites this paper
• Exponential Convergence of Sinkhorn Under Regularization Scheduling

  2022cites this paper
• The minimal canonical form of a tensor network

  2022cites this paper
• Finding Hall blockers by matrix scaling

  2022influential citation
• Optimization, Complexity and Invariant Theory (Invited Talk)

  2021cites this paper
• Computing The Permanent of (Some) Complex Matrices

  2021cites this paper
• Polynomial time algorithms in invariant theory for torus actions

  2021cites this paper
• Improved quantum lower and upper bounds for matrix scaling

  2021cites this paper
• Robust learning in social networks via matrix scaling

  2021cites this paper
• Contention Resolution, Matrix Scaling and Fair Allocation

  2021cites this paper
• Counting and Sampling Perfect Matchings in Regular Expanding Non-Bipartite Graphs

  2021cites this paper
• Scaling matrices and counting the perfect matchings in graphs

  2020cites this paper
• Modified Bethe Permanent of a Nonnegative Matrix

  2020cites this paper
• Capacity lower bounds via productization

  2020influential citation
• Information geometry of operator scaling

  2020cites this paper
• Interior-point methods for unconstrained geometric programming and scaling problems

  2020cites this paper
• Polynomial-time algorithms for multimarginal optimal transport problems with structure

  2020influential citation
• Quantum algorithms for matrix scaling and matrix balancing

  2020cites this paper
• Complete Hierarchy of Relaxation for Constrained Signomial Positivity

  2020cites this paper
• The Bethe and Sinkhorn Permanents of Low Rank Matrices and Implications for Profile Maximum Likelihood

  2020cites this paper
• Tree-Sliced Variants of Wasserstein Distances

  2019cites this paper
• Parallel algorithms for computing sparse matrix permanents

  2019cites this paper
• Sinkhorn Permutation Variational Marginal Inference

  2019influential citation
• Towards a Theory of Non-Commutative Optimization: Geodesic 1st and 2nd Order Methods for Moment Maps and Polytopes

  2019cites this paper
• From independent sets and vertex colorings to isotropic spaces and isotropic decompositions

  2019cites this paper
• D S ] 5 A pr 2 01 9 Spectral Analysis of Matrix Scaling and Operator Scaling Tsz

  2019influential citation
• Approximating the Permanent by Sampling from Adaptive Partitions

  2019cites this paper
• Matrix scaling and explicit doubly stochastic limits

  2019cites this paper
• Tree-Sliced Approximation of Wasserstein Distances

  2019cites this paper
• Matrix scaling, explicit Sinkhorn limits, and arithmetic

  2019influential citation
• Spectral Analysis of Matrix Scaling and Operator Scaling

  2019influential citation
• Asynchronous Distributed Matrix Balancing and Application to Suppressing Epidemic

  2019cites this paper
• Mathematics and Computation

  2019cites this paper
• On the nature of the Theory of Computation (ToC)

  2018cites this paper
• Massively scalable Sinkhorn distances via the Nyström method

  2018cites this paper
• Efficient Algorithms for Tensor Scaling, Quantum Marginals, and Moment Polytopes

  2018cites this paper
• Recent progress on scaling algorithms and applications

  2018cites this paper
• Operator scaling via geodesically convex optimization, invariant theory and polynomial identity testing

  2018cites this paper
• Operator Scaling with Specified Marginals

  2018cites this paper
• Towards Optimal Running Times for Optimal Transport

  2018cites this paper
• Approximating the Quadratic Transportation Metric in Near-Linear Time

  2018cites this paper
• Better and simpler error analysis of the Sinkhorn–Knopp algorithm for matrix scaling

  2018cites this paper
• UvA-DARE (Digital Academic Repository) Alternating Minimization, Scaling Algorithms, and the Null-Cone Problem from Invariant Theory

  2018cites this paper
• Computational Optimal Transport

  2018cites this paper
• Log-concave polynomials, I: Entropy and a deterministic approximation algorithm for counting bases of matroids

  2018cites this paper
• T he C omputational C omplexity C olumn

  2018cites this paper
• A Tight Analysis of Bethe Approximation for Permanent

  2018influential citation
• On Convex Programming Relaxations for the Permanent

  2017cites this paper
• A Matrix Factorization Approach for Learning Semidefinite-Representable Regularizers

  2017cites this paper
• Approximating the Permanent of a Random Matrix with Vanishing Mean

  2017cites this paper
• Operator Scaling : Theory , Applications and Connections 1

  2017cites this paper
• Analysis of a Classical Matrix Preconditioning Algorithm

  2017influential citation
• Learning Semidefinite Regularizers

  2017cites this paper
• Measuring Anonymity of Pseudonymized Data After Probabilistic Background Attacks

  2017cites this paper
• The Paulsen problem, continuous operator scaling, and smoothed analysis

  2017influential citation
• Much Faster Algorithms for Matrix Scaling

  2017influential citation
• Shortest paths, Markov chains, matrix scaling and beyond : improved algorithms through the lens of continuous optimization

  2017influential citation
• Matrix Scaling and Balancing via Box Constrained Newton's Method and Interior Point Methods

  2017influential citation
• The Paulsen Problem, Continuous Operator Scaling, and Smoothed Analysis

  2017influential citation
• SIAG/OPT Views and News

  2017influential citation
• A general law of large permanent

  2017cites this paper
• Measure concentration and the weak Pinsker property

  2017cites this paper
• Relative entropy optimization and its applications

  2017influential citation
• A review of matrix scaling and Sinkhorn's normal form for matrices and positive maps

  2016influential citation
• Algorithmic and optimization aspects of Brascamp-Lieb inequalities, via Operator Scaling

  2016cites this paper
• Improved Lower Bounds on the Size of Balls Over Permutations With the Infinity Metric

  2016cites this paper
• Some algorithmic applications of partition functions in combinatorics

  2016cites this paper
• Rank bounds for design matrices with block entries and geometric applications

  2016cites this paper
• Approximating permanents and hafnians of positive matrices

  2016cites this paper
• Approximating permanents and hafnians

  2016cites this paper
• Operator Scaling: Theory and Applications

  2015influential citation
• On testing Hamiltonicity of graphs

  2015cites this paper
• Constructive non-commutative rank computation is in deterministic polynomial time

  2015cites this paper
• Analysis of a Classical Matrix Preconditioning Algorithm

  2015cites this paper
• A Deterministic Polynomial Time Algorithm for Non-commutative Rational Identity Testing

  2015influential citation
• Bounds on the size of balls over permutations with the infinity metric

  2015cites this paper
• Lecture 5 : Lowerbound on the Permanent and Application to TSP

  2015cites this paper
• Non-commutative Edmonds’ problem and matrix semi-invariants

  2015cites this paper
• The Scaling Mean and a Law of Large Permanents

  2015influential citation
• Bounds on the Permanent and Some Applications

  2014cites this paper
• Random Gaussian matrices and Hafnian estimators

  2014cites this paper
• Scaling a Unitary Matrix

  2014cites this paper
• Relative Entropy Relaxations for Signomial Optimization

  2014cites this paper
• Computing the Permanent of (Some) Complex Matrices

  2014cites this paper