Advances in Combinatorial Modeling and Algorithmic Techniques

The field of combinatorial modeling and algorithmic techniques is witnessing significant developments, with a focus on capturing higher-order dependencies and complex relationships in large data sets. Researchers are introducing new combinatorial models and algorithms to analyze and reconstruct complex phenomena, such as sets of strings from their k-way projections. Additionally, there is a growing interest in constrained clustering problems, including connected clustering, which has applications in community detection and geodesy. Furthermore, advancements in phylogenetic networks and tree containment problems are being made, with a focus on robustness to uncertainty and poorly supported branches in biological data. Noteworthy papers in this area include:

  • A paper that introduces a new algorithm for reconstructing sets of strings from their k-way projections, using a modified version of overlap graphs from genetic reconstruction algorithms.
  • A paper that provides hardness results and approximation algorithms for connected clustering problems, including an Omega(log*(k))-hardness result for connected k-center and a (3 + epsilon)-approximation algorithm for connected min-sum-radii.
  • A paper that presents an algorithm for solving Soft Tree Containment in phylogenetic networks, leveraging the fact that networks often exhibit low scanwidth, making the problem more tractable.

Sources

Reconstructing Sets of Strings from Their k-way Projections: Algorithms & Complexity

New Algorithms and Hardness Results for Connected Clustering

Exploiting Low Scanwidth to Resolve Soft Polytomies

Local generation of languages

Built with on top of