An LP-designed algorithm for constraint satisfaction

An LP-designed algorithm for constraint satisfaction

The class Max (r, 2)-CSP consists of constraint satisfaction problems with at most two r-valued variables per clause. For instances with n variables and m binary clauses, we present an (O) over tilde (r(19m/100))-time algorithm. It is the fastest algorithm for most problems in the class (including M...

Descripció completa

Dades bibliogràfiques
Autors principals:	Scott, A, Sorkin, G
Format:	Conference item
Publicat:	2006

Ítems similars

Polynomial Constraint Satisfaction Problems, Graph Bisection, and the Ising Partition Function
per: Scott, A, et al.
Publicat: (2009)

Linear-programming design and analysis of fast algorithms for Max 2-CSP
per: Scott, A, et al.
Publicat: (2007)

LP Well-Posedness for Bilevel Vector Equilibrium and Optimization Problems with Equilibrium Constraints
per: Phan Quoc Khanh, et al.
Publicat: (2014-01-01)

Message-Passing Algorithms and Improved LP Decoding
per: Arora, Sanjeev, et al.
Publicat: (2021)

Lp quasi-norm minimization: algorithm and applications
per: Omar M. Sleem, et al.
Publicat: (2024-02-01)

Algorithms and ordering heuristics for distributed constraint satisfaction problems /
per: Mohamed Wahbi
Publicat: (2013)

Lp-Curvature Measures and Lp,q-Mixed Volumes
per: Tongyi Ma
Publicat: (2022-01-01)

Intermodal-vectorial four-wave mixing processes involving LP01, LP11, LP02 and LP21 modes of birefringent fibers
per: Tarnowski Karol, et al.
Publicat: (2023-01-01)

Regression-based LP Solver for Chance-Constrained Finite Horizon Optimal Control with Nonconvex Constraints
per: Banerjee, Ashis, et al.
Publicat: (2011)

An Adaptive Lp Norm Minimization Algorithm for Direction of Arrival Estimation
per: Lutao Liu, et al.
Publicat: (2022-02-01)

Experiments with Active-Set LP Algorithms Allowing Basis Deficiency
per: Pablo Guerrero-García, et al.
Publicat: (2022-12-01)

SCIAMACHY stratospheric aerosol extinction profile retrieval using the OMPS/LP algorithm
per: G. Taha, et al.
Publicat: (2011-03-01)

Improved ant colony optimization algorithm for solving constraint satisfaction problem
per: HANGYong-gang Z, et al.
Publicat: (2015-05-01)

Improved ant colony optimization algorithm for solving constraint satisfaction problem
per: HANGYong-gang Z, et al.
Publicat: (2015-05-01)

A matrix-based IRLS algorithm for the least lp-norm design of 2-D FIR filters
per: Zhao, Ruijie, et al.
Publicat: (2020)

Transformations of representation in constraint satisfaction
per: Salamon, A
Publicat: (2013)

On the Complexity of ID/LP Parsing
per: Barton, G. Edward, Jr.
Publicat: (2004)

Promise constraint satisfaction problems
per: Brandts-Longtin, A
Publicat: (2022)

LP-033 A study of treatment satisfaction in the patients with rheumatoid arthritis and systemic lupus erythematous
per: Han Joo Baek, et al.
Publicat: (2023-07-01)

The complexity of soft constraint satisfaction
per: Cohen, D, et al.
Publicat: (2006)

The complexity of soft constraint satisfaction
per: Cohen, D, et al.
Publicat: (2006)

HyperConsistency Width For Constraint Satisfaction
per: Marnette, B, et al.
Publicat: (2009)

Constraint satisfaction modules : a methodology for analog circuit design
per: Mitros, Piotr, 1979-
Publicat: (2008)

Variational product design by constraint propagation and satisfaction in product modelling /
per: 259518 Fumihiko Kimura, et al.

LP-based subgradient algorithm for joint pricing and inventory control problems
per: Rao, Tingting
Publicat: (2009)

Lp-approximation for Shepard operators(Shepard算子的Lp-逼近)
per: XIAOWei(肖伟), et al.
Publicat: (2000-07-01)

General complex Lp projection bodies and complex Lp mixed projection bodies
per: Cheng Manli, et al.
Publicat: (2022-04-01)

Hybrid tractability of constraint satisfaction problems with global constraints
per: Thorstensen, E
Publicat: (2013)

Enzyme-linked immunoassay for Lp[a].
per: G M Fless, et al.
Publicat: (1989-05-01)

SCLE-LP overlap syndrome
per: C Shanmuga Sekar, et al.
Publicat: (2011-01-01)

On the valued constraint satisfaction problem
per: Fulla, P
Publicat: (2018)

Reason maintenance in constraint satisfaction
per: Tay, Joc Cing.
Publicat: (2008)

Renovascular arteriovenous differences in Lp[a] plasma concentrations suggest removal of Lp[a] from the renal circulation
per: F Kronenberg, et al.
Publicat: (1997-09-01)

Criterion on Lp1×Lp2→Lq-Boundedness for Oscillatory Bilinear Hilbert Transform
per: Zuoshunhua Shi, et al.
Publicat: (2014-01-01)

Constraint satisfaction problems and finite algebras
per: Bulatov, A, et al.
Publicat: (2000)

Constraint satisfaction problems and finite algebras
per: Bulatov, A, et al.
Publicat: (2000)

The Complexity of Constraint Satisfaction: An Algebraic Approach
per: Krokhin, A, et al.
Publicat: (2004)

The constraint satisfaction problem: complexity and approximability
per: Krokhin, A, et al.
Publicat: (2017)

The complexity of constraint satisfaction games and QCSP
per: Börner, F, et al.
Publicat: (2009)

The complexity of constraint satisfaction games and QCSP
per: Boerner, F, et al.
Publicat: (2009)