betaFeedback

WorksComputer Science

Parameterized Approximation of Max k-Weight CSP: A Dichotomy for Boolean Languages

Abstract

We study \textsc{Max kk-Weight CSP}: maximize the satisfied weight of Boolean constraints with nonnegative rational weights by setting at most kk variables to 11. Each constraint uses at most dd distinct variables and a relation from a finite Boolean language ΓΓ. This includes Partial Vertex Cover, \textsc{Densest kk-Subgraph}, bounded-frequency Maximum Coverage, and cardinality-constrained Max-SAT. We completely classify the fixed finite languages admitting an efficient parameterized approximation scheme (EPAS) with parameter k+dk+d. Only nonempty relations excluding the all-zero tuple matter. For such a relation, a coordinate is a unit witness if the tuple with a single 11 in that coordinate is accepted, and a control otherwise. A relation is Direct if setting any selected control to 00, with all other coordinates unchanged, preserves satisfaction. It is Rooted if every satisfying tuple has a selected unit witness such that keeping it, setting all other unit witnesses to 00, and setting any subset of selected controls to 00 preserves satisfaction. If all such relations are Direct, or all are Rooted, we give a deterministic (1−ε)(1-\varepsilon)-approximation for every rational ε∈(0,1)\varepsilon\in(0,1) in time 2O(d+klog⁡(1+dk/ε))ℓinO(1)2^{O(d+k\log(1+dk/\varepsilon))}\ell_{\mathrm{in}}^{O(1)}, where ℓin\ell_{\mathrm{in}} is the total input length. The algorithms are uniform in dd and give an EPAS parameterized by k+dk+d whenever relation membership is polynomial-time decidable. If neither condition holds, no EPAS exists unless FPT=W[1]\mathsf{FPT}=\mathsf{W[1]}, even for unweighted instances where no two constraints involve the same set of variables.

Introduction

We study Boolean constraint satisfaction problems (CSPs). An instance consists of a finite set XX of variables, each taking a value in {0,1}\{0,1\}, and a finite collection C\mathcal{C} of constraints. Let dd be an upper bound on all constraint arities. A constraint CC of arity r≤dr \le d is specified by a tuple (x1,…,xr)(x_1,\ldots,x_r) of variables and a relation RC⊆{0,1}rR_C \subseteq\{0,1\}^r. We call the positions 1,…,r1,\ldots,r the coordinates of the relation and of the constraint. An assignment τ:X→{0,1}\tau:X\to\{0,1\} satisfies CC if (τ(x1),…,τ(xr))∈RC(\tau(x_1),\ldots,\tau(x_r))\in R_C. We write 0r\mathbf{0}_r and 1r\mathbf{1}_r for the all-zero and all-one tuples in {0,1}r\{0,1\}^r, omitting the subscript when the arity is clear. Throughout this paper, the variables x1,…,xrx_1,\ldots,x_r of every constraint CC are pairwise distinct. This assumption affects the classification; see Remark 2.3. We write sc⁡(C):={x1,…,xr}\operatorname{sc}(C):=\{x_1,\ldots,x_r\} for the set of variables of CC and call it the underlying scope set of CC; thus ∣sc⁡(C)∣=r|\operatorname{sc}(C)|=r. A Boolean constraint language Γ\Gamma is a finite set of relations, and an instance is over Γ\Gamma if RC∈ΓR_C\in\Gamma for every C∈CC\in\mathcal{C}.

The input to Max kk-Weight CSP is a CSP instance (X,C)(X,\mathcal{C}) together with a nonnegative rational weight w(C)w(C) for every constraint C∈CC\in\mathcal{C} and a nonnegative integer budget kk. The Hamming weight wt⁡(τ):=∣τ−1(1)∣\operatorname{wt}(\tau) := |\tau^{-1}(1)| of an assignment τ\tau is the number of variables it sets to 1. The goal is to find an assignment τ\tau with wt⁡(τ)≤k\operatorname{wt}(\tau) \le k that maximizes the total weight of the constraints it satisfies. The unweighted case has w(C)=1w(C) = 1 for every C∈CC \in\mathcal{C}. For a constraint language Γ\Gamma, Max kk-Weight CSP(Γ\Gamma) is the restriction to instances over Γ\Gamma.

For an instance, let n:=∣X∣n := |X| and m:=∣C∣m := |\mathcal{C}|. All accuracy parameters are rational. Let ℓin\ell_{\mathrm{in}} be the total number of bits used to encode the input, including the weights, budget, accuracy parameters when present, and any relation descriptions supplied as part of the input. All running times count bit operations.

An efficient parameterized approximation scheme (EPAS) for Max kk-Weight CSP(Γ\Gamma), for a fixed Γ\Gamma, parameterized by kk, is an algorithm that, given an instance and ε∈(0,1)\varepsilon\in(0,1), returns an assignment τ\tau with wt⁡(τ)≤k\operatorname{wt}(\tau) \le k of value at least (1−ε)(1-\varepsilon) times the optimum, in time f(k,ε)ℓinO(1)f(k,\varepsilon)\ell_{\mathrm{in}}^{O(1)} for a computable function ff. When dd varies, an EPAS parameterized by k+dk+d uses one algorithm running in time f(k,d,ε)ℓinO(1)f(k,d,\varepsilon)\ell_{\mathrm{in}}^{O(1)}.

Max kk-Weight CSP contains Partial Vertex Cover [19, 23], Maximum Coverage [1, 29, 30], cardinality-constrained Max-SAT [16, 21], and Max Cut with at most kk vertices on one side [2] as special cases (§ 1.2). Earlier work also gives approximation schemes for several of these problems through common frameworks [14, 15, 16, 18]. Can the parameterized approximability of these problems be determined uniformly by the permitted relations alone? More precisely, for every d≥1d \ge1, for which Boolean constraint languages Γ\Gamma of arity at most dd does Max kk-Weight CSP(Γ\Gamma) admit an EPAS? Theorem 1.1 gives a complete classification. It also shows that two languages can each admit an EPAS while their union admits none.

Our results

Fix d≥1d \ge1 and a finite Boolean constraint language Γ\Gamma whose relations have arity at most dd. Throughout, dd denotes this global arity bound, while rr denotes the arity of an individual relation. Only the nonempty relations that exclude the all-zero tuple affect the classification.

A relation R⊆{0,1}rR \subseteq\{0,1\}^{r} is zero-valid if 0∈R\mathbf{0} \in R and zero-free otherwise. Let

Γ+:={R∈Γ:R≠∅, 0∉R}.\Gamma_{+} := \{R \in\Gamma: R \ne\varnothing,\ \mathbf{0} \notin R\}.

Constraints with an empty relation are never satisfied and can be discarded. The all-zero assignment satisfies every constraint whose relation contains 0\mathbf{0}, although selecting variables may later falsify such constraints. The zero-valid lifting argument handles this possible loss. The dichotomy therefore depends only on Γ+\Gamma_{+}.

Fix R∈Γ+R \in\Gamma_{+}, and let r≤dr \le d be its arity. Let eie_i be the tuple whose only 1 is in coordinate ii. Coordinate ii is a unit witness if ei∈Re_i \in R and a control otherwise. The classification is determined by two repair rules, that is, two ways of deleting 1s from a satisfying tuple.

  • RR is Direct if, for every α∈R\alpha\in R and every control coordinate ii with αi=1\alpha_i = 1, setting αi\alpha_i to 0 while leaving all other coordinates unchanged produces another tuple in RR.

  • RR is Rooted if every α∈R\alpha\in R has a unit-witness coordinate uu with αu=1\alpha_u = 1 for which the following operation preserves satisfaction. First keep uu at 1, set every other unit-witness coordinate to 0, and leave all controls unchanged. From this modified tuple, set any subset of its 1-valued controls to 0. Every tuple obtained in this way must belong to RR.

Both rules can also be described by what they exclude. A control coordinate cc is helpful if some β∉R\beta\notin R with βc=0\beta_c = 0 satisfies β+ec∈R\beta+ e_c \in R. A pinned conjunction consists of disjoint sets A,T⊆[r]A,T \subseteq[r], where ∣A∣≥2|A| \ge2 and TT contains only controls: after fixing the coordinates in TT to 1 and those outside A∪TA \cup T to 0, a tuple is accepted exactly when every coordinate in AA is 1. The set TT may be empty. Then RR is Direct exactly when it has no helpful control, and Rooted exactly when it has no pinned conjunction (Lemma 7.3). Thus the hard case occurs when Γ+\Gamma_{+} contains both obstructions, possibly in different relations.

In the hardness part of the following theorem, an instance has multiplicity one if no two of its constraints have the same underlying scope set.

Theorem 1.1 (Fixed-arity dichotomy). Let d≥1d \ge1, and let Γ\Gamma be a fixed finite Boolean constraint language whose relations have arity at most dd. The following statements hold.

  1. If every relation in Γ+\Gamma_{+} is Direct, then Max kk-Weight CSP(Γ\Gamma) admits a deterministic EPAS that, for every ε∈(0,1)\varepsilon\in(0,1), runs in time

2O(d+klog⁡(1+dk/ε))ℓinO(1).2^{O(d+k\log(1+dk/\varepsilon))}\ell_{\mathrm{in}}^{O(1)}.
  1. If every relation in Γ+\Gamma_{+} is Rooted, then Max kk-Weight CSP(Γ\Gamma) admits a deterministic EPAS that, for every ε∈(0,1)\varepsilon\in(0,1), runs in time

2O(klog⁡(1+dk/ε))ℓinO(1).2^{O(k\log(1+dk/\varepsilon))}\ell_{\mathrm{in}}^{O(1)}.
  1. If neither of the preceding conditions on Γ+\Gamma_{+} holds, then Max kk-Weight CSP(Γ\Gamma) admits no EPAS unless FPT = W[1], even on unweighted multiplicity-one instances.

Remark 1.2. The deterministic algorithms in Theorem 1.1 also apply when relation descriptions are supplied as part of the input and the arity bound dd varies. Assume that membership in each relation can be tested in time polynomial in ℓin\ell_{\mathrm{in}}, with a fixed exponent for all inputs. If every relation in Γ+\Gamma_{+} is Direct, or every relation in Γ+\Gamma_{+} is Rooted, the corresponding algorithm satisfies the running-time bound in the theorem. This gives an EPAS parameterized by k+dk+d. The algorithm assumes the corresponding condition on Γ+\Gamma_{+}; the time needed to check that condition is not included.

The two rules capture two ways in which control coordinates are redundant for satisfaction. In a Direct relation, a 1-valued control can be set to 0 while every other coordinate, including every unit witness currently set to 1, remains unchanged. Since RR is zero-free, every satisfying tuple must set some unit witness to 1; otherwise, repeatedly deleting its 1-valued controls would produce 0∈R\mathbf{0} \in R. In a Rooted relation, the definition explicitly chooses a unit witness set to 1. It keeps this witness, removes all competing unit witnesses, and then permits any subset of the remaining 1-valued controls to be deleted. Call a relation R∈Γ+R \in\Gamma_{+} accessible if every tuple in RR has a 1 in some unit-witness coordinate, and inaccessible otherwise. Thus every Direct relation and every Rooted relation is accessible.

Neither rule implies the other, and the EPAS side requires the same rule for all relations in Γ+\Gamma_{+}. The relation

Rdir:={β∈{0,1}3:(β1∨β2)∧(β3→β1∧β2)}={(1,0,0),(0,1,0),(1,1,0),(1,1,1)}R_{\mathrm{dir}} := \{\beta\in\{0,1\}^{3} : (\beta_{1} \lor\beta_{2}) \land(\beta_{3} \to\beta_{1} \land\beta_{2})\} = \{(1,0,0),(0,1,0),(1,1,0),(1,1,1)\}

is Direct but not Rooted. Its unit witnesses are coordinates 1 and 2, and its only control is coordinate 3. It is Direct because (1,1,1)(1,1,1) is its only tuple with β3=1\beta_{3}=1, and setting β3\beta_{3} to 0 gives (1,1,0)∈Rdir(1,1,0) \in R_{\mathrm{dir}}. It is not Rooted because of (1,1,1)(1,1,1): keeping coordinate 1 and setting coordinate 2 to 0 gives (1,0,1)∉Rdir(1,0,1) \notin R_{\mathrm{dir}}, and symmetrically (0,1,1)∉Rdir(0,1,1) \notin R_{\mathrm{dir}}. The relation

Rroot:={β∈{0,1}3:(β1∨β2)∧(β1∧β2→β3)}={(1,0,0),(0,1,0),(1,0,1),(0,1,1),(1,1,1)}\begin{aligned} R_{\mathrm{root}} := \{\beta\in\{0,1\}^{3} : (\beta_{1} \lor\beta_{2}) \land(\beta_{1} \land\beta_{2} \to\beta_{3})\} \\ &= \{(1,0,0),(0,1,0),(1,0,1),(0,1,1),(1,1,1)\} \end{aligned}

is Rooted but not Direct, with the same unit witnesses and control. It is Rooted because every tuple with exactly one of β1,β2\beta_{1},\beta_{2} equal to 1 lies in RrootR_{\mathrm{root}}, and for every β∈Rroot\beta\in R_{\mathrm{root}}, keeping a unit witness uu with βu=1\beta_{u}=1 and setting the other unit witness to 0 produces such a tuple, whatever value the control then takes. It is not Direct because setting the control of (1,1,1)(1,1,1) to 00 gives (1,1,0)∉Rroot(1,1,0) \notin R_{\mathrm{root}}. By Theorem 1.1, Max kk-Weight CSP({Rdir}\{R_{\mathrm{dir}}\}) and Max kk-Weight CSP({Rroot}\{R_{\mathrm{root}}\}) each admit an EPAS, whereas Max kk-Weight CSP({Rdir,Rroot}\{R_{\mathrm{dir}},R_{\mathrm{root}}\}) admits none unless FPT = W[1].

The conditions are decidable by finite inspection. For a relation of arity rr, testing Direct takes O(r2r)O(r^{2r}) membership queries and testing Rooted takes O(r4)O(r^{4}). Thus O(∣Γ∣d4)O(|\Gamma|d^{4}) queries determine the case of the theorem; § 4 gives the tests.

The arity-two boundary. For languages whose relations have arity at most two, Theorem 1.1 depends on a single relation, RAND:={(1,1)}R_{\mathrm{AND}} := \{(1,1)\}. It has no unit witness, so it is inaccessible and hence neither Direct nor Rooted. Every other nonempty zero-free relation of arity at most two is both Direct and Rooted (Proposition 8.1).

References

  1. [1]Ashwinkumar Badanidiyuru, Robert Kleinberg, and Hooyeon Lee. Approximating low-dimensional coverage problems. In Tamal K. Dey and Sue Whitesides, editors, Proceedings of the 28th ACM Symposium on Computational Geometry, Chapel Hill, NC, USA, June 17-20, 2012, pages 161–170. ACM, 2012. doi:10.1145/2261250.2261274.DOI
  2. [2]Edouard Bonnet, Bruno Escoffier, Vangelis Th. Paschos, and Emeric Tourniiaire. Multiparameter analysis for local graph partitioning problems: Using greediness for parameterization. Algorithmica, 71(3):566–580, 2015. URL: https://doi.org/10.1007/s00453-014-9920-6, doi:10.1007/S00453-014-9920-6.
  3. [3]Andrei A. Bulatov and Dániel Marx. Constraint satisfaction parameterized by solution size. In Automata, Languages and Programming - 38th International Colloquium, ICALP 2011, pages 424–436. Springer, 2011. doi:10.1007/978-3-642-22006-7_36.DOI
  4. [4]Philip Cervenjak, Junhoa Gan, Seeun William Umboh, and Anthony Wirth. Maximum unique coverage on streams: Improved FPT approximation scheme and tighter space lower bound. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2024, volume 317 of LIPIcs, pages 25:1–25:23. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024. doi:10.4230/LIPIcs.APPROX/RANDOM.2024.25.DOI
  5. [5]Vincent Cohen-Addad, Anupam Gupta, Amit Kumar, Eu Jinwoong Lee, and Jason Li. Tight FPT approximations for k-median and k-means. In Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi, editors, 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece, volume 132 of LIPIcs, pages 42:1–42:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. doi:10.4230/LIPIcs.ICALP.2019.42.
  6. [6]Nadia Creignou. A dichotomy theorem for maximum generalized satisfiability problems. Journal of Computer and System Sciences, 51(3):511–522, 1995. doi:10.1006/jcss.1995.1087.DOI
  7. [7]Nadia Creignou, Henning Schnoor, and Ilka Schnoor. Non-uniform Boolean constraint satisfaction problems with cardinality constraint. In Computer Science Logic, 22nd International Workshop, CSL 2008, volume 5213 of Lecture Notes in Computer Science, pages 109–123. Springer, 2008. doi:10.1007/978-3-540-87531-4_10.DOI
  8. [8]Erik D. Demaine, Uriel Feige, MohammadTaghi Hajiaghayi, and Mohammad R. Salavatipour. Combination can be hard: Approximability of the unique coverage problem. SIAM J. Comput., 38(4):1464–1483, 2008. doi:10.1137/060656048.DOI
  9. [9]Reinhard Diestel. Graph Theory, volume 173 of Graduate Texts in Mathematics. Springer, New York, second edition, 2000.
  10. [10]Rodney G. Downey and Michael R. Fellows. Fixed-parameter tractability and completeness II: on completeness for W[1]. Theor. Comput. Sci., 141(1&2):109–131, 1995. doi: 10.1016/0304-3975(94)00097-3.DOI
  11. [11]Édouard Bonnet, László Egri, Bingkai Lin, and Dániel Marx. Fixed-parameter approximability of Boolean MinCSPs. CoRR, abs/1601.04935, 2018. URL: https://arxiv.org/abs/1601.04935v2, doi:10.48550/arXiv.1601.04935.
  12. [12]Uriel Feige. A threshold of ln n for approximating set cover. J. ACM, 45(4):634–652, 1998. doi:10.1145/285055.285059.DOI
  13. [13]Vitaly Feldman, Parikshit Gopalan, Subhash Khot, and Ashok Kumar Ponnuswami. On agnostic learning of parities, monomials, and halfspaces. SIAM J. Comput., 39(2):606–645, 2009. doi:10.1137/070684914.DOI
  14. [14]Fedor V. Fomin, Petr A. Golovach, Tanmay Inamdar, and Tomohiro Koana. FPT approximation and subexponential algorithms for covering few or many edges. Information Processing Letters, 185:106471, 2024. doi:10.1016/j.ipl.2024.106471.DOI
  15. [15]Tanmay Inamdar, Pallavi Jain, Daniel Lokshtanov, Abhishek Sahu, Saket Saurabh, and Anannya Upasana. Satisfiability to coverage in presence of fairness, matroid, and global constraints. In Karl Bringmann, Martin Grohe, Gabriele Puppis, and Ola Svensson, editors, 51st International Colloquium on Automata, Languages, and Programming, ICALP 2024, July 8-12, 2024, Tallinn, Estonia, volume 297 of LIPIcs, pages 88:1–88:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. URL: https://doi.org/10.4230/LIPIcs.ICALP.2024.88, doi:10.4230/LIPIcs.ICALP.2024.88.
  16. [16]Pallavi Jain, Lawqueen Kanesh, Fahad Panolan, Souvik Saha, Abhishek Sahu, Saket Saurabh, and Anannya Upasana. Parameterized Approximation Scheme for Biclique-free Max k-Weight SAT and Max Coverage. In Nikhil Bansal and Viswanath Nagarajan, editors, Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, Florence, Italy, January 22-25, 2023, pages 3713–3733. SIAM, 2023. URL: https://doi.org/10.1137/1.9781611977554.ch143, doi:10.1137/1.9781611977554.CH143.
  17. [17]Sanjeev Khanna, Madhu Sudan, Luca Trevisan, and David P. Williamson. The approximability of constraint satisfaction problems. SIAM J. Comput., 30(6):1863–1920, 2001. doi:10.1137/S0097539799349948.DOI
  18. [18]Madhumita Kundu, Souvik Saha, Saket Saurabh, and Anannya Upasana. Fixed budget vs. covering target: The partial set cover boundary for bounded VC-dimension, 2026. URL: https://arxiv.org/abs/2608.03801, arXiv:2608.03801.
  19. [19]Pasin Manurangsi. A note on Max k-Vertex Cover: Faster FPT-AS, smaller approximate kernel and improved approximation. In Jeremy T. Fineman and Michael Mitzenmacher, editors, 2nd Symposium on Simplicity in Algorithms, SOSA 2019, January 8-9, 2019, San Diego, CA, USA, volume 69 of OASIcs, pages 15:1–15:21. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. URL: https://doi.org/10.4230/OASIcs.SOSA.2019.15, doi:10.4230/OASIcs.SOSA.2019.15.
  20. [20]Pasin Manurangsi. Tight running time lower bounds for strong inapproximability of maximum k-coverage, unique set cover and related problems (via t-wise agreement testing theorem). In Shuchi Chawla, editor, Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, pages 62–81. SIAM, 2020. doi:10.1137/1.9781611975994.5.DOI
  21. [21]Pasin Manurangsi. Improved FPT approximation scheme and approximate kernel for biclique-free max k-weight SAT: greedy strikes back. Theor. Comput. Sci., 1028:115033, 2025. doi:10.1016/j.tcs.2024.115033.DOI
  22. [22]Dániel Marx. Parameterized complexity of constraint satisfaction problems. Comput. Complex., 14(2):153–183, 2005. doi:10.1007/s00037-005-0195-9.DOI
  23. [23]Dániel Marx. Parameterized complexity and approximation algorithms. Comput. J., 51(1):60–78, 2008. URL: https://doi.org/10.1093/comjnl/bxm048, doi:10.1093/COMJNL/BXM048.
  24. [24]David W. Matula and Leland L. Beck. Smallest-last ordering and clustering and graph coloring algorithms. Journal of the ACM, 30(3):417–427, 1983. doi:10.1145/2402.322385.DOI
  25. [25]Neeldhara Misra, Venkatesh Raman, Saket Saurabh, and Somnath Sikdar. The budgeted unique coverage problem and color-coding. In Computer Science – Theory and Applications, Fourth International Computer Science Symposium in Russia, CSR 2009, volume 5675 of Lecture Notes in Computer Science, pages 310–321. Springer, 2009. doi:10.1007/978-3-642-03351-3_29.DOI
  26. [26]Moni Naor, Leonard J. Schulman, and Aravind Srinivasan. Splitters and near-optimal derandomization. In 36th Annual Symposium on Foundations of Computer Science, Milwaukee, Wisconsin, USA, 23–25 October 1995, pages 182–191. IEEE Computer Society, 1995. doi:10.1109/SFCS.1995.492475.
  27. [27]George L. Nemhauser, Laurence A. Wolsey, and Marshall L. Fisher. An analysis of approximations for maximizing submodular set functions - I. Math. Program., 14(1):265–294, 1978. doi:10.1007/BF01588971.DOI
  28. [28]Thomas J. Schaefer. The complexity of satisfiability problems. In Proceedings of the Tenth Annual ACM Symposium on Theory of Computing, STOC ’78, pages 216–226, New York, NY, USA, 1978. Association for Computing Machinery. doi:10.1145/800133.804350.DOI
  29. [29]François Sellier. Parameterized matroid-constrained maximum coverage. In Inge Li Gørtz, Martin Farach-Colton, Simon J. Puglisi, and Grzegorz Herman, editors, 31st Annual European Symposium on Algorithms, ESA 2023, September 4-6, 2023, Amsterdam, The Netherlands, volume 274 of LIPIcs, pages 94:1–94:16. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2023. URL: https://doi.org/10.4230/LIPIcs.ESA.2023.94, doi:10.4230/LIPIcs.ESA.2023.94.
  30. [30]Piotr Krzysztof Skowron and Piotr Faliszewski. Fully proportional representation with approval ballots: Approximating the maxcover problem with bounded frequencies in FPT time. In Blai Bonet and Sven Koenig, editors, Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, January 25-30, 2015, Austin, Texas, USA, pages 2124–2130. AAAI Press, 2015. URL: https://doi.org/10.1609/aaai.v29i1.9432, doi:10.1609/AAAI.V29I1.9432.
  31. [31]Maxim Sviridenko. Best possible approximation algorithm for MAX SAT with cardinality constraint. Algorithmica, 30(3):398–405, 2001. doi:10.1007/s00453-001-0019-5.DOI

Paper details

vlnc:W_26xbkuz5
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

ChatGPT

View statement
Looking for related papers…
Contents