A Geometric Approach to Betweenness

DOI10.1137/S0895480195296221zbMATH Open0912.68058OpenAlexW2010471713WikidataQ29012479 ScholiaQ29012479MaRDI QIDQ4210221FDOQ4210221

Authors: Benny Chor, Madhu Sudan 

Publication date: 21 September 1998

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0895480195296221

Recommendations

• A geometric approach to betweenness
• Simple linear time approximation algorithm for betweenness
• On random betweenness constraints
• On Random Betweenness Constraints
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques

zbMATH Keywords

semidefinite programmingapproximation algorithmcomputational biologyNP-completeness

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Parallel algorithms in computer science (68W10)

Cited In (25)

• Every ternary permutation constraint satisfaction problem parameterized above average has a kernel with a quadratic number of variables
• Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming
• Constraint Satisfaction Problems Parameterized above or below Tight Bounds: A Survey
• A geometric approach to betweenness
• Streaming approximation resistance of every ordering CSP
• Seriation in the presence of errors: a factor 16 approximation algorithm for \(l_{\infty }\)-fitting Robinson structures to distances
• A mixed integer linear programming formulation of the maximum betweenness problem
• Approximation schemes for the betweenness problem in tournaments and related ranking problems
• Semidefinite programming in combinatorial optimization
• Betweenness parameterized above tight lower bound
• Title not available (Why is that?)
• Expansion of gene clusters, circular orders, and the shortest Hamiltonian path problem
• On random betweenness constraints
• Title not available (Why is that?)
• Satisfying ternary permutation constraints by multiple linear orders or phylogenetic trees
• Characterization and representation problems for intersection betweennesses
• Hardness of fully dense problems
• Title not available (Why is that?)
• Inapproximability for metric embeddings into $\mathbb{R}^{d}$
• On subbetweennesses of trees: hardness, algorithms, and characterizations
• On Random Betweenness Constraints
• Maximizing Polynomials Subject to Assignment Constraints
• On Random Ordering Constraints
• Simple linear time approximation algorithm for betweenness
• Sequence Covering Arrays and Linear Extensions

This page was built for publication: A Geometric Approach to Betweenness

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4210221)