From Static Code Distribution to More Shrinkage for the Multiterminal Cut
Author(s) -
Bram De Wachter,
Alexandre Ge,
Thierry Massart
Publication year - 2005
Publication title -
lecture notes in computer science
Language(s) - English
Resource type - Book series
SCImago Journal Rank - 0.249
H-Index - 400
eISSN - 1611-3349
pISSN - 0302-9743
ISBN - 3-540-25920-1
DOI - 10.1007/11427186_17
Subject(s) - heuristics , shrinkage , computer science , code (set theory) , algorithm , mathematical optimization , mathematics , programming language , set (abstract data type) , machine learning , operating system
We present the problem of statically distributing instructions of a common programming language, a problem which we prove equivalent to the multiterminal cut problem. We design efficient shrinkage techniques which allow to reduce the size of an instance in such a way that optimal solutions are preserved. We design and evaluate a fast local heuristics that yields remarkably good results compared to a well known $2-\frac{2}{k}$ approximation algorithm. The use of the shrinkage criterion allows us to increase the size of the instances solved exactly, or to augments the precision of any particular heuristics.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom