8
$\begingroup$

When learning optimization problems, we usually consider linear programming (or more generally: convex optimization) as the simplest example. It is solvable in polynomial time, and has relatively easy to understand algorithms. However, the decision version of LP is $\mathsf{P}$-complete. This suggests that it is one of the hardest problems we can solve in polynomial time.

Under the assumption that $\mathsf{NC} \neq \mathsf{P}$. What is the 'hardest' natural kind of optimization problems with decision problems in $\mathsf{NC}$?

If this is too vague, then we can restrict to restrictions. What is the minimal set of restrictions we need to place on linear programs (or more generally: convex programs) to allow the decision problem associated with the restricted programs to be solvable in $\mathsf{NC}$?

Motivation

To a large extent, this is idle curiosity. However, it was brought about by Cosma Shalizi's "In Soviet Union, Optimization Problem Solves You". In particular, if LP is too difficult to solve to have a centralized economy (i.e. optimizing in $\mathsf{P}$ is asking too much), then any decentralized system must be doing some sort of parallel processing faster than poly-time (for me: $\mathsf{NC}$).

Improve this question
$\endgroup$
1
  • $\begingroup$ Because NC is a hierarchy, you are unlikely to find a "hardest" problem in NC (more precisely: NC does not have complete problems unless the NC hierarchy collapses). Similarly, there is probably not a "universal" minimal set of restrictions on LP to put it into NC, although this seems harder to rule out, even conditioned on natural assumptions. (This is not to detract from the question - I like the question, and it obviously produced some interesting answers - just a remark.) $\endgroup$
    – Joshua Grochow
    Dec 20, 2017 at 19:48

2 Answers 2

Reset to default
10
$\begingroup$

Are you aware of the work on positive LPs/SDPs? There are a bunch of results in the area, mostly along the lines of "if the constraints of the LP/SDP are positive, then the problem can be solved in NC."

Some important references in this line of work are Luby-Nisan 93 and Jain-Yao 11. Another excellent resource is this slide of Rahul Jain's talk at the "Recent Progress in Quantum Algorithms" conference at IQC. The entire talk is available on youtube.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ More precisely, Positive Linear Programming and Positive Semidefinite Programming are optimization problems that are not only exactly solvable in polynomial time (that is, they are in $\mathsf{PO}$), but also admit $\mathsf{NC}$ approximation schemes. They are not solvable exactly in $\mathsf{NC}$ (that is, in $\mathsf{NCO}$) unless $\mathsf{P} = \mathsf{NC}$. $\endgroup$
    – argentpepper
    May 23, 2013 at 17:27
  • $\begingroup$ @argentpepper where is reference that positive SDP and LP is $P$-complete? $\endgroup$
    – Turbo
    Apr 13, 2018 at 17:48
2
$\begingroup$

I am not sure, but you may be interested - if not, I beg your pardon - to the following paper, which is not related to a natural kind of optimization problem, but deals with a problem which can be reduced to a particular optimization problem, whose solution is in NC.

Igor Averbakh, Oded Berman, "Parallel NC-algorithms for multifacility location problems with mutual communication and their applications", Networks, Volume 40, Issue 1, pages 1–12, August 2002, Wiley

DOI: 10.1002/net.10027

Abstract

The generic problem studied is to locate p distinguishable facilities on a tree to satisfy upper-bound constraints on distances between pairs of facilities, given that each facility must be located within its own feasible region, which is defined as a subtree of the tree. We present a parallel location scheme (PLS) for solving the problem that can be implemented as an NC-algorithm. We also introduce parallel NC-algorithms based on the PLS for the minimax versions of the problem, including the distance-constrained p-center problem with mutual communication. Combining the PLS and the improved Megiddo's parametric technique, we develop strongly polynomial serial algorithms for the minimax problems; the algorithms have the best complexities currently available in the literature. Efficient parallel algorithms are given for obtaining optimal regions of the facilities.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.