scientific article; zbMATH DE number 1107717

MaRDI QIDQ4373665zbMATH OpenFDO

Authors Paola Alimonti

Publication date 21 January 1998

zbMATH Keywords

maximum binary conjunctive constraint satisfaction problemmaximum directed cut problem

Mathematics Subject Classification ID

Searching and sorting (68P10)

Recommendations

• A 0. 5-approximation algorithm for MAX DICUT with given sizes of parts
• scientific article; zbMATH DE number 1670527
• Faster algorithms for MAX CUT and MAX CSP, with polynomial expected time for sparse instances

Cited in

(3)

• Oblivious algorithms for the maximum directed cut problem
• Streaming complexity of approximating Max 2CSP and Max Acyclic Subgraph
• From worst case to the average: structural guarantees in k-CSP approximation via orthogonal arrays

Describes a project that uses

Uses Software

• CCSP

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4373665)