On the approximability of trade-offs and optimal access of Web sources

By Christos H. Papadimitriou, Mihalis Yannakakis. Proceedings 41st Annual Symposium on Foundations of Computer Science, 2000

522 citations recorded by the source corpus.

Subfields: Computer Networks and Communications, Electrical and Electronic Engineering, Industrial and Manufacturing Engineering

View Paper: https://www.semanticscholar.org/paper/87e3b80fa6a8902a1f00b336c1a2134991d2f44e

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

In Electrical and Electronic Engineering

In Industrial and Manufacturing Engineering

Citations in the corpus

Mean-Variance Optimization in Markov Decision Processes (2011, unknown): “…say thatv̂(·) is an (ǫ, ν)-aproximation ofv∗(·) if, for every λ, v∗(λ− ν)− ǫ ≤ v̂(λ) ≤ v∗(λ+ ν) + ǫ. (5) This is an approximation of the same kind as those consideredin Papadimitriou and Yannakakis (2000): it returns a valuêv such that(λ, v̂) is an element of the “(ǫ + ν)-approximate Pareto…”
Combining Convergence and Diversity in Evolutionary Multiobjective Optimization (2002, background): “Recently, Papadimitriou and Yannakakis (2000) and Erlebach et al. (2001) pointed out that under certain assumptions, there is always an approximate Pareto set whose size is polynomial in the length of the encoded input.”
When optimizing nonlinear objectives is no harder than linear objectives (2018, background): “While computing the Pareto set (even membership) is NP-hard (Ravi et al., 1993), for some problems it can be succinctly approximated (Warburton, 1987; Papadimitriou and Yannakakis, 2000; Diakonikolas, 2011).”
Route Planning in Transportation Networks (2015, background): “In particular, (1 + ε)-Pareto sets have provable polynomial size [212] and can be computed efficiently [182,246,253].”
Unleashing Linear Optimizers for Group-Fair Learning and Optimization (2018, background): “While computing the Pareto set (even membership) is NP-hard (Ravi et al., 1993), for some problems it can be succinctly approximated (Warburton, 1987; Papadimitriou and Yannakakis, 2000; Diakonikolas, 2011).”
Online team formation in social networks (2012, background): “Another approach to bi-criteria optimization problems is to compute the set of Pareto optimal solutions [18], which are those solutions that are not outperformed by other solutions on both allocation and coordination costs.”
Robust Submodular Observation Selection (2008, background): “In fact, all Pareto-optimal solutions can be found in this way (Papadimitriou and Yannakakis, 2000). be expected to provide near-optimal placements.”
A survey of recent developments in multiobjective optimization (2007, methodology): “Next, we introduce results regarding the size of the -approximate Pareto optimal set by Papadimitriou and Yannakakis (2000). Before presenting the next theorems, we need some assumptions.”