New Lower Bounds and Upper Bounds for Listing Avoidable Vertices.

Mingyang Deng Virginia Vassilevska Williams Ziqian Zhong

Published in: MFCS (2022)

Keyphrases

upper bound
lower bound
branch and bound algorithm
branch and bound
upper and lower bounds
optimal solution
worst case

lower and upper bounds
tight bounds
objective function
vc dimension
np hard
sample size

sample complexity
generalization error
quadratic assignment problem
exact solution
weighted graph
linear programming relaxation

linear program
lower bounding
constant factor
special case
optimal cost
tight upper and lower bounds