Approximately dominating representatives

DOI10.1016/J.TCS.2006.11.003MaRDI QIDQ870264zbMATH OpenOpenAlexFDO

Authors Vladlen Koltun, Christos 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

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

Recommendations

• Database Theory - ICDT 2005
• Relatively dominated representations
• Approximation based on representatives
• Representation in majority tournaments
• scientific article; zbMATH DE number 3920153
• scientific article; zbMATH DE number 1124597
• Rank-1 representers
• Weighted representative democracy
• scientific article; zbMATH DE number 3899273
• A generalization on neighborhood representatives

Cites work

• 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
• Automata, Languages and Programming
• Combining fuzzy information from multiple systems
• Improved approximation algorithms for geometric set cover
• On the Average Number of Maxima in a Set of Vectors and Applications
• On the hardness of approximating minimization problems
• Optimal aggregation algorithms for middleware.
• Voronoi diagrams in higher dimensions under certain polyhedral distance functions

Cited in

(24)

• Approximate Pareto sets of minimal size for multi-objective optimization problems
• K-Dominance in Multidimensional Data: Theory and Applications
• Database Theory - ICDT 2005
• Discrete representation of the non-dominated set for multi-objective optimization problems using kernels
• A note on lower bounds for the total domination number of digraphs
• Approximation Methods for Multiobjective Optimization Problems: A Survey
• scientific article; zbMATH DE number 7626788 (Why is no real title available?)
• One-exact approximate Pareto sets
• Stochastic convergence of random search methods to fixed size Pareto front approximations
• Approximating multiobjective optimization problems: how exact can you be?
• Using scalarizations for the approximation of multiobjective optimization problems: towards a general theory
• Prioritized repairing and consistent query answering in relational databases
• The domination number of round digraphs
• Bounds on the domination number of a digraph
• K-dominance in multidimensional data: theory and applications
• On Geometric Set Cover for Orthants
• Representation in majority tournaments
• Total domination in digraphs
• Computing representations using hypervolume scalarizations
• (Approximate) uncertain skylines
• Towards strong regret minimization sets: balancing freshness and diversity in data selection
• The most-likely skyline problem for stochastic points
• Covers and approximations in multiobjective optimization
• Approximating biobjective minimization problems using general ordering cones

This page was built for publication: Approximately dominating representatives

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q870264)