Pages that link to "Item:Q5441360"
From MaRDI portal
The following pages link to Some optimal inapproximability results (Q5441360):
Displaying 50 items.
- Improved approximation for orienting mixed graphs (Q261342) (← links)
- Chromatic kernel and its applications (Q266072) (← links)
- Sharp spectral bounds of several graph parameters using eigenvector norms (Q286136) (← links)
- Complexity of approximating CSP with balance/hard constraints (Q315529) (← links)
- A nonmonotone GRASP (Q340011) (← links)
- An FPTAS for optimizing a class of low-rank functions over a polytope (Q378129) (← links)
- Reoptimization of constraint satisfaction problems with approximation resistant predicates (Q380664) (← links)
- Approximation algorithms for orienting mixed graphs (Q390889) (← links)
- On approximating string selection problems with outliers (Q391209) (← links)
- Approximation with a fixed number of solutions of some multiobjective maximization problems (Q396664) (← links)
- More on average case vs approximation complexity (Q430823) (← links)
- Towards strong nonapproximability results in the Lovász-Schrijver hierarchy (Q430828) (← links)
- Toward a model for backtracking and dynamic programming (Q430838) (← links)
- Performance tradeoffs in structured peer to peer streaming (Q433417) (← links)
- On the inapproximability of maximum intersection problems (Q456103) (← links)
- A survey on the structure of approximation classes (Q458503) (← links)
- Bisections of graphs (Q461728) (← links)
- On the approximation ratio threshold for the reoptimization of the maximum number of satisfied equations in linear systems over a finite field (Q466374) (← links)
- New inapproximability bounds for TSP (Q494069) (← links)
- Quell (Q500997) (← links)
- Improved approximation algorithms for projection games (Q513283) (← links)
- Short sequences of improvement moves lead to approximate equilibria in constraint satisfaction games (Q524372) (← links)
- The maximum labeled path problem (Q527429) (← links)
- Near optimal bounds in Freiman's theorem (Q541154) (← links)
- A fault-containing self-stabilizing \((3-\frac 2{\varDelta+1})\)-approximation algorithm for vertex cover in anonymous networks (Q555319) (← links)
- Energy efficient monitoring in sensor networks (Q627527) (← links)
- On the complexity of reconfiguration problems (Q631762) (← links)
- Approximability of sparse integer programs (Q634673) (← links)
- Solving MAX-\(r\)-SAT above a tight lower bound (Q644808) (← links)
- Local search with edge weighting and configuration checking heuristics for minimum vertex cover (Q646517) (← links)
- Techniques from combinatorial approximation algorithms yield efficient algorithms for random 2\(k\)-SAT (Q706614) (← links)
- Recognizing frozen variables in constraint satisfaction problems (Q706617) (← links)
- Hypercontractive inequality for pseudo-Boolean functions of bounded Fourier width (Q713329) (← links)
- Strong and weak edges of a graph and linkages with the vertex cover problem (Q765356) (← links)
- Hardness and approximation of traffic grooming (Q837166) (← links)
- Hard constraint satisfaction problems have hard gaps at location 1 (Q837178) (← links)
- A note on unique games (Q845686) (← links)
- Minimum 2SAT-DELETION: Inapproximability results and relations to minimum vertex cover (Q867859) (← links)
- An efficient fixed-parameter algorithm for 3-hitting set (Q876698) (← links)
- Differential approximation of MIN SAT, MAX SAT and related problems (Q877035) (← links)
- Maximum \(H\)-colourable subdigraphs and constraint optimization with arbitrary weights (Q881590) (← links)
- PCPs via the low-degree long code and hardness for constrained hypergraph coloring (Q891178) (← links)
- On the configuration LP for maximum budgeted allocation (Q896296) (← links)
- Modelling the dynamics of stochastic local search on \(k\)-SAT (Q930153) (← links)
- On the complexity of optimization over the standard simplex (Q932197) (← links)
- The complexity of optimizing over a simplex, hypercube or sphere: a short survey (Q940826) (← links)
- Sums of squares based approximation algorithms for MAX-SAT (Q944728) (← links)
- Complete partitions of graphs (Q949754) (← links)
- The Steiner tree problem on graphs: inapproximability results (Q952442) (← links)
- Combinatorial network abstraction by trees and distances (Q954979) (← links)
