Combinatorial Redundancy Detection
| Autor: | Bernd Gärtner, May Szedlák, Komei Fukuda |
|---|---|
| Přispěvatelé: | Arge, Lars, Pach, János |
| Jazyk: | angličtina |
| Rok vydání: | 2015 |
| Předmět: |
Computational Geometry (cs.CG)
FOS: Computer and information sciences Linear programming 0211 other engineering and technologies General Decision Sciences System of linear inequalities Redundancy removal Output sensitive algorithm Clarkson’s method 0102 computer and information sciences 02 engineering and technology Management Science and Operations Research 01 natural sciences Redundancy (information theory) Computer Science - Data Structures and Algorithms FOS: Mathematics Data Structures and Algorithms (cs.DS) Mathematics - Optimization and Control Mathematics Discrete mathematics 021103 operations research 000 Computer science knowledge general works Feasible region Running time Hyperplane Optimization and Control (math.OC) 010201 computation theory & mathematics Theory of computation Computer Science Computer Science - Computational Geometry Output-sensitive algorithm General position |
| Zdroj: | Leibniz International Proceedings in Informatics (LIPIcs), 34 31st International Symposium on Computational Geometry (SoCG 2015) |
| ISSN: | 1868-8969 |
| DOI: | 10.4230/lipics.socg.2015.315 |
| Popis: | The problem of detecting and removing redundant constraints is fundamental in optimization. We focus on the case of linear programs (LPs) in dictionary form, given by n equality constraints in n+d variables, where the variables are constrained to be nonnegative. A variable x_r is called redundant, if after removing its nonnegativity constraint the LP still has the same feasible region. The time needed to solve such an LP is denoted by LP(n,d). It is easy to see that solving n+d LPs of the above size is sufficient to detect all redundancies. The currently fastest practical method is the one by Clarkson: it solves n+d linear programs, but each of them has at most s variables, where s is the number of nonredundant constraints. In the first part we show that knowing all of the finitely many dictionaries of the LP is sufficient for the purpose of redundancy detection. A dictionary is a matrix that can be thought of as an enriched encoding of a vertex in the LP. Moreover - and this is the combinatorial aspect - it is enough to know only the signs of the entries, the actual values do not matter. Concretely we show that for any variable x_r one can find a dictionary, such that its sign pattern is either a redundancy or nonredundancy certificate for x_r. In the second part we show that considering only the sign patterns of the dictionary, there is an output sensitive algorithm of running time of order d (n+d) s^{d-1} LP(s,d) + d s^{d} LP(n,d) to detect all redundancies. In the case where all constraints are in general position, the running time is of order s LP(n,d) + (n+d) LP(s,d), which is essentially the running time of the Clarkson method. Our algorithm extends naturally to a more general setting of arrangements of oriented topological hyperplane arrangements. Leibniz International Proceedings in Informatics (LIPIcs), 34 ISSN:1868-8969 31st International Symposium on Computational Geometry (SoCG 2015) ISBN:978-3-939897-83-5 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|