A Geometric Approach to Betweenness
From MaRDI portal
Publication:4210221
DOI10.1137/S0895480195296221zbMath0912.68058OpenAlexW2010471713WikidataQ29012479 ScholiaQ29012479MaRDI QIDQ4210221
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
Analysis of algorithms and problem complexity (68Q25) Parallel algorithms in computer science (68W10)
Related Items (21)
Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming ⋮ Constraint Satisfaction Problems Parameterized above or below Tight Bounds: A Survey ⋮ Hardness of fully dense problems ⋮ Semidefinite programming in combinatorial optimization ⋮ Expansion of gene clusters, circular orders, and the shortest Hamiltonian path problem ⋮ Sequence Covering Arrays and Linear Extensions ⋮ Unnamed Item ⋮ Satisfying ternary permutation constraints by multiple linear orders or phylogenetic trees ⋮ Simple linear time approximation algorithm for betweenness ⋮ Every ternary permutation constraint satisfaction problem parameterized above average has a kernel with a quadratic number of variables ⋮ Characterization and representation problems for intersection betweennesses ⋮ On Random Betweenness Constraints ⋮ On subbetweennesses of trees: hardness, algorithms, and characterizations ⋮ Seriation in the presence of errors: a factor 16 approximation algorithm for \(l_{\infty }\)-fitting Robinson structures to distances ⋮ Unnamed Item ⋮ Betweenness parameterized above tight lower bound ⋮ Maximizing Polynomials Subject to Assignment Constraints ⋮ A mixed integer linear programming formulation of the maximum betweenness problem ⋮ Inapproximability for metric embeddings into $\mathbb{R}^{d}$ ⋮ Approximation Schemes for the Betweenness Problem in Tournaments and Related Ranking Problems ⋮ On Random Ordering Constraints
This page was built for publication: A Geometric Approach to Betweenness
