On the Efficiency of Convex Polyhedra | Zendy

Enea Zaffanella | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

On the Efficiency of Convex Polyhedra

Author(s) -

Enea Zaffanella

Publication year - 2018

Publication title -

electronic notes in theoretical computer science

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.242

H-Index - 60

ISSN - 1571-0661

DOI - 10.1016/j.entcs.2018.03.004

Subject(s) - polyhedron , regular polygon , domain (mathematical analysis) , computer science , mathematical optimization , exponential function , effective domain , algorithm , integer points in convex polyhedra , convex polytope , convex analysis , theoretical computer science , mathematics , convex optimization , combinatorics , linear programming , geometry , mathematical analysis , branch and price

The domain of convex polyhedra plays a special role in the collection of numerical domains considered for program analysis and verification. As far as precision is concerned, it would be the most natural choice in many contexts but, due to its worst case exponential complexity, it is sometimes considered an unaffordable option. This has led to a systematic quest for simpler domains that are capable of reasonable precision using less computational resources. There are anyway cases where the use of the domain of convex polyhedra turns out to be feasible, also due to recent progress in their implementation. After reviewing a few known approaches to decrease the amount of resources needed when computing on this domain, we will introduce a couple of novel techniques that can be used to further improve its efficiency, without incurring precision losses.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research