Advances in Computational Complexity and Optimization

The field of computational complexity and optimization is witnessing significant developments, with a focus on improving approximation guarantees, hardness results, and optimization techniques. Researchers are exploring new frameworks, such as State Algebra, to represent and manipulate propositional logic, and developing novel algorithms, like DaSAThco, to optimize SAT heuristics. The integration of machine learning and large language models is also becoming increasingly prominent, with applications in areas like nonlinear combinatorial optimization and automated constraint optimization. Furthermore, there is a growing interest in understanding the complexity of representing polynomials by Read-Once Oblivious Algebraic Branching Programs (ROABPs) and the hardness of order finding and equivalence testing for ROABPs. Noteworthy papers include: Improved Approximation Guarantees and Hardness Results for MNL-Driven Product Ranking, which devises a polynomial-time approximation scheme for the market share ranking problem. Learn to Relax with Large Language Models, which introduces an end-to-end automated constraint optimization method for nonlinear combinatorial optimization problems. Variables Ordering Optimization in Boolean Characteristic Set Method Using Simulated Annealing and Machine Learning-based Time Prediction, which presents a novel optimization framework that integrates machine learning-based time prediction with simulated annealing to efficiently identify high-performance variables orderings.

Sources

Improved Approximation Guarantees and Hardness Results for MNL-Driven Product Ranking

Guarded Fragments Meet Dynamic Logic: The Story of Regular Guards (Extended Version)

A Markovian Framing of WaveFunctionCollapse for Procedurally Generating Aesthetically Complex Environments

State Algebra for Propositional Logic

DaSAThco: Data-Aware SAT Heuristics Combinations Optimization via Large Language Models

Learn to Relax with Large Language Models: Solving Nonlinear Combinatorial Optimization Problems via Bidirectional Coevolution

G-CSEA: A Graph-Based Conflict Set Extraction Algorithm for Identifying Infeasibility in Pseudo-Boolean Models

On the Hardness of Order Finding and Equivalence Testing for ROABPs

Variables Ordering Optimization in Boolean Characteristic Set Method Using Simulated Annealing and Machine Learning-based Time Prediction

Built with on top of