Document Open Access Logo

Learning Lines with Ordinal Constraints

Authors Bohan Fan, Diego Ihara , Neshat Mohammadi, Francesco Sgherzi, Anastasios Sidiropoulos, Mina Valizadeh

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2020.45.pdf
  • Filesize: 483 kB
  • 15 pages

Document Identifiers

Author Details

Bohan Fan
  • Department of Computer Science, University of Illinois at Chicago, IL, USA
Diego Ihara
  • Department of Computer Science, University of Illinois at Chicago, IL, USA
Neshat Mohammadi
  • Department of Computer Science, University of Illinois at Chicago, IL, USA
Francesco Sgherzi
  • Department of Computer Science, University of Illinois at Chicago, IL, USA
Anastasios Sidiropoulos
  • Department of Computer Science, University of Illinois at Chicago, IL, USA
Mina Valizadeh
  • Department of Computer Science, University of Illinois at Chicago, IL, USA

Funding

Supported by NSF grants CCF-1815145, CCF-1934915, and by NSF CAREER award 1453472.

Cite As Get BibTex

Bohan Fan, Diego Ihara, Neshat Mohammadi, Francesco Sgherzi, Anastasios Sidiropoulos, and Mina Valizadeh. Learning Lines with Ordinal Constraints. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 45:1-45:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2020.45

Abstract

We study the problem of finding a mapping f from a set of points into the real line, under ordinal triple constraints. An ordinal constraint for a triple of points (u,v,w) asserts that |f(u)-f(v)| < |f(u)-f(w)|. We present an approximation algorithm for the dense case of this problem. Given an instance that admits a solution that satisfies (1-ε)-fraction of all constraints, our algorithm computes a solution that satisfies (1-O(ε^{1/8}))-fraction of all constraints, in time O(n⁷) + (1/ε)^{O(1/ε^{1/8})} n.

Subject Classification

ACM Subject Classification
  • Theory of computation → Approximation algorithms analysis
Keywords
  • metric learning
  • embedding into the line
  • ordinal constraints
  • approximation algorithms

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

Supplementary Materials

References

  1. Nir Ailon and Noga Alon. Hardness of fully dense problems. Information and Computation, 205(8):1117-1129, 2007. Google Scholar
  2. Noga Alon, Mihai Bădoiu, Erik D Demaine, Martin Farach-Colton, MohammadTaghi Hajiaghayi, and Anastasios Sidiropoulos. Ordinal embeddings of minimum relaxation: general properties, trees, and ultrametrics. ACM Transactions on Algorithms (TALG), 4(4):1-21, 2008. Google Scholar
  3. Mihai Badoiu. Approximation algorithm for embedding metrics into a two-dimensional space. In Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, pages 434-443. Society for Industrial and Applied Mathematics, 2003. Google Scholar
  4. Mihai Bădoiu, Erik D Demaine, MohammadTaghi Hajiaghayi, Anastasios Sidiropoulos, and Morteza Zadimoghaddam. Ordinal embedding: Approximation algorithms and dimensionality reduction. In Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques, pages 21-34. Springer, 2008. Google Scholar
  5. Mihai Badoiu, Kedar Dhamdhere, Anupam Gupta, Yuri Rabinovich, Harald Räcke, Ramamoorthi Ravi, and Anastasios Sidiropoulos. Approximation algorithms for low-distortion embeddings into low-dimensional spaces. In SODA, volume 5, pages 119-128. Citeseer, 2005. Google Scholar
  6. Mihai Bǎdoiu, Julia Chuzhoy, Piotr Indyk, and Anastasios Sidiropoulos. Low-distortion embeddings of general metrics into the line. In Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, pages 225-233. ACM, 2005. Google Scholar
  7. Timothy Carpenter, Fedor V Fomin, Daniel Lokshtanov, Saket Saurabh, and Anastasios Sidiropoulos. Algorithms for low-distortion embeddings into arbitrary 1-dimensional spaces. In 34th International Symposium on Computational Geometry (SoCG 2018). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018. Google Scholar
  8. Moses Charikar, Venkatesan Guruswami, and Rajsekar Manokaran. Every permutation csp of arity 3 is approximation resistant. In 2009 24th Annual IEEE Conference on Computational Complexity, pages 62-73. IEEE, 2009. Google Scholar
  9. Benny Chor and Madhu Sudan. A geometric approach to betweenness. SIAM Journal on Discrete Mathematics, 11(4):511-523, 1998. Google Scholar
  10. Kedar Dhamdhere, Anupam Gupta, and R. Ravi. Approximation algorithms for minimizing average distortion. Theory Comput. Syst., 39(1):93-111, 2006. URL: https://doi.org/10.1007/s00224-005-1259-6.
  11. Michael R Fellows, Fedor V Fomin, Daniel Lokshtanov, Elena Losievskaja, Frances A Rosamond, and Saket Saurabh. Distortion is fixed parameter tractable. In International Colloquium on Automata, Languages, and Programming, pages 463-474. Springer, 2009. Google Scholar
  12. Diego Ihara, Neshat Mohammadi, Francesco Sgherzi, and Anastasios Sidiropoulos. Robust mahalanobis metric learning via geometric approximation algorithms. CoRR, abs/1905.09989, 2019. URL: http://arxiv.org/abs/1905.09989.
  13. Diego Ihara, Neshat Mohammadi, and Anastasios Sidiropoulos. Algorithms for metric learning via contrastive embeddings. In 35th International Symposium on Computational Geometry (SoCG 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2019. Google Scholar
  14. Piotr Indyk, Jiří Matoušek, and Anastasios Sidiropoulos. Low-distortion embeddings of finite metric spaces. In Jacob E. Goodman, Joseph O'Rourke, and Csaba D. Toth, editors, Handbook of Discrete and Computational Geometry, Second Edition. Chapman and Hall/CRC, 2017. Google Scholar
  15. Marek Karpinski and Warren Schudy. Approximation schemes for the betweenness problem in tournaments and related ranking problems. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pages 277-288. Springer, 2011. Google Scholar
  16. Claire Kenyon-Mathieu and Warren Schudy. How to rank with few errors. In Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, pages 95-103, 2007. Google Scholar
  17. Brian Kulis et al. Metric learning: A survey. Foundations and Trendsregistered in Machine Learning, 5(4):287-364, 2013. Google Scholar
  18. Yury Makarychev. Simple linear time approximation algorithm for betweenness. Operations research letters, 40(6):450-452, 2012. Google Scholar
  19. Amir Nayyeri and Benjamin Raichel. Reality distortion: Exact and approximate algorithms for embedding into the line. In Foundations of Computer Science (FOCS), 2015 IEEE 56th Annual Symposium on, pages 729-747. IEEE, 2015. Google Scholar
  20. Amir Nayyeri and Benjamin Raichel. A treehouse with custom windows: Minimum distortion embeddings into bounded treewidth graphs. In Philip N. Klein, editor, Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 724-736. SIAM, 2017. URL: https://doi.org/10.1137/1.9781611974782.46.
  21. Jaroslav Opatrny. Total ordering problem. SIAM Journal on Computing, 8(1):111-114, 1979. Google Scholar
  22. Yuri Rabinovich. On average distortion of embedding metrics into the line and into l1. In Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, pages 456-462, 2003. Google Scholar
  23. Gregory Shakhnarovich. Learning task-specific similarity. PhD thesis, Massachusetts Institute of Technology, 2005. Google Scholar
  24. Csaba D Toth, Joseph O'Rourke, and Jacob E Goodman. Handbook of discrete and computational geometry. Chapman and Hall/CRC, 2017. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact