Katalin Fazekas, Markus Sinnl, Armin Biere, Sophie Parragh,
"Duplex Encoding of Antibandwidth Feasibility Formulas Submitted to the SAT Competition 2020"
, in Tomas Balyo, Nils Froleyks, Marijn Heule, Markus Iser, Matti Järvisalo, Martin Suda: Proc. of SAT Competition 2020 - Solver and Benchmark Descriptions, Serie Department of Computer Science Report Series B, Vol. B-2020-1, University of Helsinki, Seite(n) 81-82, 2020
Original Titel:
Duplex Encoding of Antibandwidth Feasibility Formulas Submitted to the SAT Competition 2020
Sprache des Titels:
Englisch
Original Buchtitel:
Proc. of SAT Competition 2020 - Solver and Benchmark Descriptions
Original Kurzfassung:
This benchmark set is originating in our recent work on the antibandwidth problem (in short ABP) presented in [1]. The ABP is a max-min optimization problem where, for a given graph G= (V,E), the goal is to assign a unique label from the range [1,...,|V|] to each vertex v?V, such that the smallest difference between labels of neighbouring nodes is maximal.Applications of the ABP include for example scheduling,obnoxious facility location, radio frequency assignment. To solve the ABP, in [2] an iterative solution method was proposed, where each iteration asked whether there exists a labelling to the graph, s.t. the smallest difference between labels of neighbours is greater thank. Finding the highest k where the answer is still affirmative determines the optimal solution of the ABP. In [1] we slightly refined the proposed formalization of [2] s.t. the question of each iteration can bestated as combinations of at-most-one constraints sliding overk-long sequences of binary variables.
Forschungs-