Pages that link to "Item:Q5441360"
From MaRDI portal
The following pages link to Some optimal inapproximability results (Q5441360):
Displaying 50 items.
- Approximation hardness of dominating set problems in bounded degree graphs (Q958303) (← links)
- Approximating maximum satisfiable subsystems of linear equations of bounded width (Q963367) (← links)
- Average-case analysis for the MAX-2SAT problem (Q964385) (← links)
- Inapproximability results for equations over infinite groups (Q974745) (← links)
- Reduced error pruning of branching programs cannot be approximated to within a logarithmic factor (Q1014397) (← links)
- Single machine precedence constrained scheduling is a Vertex cover problem (Q1016523) (← links)
- Minimal achievable approximation ratio for MAX-MQ in finite fields (Q1019747) (← links)
- Non-approximability of weighted multiple sequence alignment. (Q1401267) (← links)
- Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT. (Q1408377) (← links)
- Solving integer programs over monotone inequalities in three variables: A framework for half integrality and good approximations (Q1598763) (← links)
- On the approximability of the maximum interval constrained coloring problem (Q1662109) (← links)
- Towards a characterization of constant-factor approximable finite-valued CSPs (Q1671996) (← links)
- Time-approximation trade-offs for inapproximable problems (Q1678175) (← links)
- Approximation for vertex cover in \(\beta\)-conflict graphs (Q1679502) (← links)
- Welfare maximization with friends-of-friends network externalities (Q1693985) (← links)
- Minimizing worst-case and average-case makespan over scenarios (Q1702655) (← links)
- On the robust hardness of Gröbner basis computation (Q1713027) (← links)
- Affine reductions for LPs and SDPs (Q1717229) (← links)
- Approximate inference in Bayesian networks: parameterized complexity results (Q1726381) (← links)
- \(K\)-adaptability in stochastic combinatorial optimization under objective uncertainty (Q1740549) (← links)
- On extensions of the deterministic online model for bipartite matching and max-sat (Q1740687) (← links)
- On the lower bounds of random Max 3 and 4-SAT (Q1752631) (← links)
- On approximating the b-chromatic number (Q1765381) (← links)
- The approximability of non-Boolean satisfiability problems and restricted integer programming (Q1770383) (← links)
- Complexity and approximation of finding the longest vector sum (Q1785063) (← links)
- A priori TSP in the scenario model (Q1801079) (← links)
- The complexity of solving equations over finite groups (Q1854566) (← links)
- Towards optimal lower bounds for clique and chromatic number. (Q1874411) (← links)
- Improved approximations for max set splitting and max NAE SAT (Q1878408) (← links)
- Approximation algorithms for aligning points (Q1879366) (← links)
- The inapproximability of lattice and coding problems with preprocessing (Q1881262) (← links)
- Inapproximability results for equations over finite groups (Q1884871) (← links)
- Approximation algorithm for a class of global optimization problems (Q1937958) (← links)
- A tighter upper bound for random MAX \(2\)-SAT (Q1944049) (← links)
- Intractability of min- and max-cut in streaming graphs (Q1944060) (← links)
- Approximating multilinear monomial coefficients and maximum multilinear monomials in multivariate polynomials (Q1944393) (← links)
- Greedy \(\varDelta \)-approximation algorithm for covering with arbitrary constraints and submodular cost (Q1949749) (← links)
- Limited lookahead in imperfect-information games (Q1989388) (← links)
- On the structure of Boolean functions with small spectral norm (Q2012184) (← links)
- The commuting local Hamiltonian problem on locally expanding graphs is approximable in \(\mathsf{NP}\) (Q2018136) (← links)
- An SDP randomized approximation algorithm for max hypergraph cut with limited unbalance (Q2018887) (← links)
- Producing genomic sequences after genome scaffolding with ambiguous paths: complexity, approximation and lower bounds (Q2037107) (← links)
- New results on the complexity of deletion propagation (Q2039681) (← links)
- Approximation algorithms for balancing signed graphs (Q2039689) (← links)
- Probabilistic characterization of random Max \(r\)-Sat (Q2042075) (← links)
- On non-optimally expanding sets in Grassmann graphs (Q2048867) (← links)
- A simple rounding scheme for multistage optimization (Q2077374) (← links)
- Dynamical noise sensitivity for the voter model (Q2081110) (← links)
- Using the method of conditional expectations to supply an improved starting point for CCLS (Q2091119) (← links)
- Optimization in business strategy as a part of sustainable economic growth using clique covering of fuzzy graphs (Q2098337) (← links)
