Approximately dominating representatives

DOI10.1016/j.tcs.2006.11.003zbMath1108.68042OpenAlexW2129143099MaRDI QIDQ870264

Vladlen Koltun, Christos H. Papadimitriou

Publication date: 12 March 2007

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2006.11.003

zbMATH Keywords

constant factor approximation algorithm

Mathematics Subject Classification ID

Database theory (68P15) Network design and communication in computer systems (68M10) Approximation algorithms (68W25)

Related Items (19)

(Approximate) uncertain skylines ⋮ Approximation Methods for Multiobjective Optimization Problems: A Survey ⋮ K-dominance in multidimensional data: theory and applications ⋮ Computing representations using hypervolume scalarizations ⋮ Approximating biobjective minimization problems using general ordering cones ⋮ Bounds on the domination number of a digraph ⋮ Prioritized repairing and consistent query answering in relational databases ⋮ Unnamed Item ⋮ Covers and approximations in multiobjective optimization ⋮ Discrete representation of the non-dominated set for multi-objective optimization problems using kernels ⋮ Stochastic convergence of random search methods to fixed size Pareto front approximations ⋮ Approximate Pareto sets of minimal size for multi-objective optimization problems ⋮ One-exact approximate Pareto sets ⋮ On Geometric Set Cover for Orthants ⋮ The domination number of round digraphs ⋮ The most-likely skyline problem for stochastic points ⋮ Total domination in digraphs ⋮ A note on lower bounds for the total domination number of digraphs ⋮ K-Dominance in Multidimensional Data: Theory and Applications

Cites Work

• Improved approximation algorithms for geometric set cover
• Combining fuzzy information from multiple systems
• Voronoi diagrams in higher dimensions under certain polyhedral distance functions
• Optimal aggregation algorithms for middleware.
• A formula for incorporating weights into scoring rules
• Almost optimal set covers in finite VC-dimension
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• On the Average Number of Maxima in a Set of Vectors and Applications
• On the hardness of approximating minimization problems
• Automata, Languages and Programming

This page was built for publication: Approximately dominating representatives