Sub-polyhedral scheduling using (unit-)two-variable-per-inequality polyhedra

DOI10.1145/2429069.2429127MaRDI QIDQ2931828zbMATH OpenOpenAlexFDO

Authors Ramakrishna Upadrasta, Albert Cohen

Publication date 27 November 2014

Published in Proceedings of the 40th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages (Search for Journal in Brave)

Full work available at URL https://hal.inria.fr/hal-00911888/file/popl070-upadrasta.pdf

zbMATH Keywords

affine schedulingapproximation algorithmscompiler optimizationsloop transformationsoptimizationparallelism

Mathematics Subject Classification ID

Theory of compilers and interpreters (68N20) Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25)

Recommendations

• Polyhedral Reformulation of a Scheduling Problem And Related Theoretical Results
• Approximation algorithms for the multiprocessor scheduling with submodular penalties
• Scheduling two chains of unit jobs on one machine: a polyhedral study
• An analog of the flexible polyhedron method for scheduling problems
• Multiprocessor scheduling under precedence constraints: polyhedral results
• Scheduling lower bounds via AND subset sum
• An approximation scheme for scheduling independent jobs into subcubes of a hypercube of fixed dimension
• On polynomial solvability of two multiprocessor scheduling problems
• Scheduling problem: complexity analysis and polynomially solvable subclasses
• On the extension complexity of scheduling polytopes

Cited in

(3)

• Incremental closure for systems of two variables per inequality
• Neighborhood persistency of the linear optimization relaxation of integer linear optimization
• Neighborhood persistency of the linear optimization relaxation of integer linear optimization

Describes a project that uses

Uses Software

• Apron
• PPL

This page was built for publication: Sub-polyhedral scheduling using (unit-)two-variable-per-inequality polyhedra

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2931828)