Some optimal inapproximability results
From MaRDI portal
Recommendations
Cited in
(only showing first 100 items - show all)- Reduced error pruning of branching programs cannot be approximated to within a logarithmic factor
- Single machine precedence constrained scheduling is a Vertex cover problem
- Minimal achievable approximation ratio for MAX-MQ in finite fields
- Non-approximability of weighted multiple sequence alignment.
- Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT.
- Solving integer programs over monotone inequalities in three variables: A framework for half integrality and good approximations
- On the approximability of the maximum interval constrained coloring problem
- Towards a characterization of constant-factor approximable finite-valued CSPs
- Time-approximation trade-offs for inapproximable problems
- Approximation for vertex cover in -conflict graphs
- Welfare maximization with friends-of-friends network externalities
- Minimizing worst-case and average-case makespan over scenarios
- On the robust hardness of Gröbner basis computation
- Affine reductions for LPs and SDPs
- Approximate inference in Bayesian networks: parameterized complexity results
- \(K\)-adaptability in stochastic combinatorial optimization under objective uncertainty
- On extensions of the deterministic online model for bipartite matching and max-sat
- On the lower bounds of random Max 3 and 4-SAT
- On approximating the b-chromatic number
- The approximability of non-Boolean satisfiability problems and restricted integer programming
- Complexity and approximation of finding the longest vector sum
- A priori TSP in the scenario model
- The complexity of solving equations over finite groups
- Towards optimal lower bounds for clique and chromatic number.
- Improved approximations for max set splitting and max NAE SAT
- Approximation algorithms for aligning points
- The inapproximability of lattice and coding problems with preprocessing
- Inapproximability results for equations over finite groups
- Approximation algorithm for a class of global optimization problems
- A tighter upper bound for random MAX \(2\)-SAT
- Intractability of min- and max-cut in streaming graphs
- Greedy -approximation algorithm for covering with arbitrary constraints and submodular cost
- Limited lookahead in imperfect-information games
- The commuting local Hamiltonian problem on locally expanding graphs is approximable in \(\mathsf{NP}\)
- An SDP randomized approximation algorithm for max hypergraph cut with limited unbalance
- Producing genomic sequences after genome scaffolding with ambiguous paths: complexity, approximation and lower bounds
- New results on the complexity of deletion propagation
- Approximation algorithms for balancing signed graphs
- Probabilistic characterization of random Max r-Sat
- On non-optimally expanding sets in Grassmann graphs
- A simple rounding scheme for multistage optimization
- Dynamical noise sensitivity for the voter model
- Using the method of conditional expectations to supply an improved starting point for CCLS
- Optimization in business strategy as a part of sustainable economic growth using clique covering of fuzzy graphs
- Classical symmetries and the quantum approximate optimization algorithm
- New limits of treewidth-based tractability in optimization
- On regularity of Max-CSPs and Min-CSPs
- Fuzzy covering problem of fuzzy graphs and its application to investigate the Indian economy in new normal
- Noisy tensor completion via the sum-of-squares hierarchy
- A novel algorithm for Max Sat calling MOCE to order
- On computational capabilities of Ising machines based on nonlinear oscillators
- Weighted amplifiers and inapproximability results for travelling salesman problem
- Covering problem on fuzzy graphs and its application in disaster management system
- On the (In)security of Kilian-based SNARGs
- Accelerating deep learning with memcomputing
- A fast algorithm for maximizing a non-monotone DR-submodular integer lattice function
- Approximation algorithms for geometric conflict free covering problems
- PCPs and the hardness of generating synthetic data
- Approximability of the dispersed \(\vec{p}\)-neighbor \(k\)-supplier problem
- Minimization problems for parity OBDDs
- Max-bisections of \(H\)-free graphs
- Complexity results on planar multifacility location problems with forbidden regions
- Optimizing positional scoring rules for rank aggregation
- Maximizing submodular or monotone approximately submodular functions by multi-objective evolutionary algorithms
- Hypergraph cuts above the average
- Eigenvector-based identification of bipartite subgraphs
- Hardness of approximation for knapsack problems
- Oblivious algorithms for the maximum directed cut problem
- Complexity of approximating bounded variants of optimization problems
- Approximation hardness of edge dominating set problems
- Short PCPPs verifiable in polylogarithmic time with \(O(1)\) queries
- Adding cardinality constraints to integer programs with applications to maximum satisfiability
- Note on maximal split-stable subgraphs
- Supermodular functions and the complexity of MAX CSP
- Parameterized complexity of satisfying almost all linear equations over \(\mathbb F_2\)
- Improved approximation algorithms for the spanning star forest problem
- An algebraic proof of the real number PCP theorem
- Complexity and approximability of parameterized MAX-CSPs
- Large cuts with local algorithms on triangle-free graphs
- Inapproximability ratios for crossing number
- Complexity and approximability of extended spanning star forest problems in general and complete graphs
- Vertex cover in conflict graphs
- A survey of approximability and inapproximability results for social welfare optimization in multiagent resource allocation
- New exact algorithms for the 2-constraint satisfaction problem
- Quantitative relation between noise sensitivity and influences
- Non-interactive correlation distillation, inhomogeneous Markov chains, and the reverse Bonami-Beckner inequality
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
- Hardness of approximating the shortest vector problem in high \(\ell_{p}\) norms
- Hedging uncertainty: approximation algorithms for stochastic optimization problems
- TSP with bounded metrics
- A semidefinite programming based polyhedral cut and price approach for the maxcut problem
- Clustering with qualitative information
- Locally consistent constraint satisfaction problems
- Improved approximation for orienting mixed graphs
- From the quantum approximate optimization algorithm to a quantum alternating operator ansatz
- Inapproximability of maximum biclique problems, minimum k-cut and densest at-least- k-subgraph from the small set expansion hypothesis
- Satisfiability with index dependency
- Satisfying more than half of a system of linear equations over GF(2): a multivariate approach
- Column subset selection problem is UG-hard
- Chromatic kernel and its applications
This page was built for publication: Some optimal inapproximability results
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5441360)
