caa a22 4500 445878010 CHVBK 20180317145533.0 cr unu---uuuuu 170323e20111201xx s 000 0 eng 10.1007/s11081-010-9128-9 doi (NATIONALLICENCE)springer-10.1007/s11081-010-9128-9 On VLSI interconnect optimization and linear ordering problem [Elektronische Daten] [Shmuel Wimer, Konstantin Moiseev, Avinoam Kolodny] Some well-known VLSI interconnect optimizations problems for timing, power and cross-coupling noise immunity share a property that enables mapping them into a specialized Linear Ordering Problem (LOP). Unlike the general LOP problem which is NP-complete, this paper proves that the specialized one has a closed-form solution. Let f(x,y):ℝ2→ℝ be symmetric, non-negative, defined for x≥0 and y≥0, and let f(x,y) be twice differentiable, satisfying ∂ 2 f(x,y)/∂x∂y<0. Let π be a permutation of {1, ,n}. The specialized LOP comprises n objects, each associated with a real value parameter r i, 1≤i≤n, and a cost f(r i,r j) associated to any two objects if |π(i)−π(j)|=1,1≤i,j≤n, and f(r i,r j)=0 otherwise. We show that the permutation π which minimizes $\sum_{i= 1}^{n - 1} f( r_{\pi^{ - 1}( i )},r_{\pi^{ - 1}( i + 1 )} )$, called "symmetric hill”, is determined upfront by the relations between the parameter valuesr i. Springer Science+Business Media, LLC, 2010 VLSI interconnects optimization nationallicence Delay minimization nationallicence Power minimization nationallicence Linear ordering problem nationallicence Optimal permutation nationallicence Wimer Shmuel School of Engineering, Bar-Ilan University, Ramat-Gan, Israel aut Moiseev Konstantin Electrical Engineering Department, Technion, Haifa, Israel aut Kolodny Avinoam Electrical Engineering Department, Technion, Haifa, Israel aut Optimization and Engineering Springer US; http://www.springer-ny.com 12/4(2011-12-01), 603-609 1389-4420 12:4<603 2011 12 11081 https://doi.org/10.1007/s11081-010-9128-9 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s11081-010-9128-9 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Wimer Shmuel School of Engineering, Bar-Ilan University, Ramat-Gan, Israel aut NATIONALLICENCE 700 1- Moiseev Konstantin Electrical Engineering Department, Technion, Haifa, Israel aut NATIONALLICENCE 700 1- Kolodny Avinoam Electrical Engineering Department, Technion, Haifa, Israel aut NATIONALLICENCE 773 0- Optimization and Engineering Springer US; http://www.springer-ny.com 12/4(2011-12-01), 603-609 1389-4420 12:4<603 2011 12 11081 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer