Approximation algorithms for bipartite matching with metric and geometric costs
DOI10.1145/2591796.2591844zbMATH Open1315.05104OpenAlexW2079168081MaRDI QIDQ5259591FDOQ5259591
R. Sharathkumar, Pankaj K. Agarwal
Publication date: 26 June 2015
Published in: Proceedings of the forty-sixth annual ACM symposium on Theory of computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/2591796.2591844
Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Signed and weighted graphs (05C22) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Theory of Cryptography
- The geometry of differential privacy: the small database and approximate cases
- On the geometry of differential privacy
- Interactive privacy via the median mechanism
- The price of privately releasing contingency tables and the spectra of random matrices with correlated rows
- Lower Bounds in Differential Privacy
- Iterative Constructions and Private Data Release
- Differential Privacy and the Fat-Shattering Dimension of Linear Queries
- Our Data, Ourselves: Privacy Via Distributed Noise Generation
- On the complexity of differentially private data release
- Collusion-secure fingerprinting for digital data
- Advances in Cryptology – CRYPTO 2004
- New Efficient Attacks on Statistical Disclosure Control Mechanisms
- Bounds on the Sample Complexity for Private Learning and Private Data Release
- Answering n {2+o(1)} counting queries with differential privacy is hard
- Characterizing the sample complexity of private learners
- Faster Algorithms for Privately Releasing Marginals
- Faster private release of marginals on small databases
- Private Learning and Sanitization: Pure vs. Approximate Differential Privacy
- Privately releasing conjunctions and the statistical query barrier
- Efficient algorithms for privately releasing marginals via convex relaxations
Cited In (14)
- Towards optimal running timesfor optimal transport
- Title not available (Why is that?)
- Optimal transport: discretization and algorithms
- An 0(n log n) algorithm for the convex bipartite matching problem
- Title not available (Why is that?)
- Title not available (Why is that?)
- A Near-linear Time ε-Approximation Algorithm for Geometric Bipartite Matching
- A near-linear time ε-approximation algorithm for geometric bipartite matching
- Geometry Helps to Compare Persistence Diagrams
- Bi-objective matchings with the triangle inequality
- Distribution-Free Consistent Independence Tests via Center-Outward Ranks and Signs
- On universally consistent and fully distribution-free rank tests of vector independence
- Preconditioning for the Geometric Transportation Problem
- Parameterized and Approximation Algorithms for Finding Two Disjoint Matchings
Uses Software
This page was built for publication: Approximation algorithms for bipartite matching with metric and geometric costs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5259591)
