Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Heuristics:
TR95-030 | 20th June 1995
Marek Karpinski, Alexander Zelikovsky

New Approximation Algorithms for the Steiner Tree Problems

The Steiner tree problem asks for the shortest tree connecting
a given set of terminal points in a metric space. We design
new approximation algorithms for the Steiner tree problems
using a novel technique of choosing Steiner points in dependence
on the possible deviation from ... more >>>

TR99-047 | 10th November 1999
Wolfgang Slany

Graph Ramsey games

We consider combinatorial avoidance and achievement games
based on graph Ramsey theory: The players take turns in coloring
still uncolored edges of a graph G, each player being assigned a
distinct color, choosing one edge per move. In avoidance games,
completing a monochromatic subgraph isomorphic to ... more >>>

TR21-044 | 14th February 2021
Alexander Kulikov, Nikita Slezkin

SAT-based Circuit Local Improvement

Finding exact circuit size is a notorious optimization problem in practice. Whereas modern computers and algorithmic techniques allow to find a circuit of size seven in blink of an eye, it may take more than a week to search for a circuit of size thirteen. One of the reasons of ... more >>>

ISSN 1433-8092 | Imprint