Matthew Anderson
Anuj Dawar
Skip Abstract Section
Abstract
We show that the ellipsoid method for solving linear programs can be implemented in a way that respects the symmetry of the program being solved. That is to say, there is an algorithmic implementation of the method that does not distinguish, or make choices, between variables or constraints in the program unless they are distinguished by properties definable from the program. In particular, we demonstrate that the solvability of linear programs can be expressed in fixed-point logic with counting (FPC) as long as the program is given by a separation oracle that is itself definable in FPC. We use this to show that the size of a maximum matching in a graph is definable in FPC. This settles an open problem first posed by Blass, Gurevich and Shelah [Blass et al. 1999]. On the way to defining a suitable separation oracle for the maximum matching program, we provide FPC formulas defining canonical maximum flows and minimum cuts in undirected capacitated graphs.
- M. Anderson and A. Dawar. 2014. On symmetric circuits and fixed-point logics. In Proceedings of STACS. LIPIcs, 41--52.Google Scholar
- M. Anderson, A. Dawar, and B. Holm. 2013. Maximum matching and linear programming in fixed-point logic with counting. In Proceedings of LICS. IEEE, 173--182. Google ScholarDigital Library
- A. Atserias, A. Bulatov, and A. Dawar. 2009. Affine systems of equations and counting infinitary logic. Theor. Comput. Sci. 410, 18, 1666--1683. Google ScholarDigital Library
- A. Atserias and E. Maneva. 2012. Sherali-Adams relaxations and indistinguishability in counting logics. In Proceedings of ITCS. ACM, 367--379. Google ScholarDigital Library
- A. Blass and Y. Gurevich. 2005. A quick update on open problems in Blass-Gurevich-Shelah's article ‘On polynomial time computations over unordered structures’. Online at http://research.microsoft.com/_gurevich/annotated.html.Google Scholar
- A. Blass, Y. Gurevich, and S. Shelah. 1999. Choiceless polynomial time. Ann. Pure Appl. Logic 100, 141--187.Google ScholarCross Ref
- A. Blass, Y. Gurevich, and S. Shelah. 2002. On polynomial time computation over unordered structures. J. Symbolic Logic 67, 3, 1093--1125.Google ScholarCross Ref
- J.-Y. Cai, M. Fürer, and N. Immerman. 1992. An optimal lower bound on the number of variables for graph identification. Combinatorica 12, 4, 389--410.Google ScholarCross Ref
- A. Caprara and M. Fischetti. 1996. {0, 1/2}-Chvátal-Gomory cuts. Math. Program. 74, 3, 221--235. Google ScholarCross Ref
- A. Chandra and D. Harel. 1982. Structure and complexity of relational queries. J. Comput. Syst. Sci. 25, 1, 99--128.Google ScholarCross Ref
- T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. 2009. Introduction to Algorithms (3. ed.). MIT Press. Google ScholarDigital Library
- G. Dantzig. 1963. Linear Programming and Extensions. Princeton University Press.Google Scholar
- A. Dawar, M. Grohe, B. Holm, and B. Laubner. 2009. Logics with Rank Operators. In Proceedings of LICS. IEEE, 113--122. Google ScholarDigital Library
- E. A. Dinitz, A. V. Karazanov, and M. V. Lomonosov. 1976. On the structure of the system of minimum edge cuts in a graph. Studies in Discrete Optimizations, 290--306. In Russian.Google Scholar
- D. Dobkin, R. J. Lipton, and S. Reiss. 1979. Linear programming is log-space hard for P. Inform. Process. Lett. 8, 2 (1979), 96--97.Google ScholarCross Ref
- R. Duan and S. Pettie. 2014. Linear-time approximation for maximum weight matching. J. ACM 61, 1, Article 1, 23 pages. DOI:http://dx.doi.org/10.1145/2529989 Google ScholarDigital Library
- H. D. Ebbinghaus and J. Flum. 1999. Finite Model Theory. Springer.Google Scholar
- J. Edmonds. 1965. Maximum matching and a polyhedron with 0; 1 vertices. J. Res. Nat. Bur. Stand. 69 B, 125--130.Google ScholarCross Ref
- M. X. Goemans and V. S. Ramakrishnan. 1995. Minimizing submodular functions over families of sets. Combinatorica 15, 4, 499--513.Google ScholarCross Ref
- M. Grohe. 2012. Fixed-point definability and polynomial time on graphs with excluded minors. J. ACM 59, 5, Article 27, 64 pages. Google ScholarDigital Library
- M. Grohe, K. Kersting, M. Mladenov, and E. Selman. 2013. Dimension Reduction via Colour Refinement. CoRR abs/1307.5697 (2013), 17 pages.Google Scholar
- M. Grohe and M. Otto. 2012. Pebble Games and Linear Equations. In Proceedings of CSL. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 289--304. DOI:http://dx.doi.org/10.4230/LIPIcs.CSL.2012.289Google Scholar
- M. Grötschel, L. Lovász, and A. Schrijver. 1981. The ellipsoid method and its consequences in combinatorial optimization. Combinatorica 1, 2, 169--197.Google ScholarCross Ref
- M. Grötschel, L. Lovász, and A. Schrijver. 1988. Geometric Algorithms and Combinatorial Optimization. Springer.Google Scholar
- B. Holm. 2010. Descriptive Complexity of Linear Algebra. Ph.D. Dissertation. University of Cambridge.Google Scholar
- N. Immerman. 1986. Relational queries computable in polynomial time. Inform. Control 68, 1--3 (1986), 86--104. Google ScholarDigital Library
- N. Immerman. 1999. Descriptive Complexity. Springer-Verlag.Google Scholar
- N. Karmarkar. 1984. A new polynomial-time algorithm for linear programming. In Proceedings of STOC. ACM, 302--311. Google ScholarDigital Library
- L. G. Khachiyan. 1980. Polynomial algorithms in linear programming. USSR Comp. Math. Math 20, 1, 53--72.Google ScholarCross Ref
- V. Klee and G. J. Minty. 1972. How good is the simplex algorithm? In Proceedings of the 3rd Symposium on Inequalities, Oved. Shisha (Ed.). Academic Press, New York-London, 159--175.Google Scholar
- B. Laubner. 2011. The Structure of Graphs and New Logics for the Characterization of Polynomial Time. Ph.D. Dissertation. Humboldt-Universitt zu Berlin.Google Scholar
- A. N. Letchford, G. Reinelt, and D. O. Theis. 2004. A faster exact separation algorithm for blossom inequalities. In Integer Programming and Combinatorial Optimization. Springer, 196--205.Google Scholar
- L. Libkin. 2004. Elements of Finite Model Theory. Springer. Google ScholarDigital Library
- S. Micali and V. V. Vazirani. 1980. An O(√|V||E|) algorithm for finding maximum matching in general graphs. In Proceedings of the 21st Annual Symposium on Foundations of Computer Science. IEEE, 17--27. Google ScholarDigital Library
- M. W. Padberg and M. R. Rao. 1982. Odd minimum cut-sets and b-matchings. Math. Oper. Res. 7, 1, 67--80. Google ScholarDigital Library
- B. Rossman. 2010. Choiceless computation and symmetry. In Fields of Logic and Computation. Springer, 565--580. Google ScholarDigital Library
- T. Rothvoß. 2013. The matching polytope has exponential extension complexity. CoRR abs/1311.2369 (2013), 19 pages.Google Scholar
- H. D. Sherali and W. P. Adams. 1990. A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems. SIAM J. Discrete Math. 3, 3, 411--430. Google ScholarDigital Library
- N. Z. Shor. 1972. Utilization of the operation of space dilatation in the minimization of convex functions. Cybern. Syst. Anal. 6, 1, 7--15.Google ScholarCross Ref
- N. Z. Shor. 1977. Cut-off method with space extension in convex programming problems. Cybern. Syst. Anal. 13, 1, 94--96.Google Scholar
- D. A. Spielman and S.-H. Teng. 2004. Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time. J. ACM 51, 3, 385--463. Google ScholarDigital Library
- M. Vardi. 1982. The complexity of relational query languages. In Proceedings of STOC. ACM, 137--146. Google ScholarDigital Library
- V. V. Vazirani. 1994. A theory of alternating paths and blossoms for proving correctness of the O(√ V E) general graph maximum matching algorithm. Combinatorica 14, 71--109.Google ScholarCross Ref
- D. B. Yudin and A. S. Nemirovskii. 1976. Informational complexity and efficient methods for the solution of convex extremal problems. Matekon 13, 2, 3--25.Google Scholar
Index Terms
- Solving Linear Programs without Breaking Abstractions
Recommendations
Maximum Matching and Linear Programming in Fixed-Point Logic with Counting
LICS '13: Proceedings of the 2013 28th Annual ACM/IEEE Symposium on Logic in Computer ScienceWe establish the expressibility in fixed-point logic with counting (FPC) of a number of natural polynomial-time problems. In particular, we show that the size of a maximum matching in a graph is definable in FPC. This settles an open problem first posed ...
Definability of Cai-Fürer-Immerman Problems in Choiceless Polynomial Time
Choiceless Polynomial Time (CPT) is one of the most promising candidates in the search for a logic capturing Ptime. The question whether there is a logic that expresses exactly the polynomial-time computable properties of finite structures, which has ...
On Linear Characterizations of Combinatorial Optimization Problems
We show that there can be no computationally tractable description by linear inequalities of the polyhedron associated with any NP-complete combinatorial optimization problem unless NP = co-NP—a very unlikely event. We also apply the ellipsoid method for ...
Comments