Filters
LP Relaxations of Some NP-Hard Problems Are as Hard as Any LP
We show that solving linear programming (LP) relaxations of many classical NP problem. Precisely, the general LP can be reduced in linear time to the LP relaxation efficient algorithms to solve the LP<...
Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
- 2017 •
- D •
- Link
Rok uplatnění
D - Stať ve sborníku
Výsledek na webu
Solving LP Relaxations of Some NP-Hard Problems Is As Hard As Solving Any Linear Program
linear time to the LP relaxations of many classical NP-hard combinatorial problems and bounded iff the optimum value of the LP relaxation attains a threshold to the LP relaxation. In the second t...
Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
- 2019 •
- Jimp •
- Link
Rok uplatnění
Jimp - Článek v periodiku v databázi Web of Science
Výsledek na webu
The Power of LP Relaxation for MAP Inference
approachesto this problem is linear programming (LP) relaxation. We discuss this LP relaxation from two aspects. First, we review recent results which characterize languages issolved by the relaxation exa...
JD - Využití počítačů, robotika a její aplikace
- 2014 •
- C •
- Link
Rok uplatnění
C - Kapitola v odborné knize
Výsledek na webu
LP-relaxation of binarized energy minimization
is that they may converge to a suboptimal point. The other LP relaxation we consider here] to the reformulated problem. We refer to the resulting relaxation as LP-2. it as integer linearprogramming and relax
JD - Využití počítačů, robotika a její aplikace
- 2008 •
- O
Rok uplatnění
O - Ostatní výsledky
On Partial Opimality by Auxiliary Submodular Problems
), the linear programming relaxation approach (LP) and the popular expansion move assignment, which is based on LP relaxation and called LP-autarky. We show that methods. Thefollowing link is thus establis...
JD - Využití počítačů, robotika a její aplikace
- 2011 •
- Jx
Rok uplatnění
Jx - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)
Universality of the Local Marginal Polytope
We show that solving the LP relaxation of the MAP inference problem in graphical models (also known as the min-sum problem, energy minimization, or weighted constraint satisfaction) is not easier than solving any LP. More p...
JD - Využití počítačů, robotika a její aplikace
- 2013 •
- D •
- Link
Rok uplatnění
D - Stať ve sborníku
Výsledek na webu
Relaxation of optimal control problems coercive in Lp-spaces.
Annotation not available...
BD - Teorie informace
- 1996 •
- C
Rok uplatnění
C - Kapitola v odborné knize
Unit Propagation by Means of Coordinate-Wise Minimization
We present a novel theoretical result concerning the applicability of coordinate-wise minimization on the dual problem of linear programming (LP) relaxation the particular case of LP relaxation of SAT and observe t...
Mathematics
- 2020 •
- D •
- Link
Rok uplatnění
D - Stať ve sborníku
Výsledek na webu
How to Compute Primal Solution from Dual One in MAP Inference in MRF?
In LP relaxation of MAP inference in Markov random fields (MRF), the primal LP maximizes the MAP objective over relaxed labelings (pseudomarginals) and the dual LP the dual~LP, we have no direct a...
JD - Využití počítačů, robotika a její aplikace
- 2011 •
- Jx
Rok uplatnění
Jx - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)
How Hard Is the LP Relaxation of the Potts Min-Sum Labeling Problem?
the LP relaxation of the Potts min-sum problem is not significantly easier than that trying to find an efficient algorithm to solve the LP relaxation of the Potts min-sum solutions, yielding novel reductions of th...
JD - Využití počítačů, robotika a její aplikace
- 2015 •
- D •
- Link
Rok uplatnění
D - Stať ve sborníku
Výsledek na webu
- 1 - 10 out of 5 986