Complexity of approximating bounded variants of optimization problems
From MaRDI portal
Publication:2368970
DOI10.1016/j.tcs.2005.11.029zbMath1105.90110OpenAlexW1980842804MaRDI QIDQ2368970
Janka Chlebíková, Miroslav Chlebík
Publication date: 28 April 2006
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://researchportal.port.ac.uk/portal/en/publications/complexity-of-approximating-bounded-variants-of-optimization-problems(033531e7-202b-476c-8568-b9c586a2a819).html
Related Items (46)
Bounded clique cover of some sparse graphs ⋮ Approximation hardness of edge dominating set problems ⋮ Computing envy-freeable allocations with limited subsidies ⋮ Minimum 2SAT-DELETION: Inapproximability results and relations to minimum vertex cover ⋮ Relationship between Approximability and Request Structures in the Minimum Certificate Dispersal Problem ⋮ Approximation algorithms for clustering with dynamic points ⋮ Global and fixed-terminal cuts in digraphs ⋮ APX-hardness of maximizing Nash social welfare with indivisible items ⋮ Cascading Critical Nodes Detection with Load Redistribution in Complex Systems ⋮ Caching with Time Windows and Delays ⋮ Why did the shape of your network change? (On detecting network anomalies via non-local curvatures) ⋮ Identifying path covers in graphs ⋮ There is no APTAS for 2-dimensional vector bin packing: revisited ⋮ Catastrophic cascading failures in power networks ⋮ Approximability of the Distance Independent Set Problem on Regular Graphs and Planar Graphs ⋮ Complexity of majority monopoly and signed domination problems ⋮ Computing maximum matchings in temporal graphs ⋮ A 6/5-approximation algorithm for the maximum 3-cover problem ⋮ Maximal strip recovery problem with gaps: hardness and approximation algorithms ⋮ Greed is good for deterministic scale-free networks ⋮ Secure connected domination and secure total domination in unit disk graphs and rectangle graphs ⋮ Approximation complexity of metric dimension problem ⋮ Approximation Algorithm for the Distance-3 Independent Set Problem on Cubic Graphs ⋮ On a connection between small set expansions and modularity clustering ⋮ Triangle strings: structures for augmentation of vertex-disjoint triangle sets ⋮ Second-price ad auctions with binary bids and markets with good competition ⋮ On Variants of the Spanning Star Forest Problem ⋮ Improved and simplified inapproximability for \(k\)-means ⋮ Approximation hardness of dominating set problems in bounded degree graphs ⋮ Multicommodity flow in trees: packing via covering and iterated relaxation ⋮ Inapproximability of maximal strip recovery ⋮ Complexity and approximation of the constrained forest problem ⋮ Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs ⋮ Approximability and inapproximability of the minimum certificate dispersal problem ⋮ Fingerprint clustering with bounded number of missing values ⋮ Algorithmic aspects of upper edge domination ⋮ Approximation of the \(k\)-batch consolidation problem ⋮ Unnamed Item ⋮ Weighted Upper Edge Cover: Complexity and Approximability ⋮ On approximating four covering and packing problems ⋮ Approximability of minimum AND-circuits ⋮ Vertex and edge covers with clustering properties: Complexity and algorithms ⋮ Hardness of approximation for orthogonal rectangle packing and covering problems ⋮ Approximation of a batch consolidation problem ⋮ Proportionally dense subgraph of maximum size: complexity and approximation ⋮ Degree-constrained graph orientation: maximum satisfaction and minimum violation
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Maximum bounded 3-dimensional matching is MAX SNP-complete
- Optimization, approximation, and complexity classes
- On approximation properties of the independent set problem for low degree graphs
- Approximating the independence number via the \(\vartheta\)-function
- Improved non-approximability results for minimum vertex cover with density constraints
- On the approximability of the traveling salesman problem (extended abstract)
- The importance of being biased
- Approximate graph coloring by semidefinite programming
- Non-approximability results for optimization problems on bounded degree instances
- Structural Information and Communication Complexity
- Some optimal inapproximability results
- Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
This page was built for publication: Complexity of approximating bounded variants of optimization problems
