Minimum Mean Cycle Instances

Citation Metadata

Title title

Minimum Mean Cycle Instances

Author author

1. Author Name

   Held, Stephan

   Author Affiliation

   University of Bonn

   Author Identifier Scheme

   ORCID

   Author Identifier

   Type Name

   authorIdentifier

   Multiple

   False

   Type Class

   primitive

   Value

   https://orcid.org/0000-0003-2188-1559

   Expandedvalue

   Person Name

   Held, Stephan

   @id

   https://orcid.org/0000-0003-2188-1559

   Scheme

   ORCID

   @type

   https://schema.org/Person

Dataset Contact datasetContact

1. Dataset Contact Name

   Held, Stephan

   Dataset Contact Affiliation

   University of Bonn

   Dataset Contact Email

   held@dm.uni-bonn.de

Ds Description dsDescription

1. Ds Description Value

   This data set contains some large real-world instances of the minimum mean cycle problem. They are reported as the bonn01 to bonn09 instances in the paper: <br> <br> Georgiadis, L., Goldberg, A. V., Tarjan, R. E., & Werneck, R. F. "An experimental study of minimum mean cycle algorithms", in 2009 Proceedings of the Eleventh Workshop on Algorithm Engineering and Experiments (ALENEX), pp. 1–13, SIAM. <br> <br> The instances arise in clock skew scheduling in chip design, e.g. see <br> <br> Held, S., Korte, B., Rautenbach, D. and Vygen, J. "Combinatorial optimization in VLSI design. Combinatorial Optimization", in Combinatorial Optimization, NATO Science for Peace and Security Series - D: Information and Communication Security, pp. 33–96, 2011. <br> <br> The clock skew scheduling problem in chip design is, given a directed graph G with edge delays d:E(G)-> R, find a minimum cycle time T and arrival times (a schedule) a: V(G) -> R such that <br> <br> a(v) + d(v,w) <= a(w) + T for all (v,w) in E(G). <br> <br> G is called a latch graph. The nodes represent latches and registers, and the edges represent the longest signal paths between registers. <br> The problem of minimizing T is equivalent to maximizing the worst slack min{s(v,w) := a(w) + T - a(v) - d(v,w) | (v,w) in E(G)} for a fixed cycle time T. <br> The instances provided in the tar file below consist of directed graphs with edge costs c(v,w) = T - d(v,w), i.e. edge slacks w.r.t. a zero-skew schedule where a = 0. The maximum achievable worst slack by varying the schedule 'a' equals the value of a minimum mean cycle in (G,c). Instance sizes range from 70346 nodes and 898220 edges to 1065274 nodes and 104340248 edges. Other instances are very dense, e.g. 5361 nodes and 4169878 edges. <br> Note that the instances may not be strongly connected or even connected. Format: Ignore empty lines and lines starting with '#', then: 1st line: number_of_nodes number_of_edges next lines: from_node to_node edge_cost (i.e., zero skew slack)

   Ds Description Date

   2024-02-27

Subject subject

1. Engineering
2. Mathematical Sciences

Subject Refinement subjectRefinement

1. Subject Refinement Value

   combinatorial optimization

Free Keyword freeKeyword

1. Free Keyword Value

   mininum mean-cycle instances

Publication publication

1. Publication Citation

   Georgiadis, L., Goldberg, A. V., Tarjan, R. E., & Werneck, R. F. "An experimental study of minimum mean cycle algorithms", in 2009 Proceedings of the Eleventh Workshop on Algorithm Engineering and Experiments (ALENEX), pp. 1-13, SIAM.

   Publication IDType

   isbn

   Publication IDNumber

   978-0-89871-930-7

   Publication URL

   https://epubs.siam.org/doi/abs/10.1137/1.9781611972894.1

Depositor depositor

Held, Stephan

Date Of Deposit dateOfDeposit

2024-02-27