yusuke1997/dblp-id-title huggingface dataset:
Online Strip Packing with Polynomial Migration
Upper Bounds on the 2-Colorability Threshold of Random d-Regular k-Uniform Hypergraphs for k ≥ 3
Lifting to Randomized Parity Decision Trees
Low Rank Approximation in the Presence of Outliers
Lower Bounds for Approximating Graph Parameters via Communication Complexity
Singularity of Random Integer Matrices with Large Entries
New Constructions of Pseudorandom Codes
Improved Hardness Results for Profit Maximization Pricing Problems with Unlimited Supply
On the Structure of Quintic Polynomials
Nearly Optimal Bounds for Sample-Based Testing and Learning of k-Monotone Functions
Global and Local Information in Clustering Labeled Block Models
Query Complexity of Global Minimum Cut
Explicit and Near-Optimal Construction of t-Rankwise Independent Permutations
Erratum: Resource Minimization Job Scheduling
Online Multidimensional Load Balancing
Shared Randomness in Locally Checkable Problems: The Role of Computational Assumptions
Parity is Positively Useless
Embedding Hard Learning Problems Into Gaussian Space
Tight Chernoff-Like Bounds Under Limited Independence
The Cover Number of a Matrix and its Algorithmic Applications
Uniform Derandomization from Pathetic Lower Bounds
Smooth Analysis of the Condition Number and the Least Singular Value
Samplers and Extractors for Unbounded Functions
On the Complexity of Triangle Counting Using Emptiness Queries
Approximation Schemes for Broadcasting in Heterogenous Networks
What's the Frequency, Kenneth?: Sublinear Fourier Sampling Off the Grid
Giant Components in Random Temporal Graphs
On Approximating the Number of Relevant Variables in a Function
The Expected Number of Maximal Points of the Convolution of Two 2-D Distributions
Max-Min Greedy Matching
Traveling in Randomly Embedded Random Graphs
An O(1)-Approximation Algorithm for Dynamic Weighted Vertex Cover with Soft Capacity
Maintaining External Memory Efficient Hash Tables
Efficient Algorithms and Hardness Results for the Weighted k-Server Problem
Multi-Agent Submodular Optimization
A Robust and Optimal Online Algorithm for Minimum Metric Bipartite Matching
Approximation algorithms that take advice
An Improved Analysis for a Greedy Remote-Clique Algorithm Using Factor-Revealing LPs
On Estimating Frequency Moments of Data Streams
Best Possible Approximation Algorithm for MAX SAT with Cardinality Constraint
Deterministic O(1)-Approximation Algorithms to 1-Center Clustering with Outliers
Refining the Adaptivity Notion in the Huge Object Model
The Power of Choice for Random Satisfiability
Every Property of Outerplanar Graphs is Testable
Sampling and Certifying Symmetric Functions
Computing Approximate PSD Factorizations
Sampling in Potts Model on Sparse Random Graphs
Range Avoidance for Low-Depth Circuits and Connections to Pseudorandomness
Quantum Property Testing for Bounded-Degree Graphs
Density Independent Algorithms for Sparsifying k-Step Random Walks
Limits on the Rate of Locally Testable Affine-Invariant Codes
The Maximum Label Propagation Algorithm on Sparse Random Graphs
Fourier Growth of Structured 𝔽 2 -Polynomials and Applications
An Embarrassingly Parallel Optimal-Space Cardinality Estimation Algorithm
Separating Decision Tree Complexity from Subcube Partition Complexity
On the Constant-Factor Approximability of Minimum Cost Constraint Satisfaction Problems
Streaming Approximation Resistance of Every Ordering CSP
Complete Convergence of Message Passing Algorithms for Some Satisfiability Problems
A Local Stochastic Algorithm for Separation in Heterogeneous Self-Organizing Particle Systems
Local Reconstructors and Tolerant Testers for Connectivity and Diameter
Single-Elimination Brackets Fail to Approximate Copeland Winner
Approximating Max kCSP Using Random Restrictions
Ramsey Properties of Randomly Perturbed Hypergraphs
Accelerating Polarization via Alphabet Extension
Asynchronous Majority Dynamics on Binomial Random Graphs
Improved Local Computation Algorithms for Constructing Spanners
Fast Algorithms at Low Temperatures via Markov Chains
Counting Independent Sets and Colorings on Random Regular Bipartite Graphs
Streaming Periodicity with Mismatches
Approximating Hit Rate Curves using Streaming Algorithms
Using Linear Programming in the Design and Analysis of Approximation Algorithms: Two Illustrative Problems
Approximating Subadditive Hadamard Functions on Implicit Matrices
Scheduling Splittable Jobs on Configurable Machines
On Higher-Order Fourier Analysis over Non-Prime Fields
Improved Bounds on the Phase Transition for the Hard-Core Model in 2-Dimensions
On Geodesically Convex Formulations for the Brascamp-Lieb Constant
Random-Cluster Dynamics in Z 2 : Rapid Mixing with General Boundary Conditions
Gap Amplification for Small-Set Expansion via Random Walks
Space Pseudorandom Generators by Communication Complexity Lower Bounds
Approximation Algorithms for Min-Max Generalization Problems
Correlation in Hard Distributions in Communication Complexity
Relative Survivable Network Design
On the Security of Goldreich's One-Way Function
Scheduling Problems over Network of Machines
Ordered k-Median with Outliers
Online Non-clairvoyant Scheduling to Simultaneously Minimize All Convex Functions
Approximating Maximum Edge Coloring in Multigraphs
Streaming Algorithms for Maximizing Monotone Submodular Functions under a Knapsack Constraint
Revisiting Connected Dominating Sets: An Optimal Local Algorithm?
Limitations of Hardness vs. Randomness under Uniform Reductions
Analysis of Algorithms on the Cores of Random Graphs
Improved Bounds for Open Online Dial-a-Ride on the Line
Approximating the Best-Fit Tree Under L p Norms
Sampling from the Random Cluster Model on Random Regular Graphs at All Temperatures via Glauber Dynamics
Testing Versus Estimation of Graph Properties, Revisited
Near Optimal Dimensionality Reductions That Preserve Volumes
Smoothed Analysis of the Condition Number Under Low-Rank Perturbations
Secretary Matching Meets Probing with Commitment
Tighter Approximation for the Uniform Cost-Distance Steiner Tree Problem
Rapid Mixing of Global Markov Chains via Spectral Independence: The Unbounded Degree Case
Improved Lower Bounds on Multiflow-Multicut Gaps
Exploring Differential Obliviousness
A Rounding Algorithm for Approximating Minimum Manhattan Networks
A Fast Coloring Oracle for Average Case Hypergraphs
What Would Edmonds Do? Augmenting Paths and Witnesses for Degree-Bounded MSTs
Tight Bounds for String Reconstruction Using Substring Queries
Integrality Gap of Time-Indexed Linear Programming Relaxation for Coflow Scheduling
Conditional Hardness of Earth Mover Distance
Almost Optimal Explicit Johnson-Lindenstrauss Families
Local Convergence of Random Graph Colorings
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2020, Virtual Conference, August 17-19, 2020
On Closeness to k-Wise Uniformity
Inapproximability of Treewidth, One-Shot Pebbling, and Related Layout Problems
Maximum Matching in Two, Three, and a Few More Passes Over Graph Streams
Sampling Multiple Edges Efficiently
Improved Approximation Guarantees for Advertisement Placement
Scheduling on Unrelated Machines Under Tree-Like Precedence Constraints
Optimal Lower Bounds for Universal and Differentially Private Steiner Trees and TSPs
Robust Approximation of Temporal CSP
Optimal Deterministic Extractors for Generalized Santha-Vazirani Sources
Harnessing the Bethe Free Energy
Learning and Lower Bounds for AC 0 with Threshold Gates
Single-Source Stochastic Routing
Matrix Multiplication Reductions
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2016, Paris, France, September 7-9, 2016
Primal-Dual Algorithms for Connected Facility Location Problems
Hitting Weighted Even Cycles in Planar Graphs
Online Row Sampling
Approximation Algorithms for Correlated Knapsack Orienteering
Deterministic Approximate Counting of Polynomial Threshold Functions via a Derandomized Regularity Lemma
Front Matter, Table of Contents, Preface, Program Committees, External Reviewers, List of Authors
Adaptive Sampling and Fast Low-Rank Matrix Approximation
Strong Refutation Heuristics for Random k-SAT
An Estimator for Matching Size in Low Arboricity Graphs with Two Applications
Tight Approximation Algorithms For Geometric Bin Packing with Skewed Items
Black-Box Identity Testing of Noncommutative Rational Formulas of Inversion Height Two in Deterministic Quasipolynomial Time
Spectral Norm of Symmetric Functions
Implementing Huge Sparse Random Graphs
Round Complexity Versus Randomness Complexity in Interactive Proofs
Online Facility Location with Linear Delay
Exploring the Gap Between Tolerant and Non-Tolerant Distribution Testing
A (3/2 + 1/e)-Approximation Algorithm for Ordered TSP
Faster Algorithms for Schatten-p Low Rank Approximation
Greedy Bipartite Matching in Random Type Poisson Arrival Model
Testing Isomorphism of Boolean Functions over Finite Abelian Groups
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2018, Princeton, NJ, USA, August 20-22, 2018
The Condensation Phase Transition in Random Graph Coloring
On Finding Frequent Elements in a Data Stream
Global and Fixed-Terminal Cuts in Digraphs
Tight Results on Minimum Entropy Set Cover
Capacity-Achieving Gray Codes
Approximating the Norms of Graph Spanners
PASS Approximation
Online Directed Spanners and Steiner Forests
Small Clique Detection and Approximate Nash Equilibria
The Biased Homogeneous r-Lin Problem
On Two-Pass Streaming Algorithms for Maximum Bipartite Matching
Fixed-Parameter Approximation Schemes for Weighted Flowtime
Monotone Circuits for the Majority Function
A Deterministic Fully Polynomial Time Approximation Scheme For Counting Integer Knapsack Solutions Made Easy
Optimal Sherali-Adams Gaps from Pairwise Independence
Maximum Flows on Disjoint Paths
Sweeping Points
Learning Circuits with few Negations
Rounding Two and Three Dimensional Solutions of the SDP Relaxation of MAX CUT
On Sums of Locally Testable Affine Invariant Properties
Periodicity in Streams
Unidirectional Input/Output Streaming Complexity of Reversal and Sorting
Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut
Testing st -Connectivity
Parametrized Metrical Task Systems
Upper and Lower Bounds for Complete Linkage in General Metric Spaces
Polynomial Identity Testing for Low Degree Polynomials with Optimal Randomness
A Constant-Factor Approximation for Quasi-Bipartite Directed Steiner Tree on Minor-Free Graphs
PTAS for Weighted Set Cover on Unit Squares
Fractional Matching Via Balls-and-Bins
Efficient Quantum Tensor Product Expanders and k-Designs
Stochastic Distance in Property Testing
Unbalanced Expanders from Multiplicity Codes
Towards a Constructive Version of Banaszczyk's Vector Balancing Theorem
An Optimal Lower Bound for Monotonicity Testing over Hypergrids
Additive Noise Mechanisms for Making Randomized Approximation Algorithms Differentially Private
Finding Graph Matchings in Data Streams
Small Space Stream Summary for Matroid Center
Classical Simulation of One-Query Quantum Distinguishers
On the Power of Choice for k-Colorability of Random Graphs
Approximating Pandora's Box with Correlations
Equality Is Far Weaker Than Constant-Cost Communication
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 14th International Workshop, APPROX 2011, and 15th International Workshop, RANDOM 2011, Princeton, NJ, USA, August 17-19, 2011. Proceedings
Simple Analysis of Sparse, Sign-Consistent JL
Worst-Case Vs. Algorithmic Average-Case Complexity in the Polynomial-Time Hierarchy
Optimal Convergence Rate of Hamiltonian Monte Carlo for Strongly Logconcave Distributions
Interplay Between Graph Isomorphism and Earth Mover's Distance in the Query and Communication Worlds
Approximation, Randomization and Combinatorial Optimization, Algorithms and Techniques, 8th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2005 and 9th InternationalWorkshop on Randomization and Computation, RANDOM 2005, Berkeley, CA, USA, August 22-24, 2005, Proceedings
L1 Regression with Lewis Weights Subsampling
Speed-Robust Scheduling Revisited
An ~O(n) Queries Adaptive Tester for Unateness
Minimum Vehicle Routing with a Common Deadline
Submodular Optimization with Contention Resolution Extensions
Approximate Hypergraph Coloring under Low-discrepancy and Related Promises
An Optimal Algorithm for Triangle Counting in the Stream
A Query Efficient Non-adaptive Long Code Test with Perfect Completeness
Two Sides of the Coin Problem
Memory-Sample Lower Bounds for Learning Parity with Noise
Counting Connected Graphs and Hypergraphs via the Probabilistic Method
Online Scheduling of Jobs with Fixed Start Times on Related Machines
Improved Bounds for Testing Juntas
Improved Product-Based High-Dimensional Expanders
Robustness for Space-Bounded Statistical Zero Knowledge
Rectangle tiling
Coarse Differentiation and Multi-flows in Planar Graphs
Generalizing the Layering Method of Indyk and Woodruff: Recursive Sketches for Frequency-Based Vectors on Streams
Is It Possible to Improve Yao's XOR Lemma Using Reductions That Exploit the Efficiency of Their Oracle?
Decision Tree Heuristics Can Fail, Even in the Smoothed Setting
Minimizing Setup and Beam-On Times in Radiation Therapy
Sample-Based High-Dimensional Convexity Testing
Delaying Satisfiability for Random 2SAT
New results for online page replication
Cover and Hitting Times of Hyperbolic Random Graphs
Commutative Algorithms Approximate the LLL-distribution
Random Subsets of the Interval and P2P Protocols
Time-Space Tradeoffs for Distinguishing Distributions and Applications to Security of Goldreich's PRG
Evaluating Stability in Massive Social Networks: Efficient Streaming Algorithms for Structural Balance
How to Tame Rectangles: Solving Independent Set and Coloring of Rectangles via Shrinking
Think Globally, Act Locally: On the Optimal Seeding for Nonsubmodular Influence Maximization
Randomness Extraction in AC0 and with Small Locality
Improved Approximation Algorithms for the Min-Max Tree Cover and Bounded Tree Cover Problems
Reconstruction of Markov Random Fields from Samples: Some Observations and Algorithms
Prize-Collecting Survivable Network Design in Node-Weighted Graphs
Ideal-Theoretic Explanation of Capacity-Achieving Decoding
On Sharp Thresholds in Random Geometric Graphs
Polynomial Mixing of the Edge-Flip Markov Chain for Unbiased Dyadic Tilings
Approximation Algorithm for Non-boolean MAX k-CSP
Efficient Algorithms for Fixed-Precision Instances of Bin Packing and Euclidean TSP
Improved Algorithm for the Half-Disjoint Paths Problem
Fair Correlation Clustering in General Graphs
Symmetric Interdiction for Matching Problems
On Constructing Spanners from Random Gaussian Projections
Cost-Sharing Mechanisms for Network Design
-Approximation for Treewidth of Graphs Excluding a Graph with One Crossing as a Minor
Density Frankl-Rödl on the Sphere
Approximating an Interval Scheduling Problem
Approximating the Influence of Monotone Boolean Functions in $O(\sqrt{n})$ Query Complexity
Approximating Precedence-Constrained Single Machine Scheduling by Coloring
A New Notion of Commutativity for the Algorithmic Lovász Local Lemma
Improved Polynomial Identity Testing for Read-Once Formulas
On Sampling from Multivariate Distributions
Percolation of Lipschitz Surface and Tight Bounds on the Spread of Information Among Mobile Agents
The Remote Set Problem on Lattices
Unsplittable Flow in Paths and Trees and Column-Restricted Packing Integer Programs
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2019, Massachusetts Institute of Technology, Cambridge, MA, USA, September 20-22, 2019
O(1)-Approximations for Maximum Movement Problems
Approximation Algorithms for Reliable Stochastic Combinatorial Optimization
Vector-Matrix-Vector Queries for Solving Linear Algebra, Statistics, and Graph Problems
Efficiently Decodable Codes for the Binary Deletion Channel
Testable Properties in General Graphs and Random Order Streaming
Decomposing Overcomplete 3rd Order Tensors using Sum-of-Squares Algorithms
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2014, Barcelona, Spain, September 4-6, 2014
Improved Approximation Algorithms for Matroid and Knapsack Median Problems and Applications
Malleable Scheduling Beyond Identical Machines
An Approximation Algorithm for the MAX-2-Local Hamiltonian Problem
Robust Mixing
An approximation algorithm for the fault tolerant metric facility location problem
Improved Hardness of Approximating Chromatic Number
A Tight Approximation Bound for the Stable Marriage Problem with Restricted Ties
Improved Rounding for Parallel Repeated Unique Games
Testing Hamiltonicity (And Other Problems) in Minor-Free Graphs
Robust Appointment Scheduling with Heterogeneous Costs
Torpid Mixing of Markov Chains for the Six-vertex Model on Z^2
Local Limit Theorems for the Giant Component of Random Hypergraphs
Semi-Direct Sum Theorem and Nearest Neighbor under l_infty
Probabilistic Metric Embedding via Metric Labeling
A Direct-Sum Theorem for Read-Once Branching Programs
Typical Rounding Problems
A Quadratic Lower Bound for Three-Query Linear Locally Decodable Codes over Any Field
On the Facility Location Problem in Online and Dynamic Models
Hardness of Approximation for Vertex-Connectivity Network-Design Problems
Mirror Descent Based Database Privacy
Weighted Sum Coloring in Batch Scheduling of Conflicting Jobs
Constant Approximation Algorithms for Embedding Graph Metrics into Trees and Outerplanar Graphs
On Sampling from Ising Models with Spectral Constraints
A Canonical Form for Testing Boolean Function Properties
Hardness Results for Weaver's Discrepancy Problem
Testing ±1-weight halfspace
Sparse High Dimensional Expanders via Local Lifts
Scheduling Subset Tests: One-Time, Continuous, and How They Relate
Breaking the epsilon-Soundness Bound of the Linearity Test over GF(2)
Renyi Entropy Estimation Revisited
Fractional Decompositions of Dense Hypergraphs
Approximation Algorithms for the Directed k-Tour and k-Stroll Problems
Large Supports are Required for Well-Supported Nash Equilibria
Viral Processes by Random Walks on Random Regular Graphs
Approximation Algorithms for the Max-Min Allocation Problem
Improved Spectral-Norm Bounds for Clustering
Approximating Unique Games Using Low Diameter Graph Decomposition
Instant recognition of polynominal time solvability, half integrality and 2-approximations
Fully Polynomial Time Approximation Schemes for Time-Cost Tradeoff Problems in Series-Parallel Project Networks
Approximating Additive Distortion of Embeddings into Line Metrics
On Approximating the Average Distance Between Points
On Hitting-Set Generators for Polynomials That Vanish Rarely
Randomized Approximation Algorithms for Set Multicover Problems with Applications to Reverse Engineering of Protein and Gene Networks
A Local Algorithm for Constructing Spanners in Minor-Free Graphs
Implications of Better PRGs for Permutation Branching Programs
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 10th International Workshop, APPROX 2007, and 11th International Workshop, RANDOM 2007, Princeton, NJ, USA, August 20-22, 2007, Proceedings
Relativized Worlds without Worst-Case to Average-Case Reductions for NP
Improved Approximation Algorithm for Steiner k-Forest with Nearly Uniform Weights
The Minimum Bisection in the Planted Bisection Model
Computational Complexity of Certifying Restricted Isometry Property
On the NP-Hardness Approximation Curve for Max-2Lin(2)
Sparse Recovery with Partial Support Knowledge
A General Framework for Designing Approximation Schemes for Combinatorial Optimization Problems with Many Objectives Combined into One
Derandomizing the Isolation Lemma and Lower Bounds for Circuit Size
Reaching a Consensus on Random Networks: The Power of Few
On Guillotine Cutting Sequences
Poly-logarithmic Approximation Algorithms for Directed Vehicle Routing Problems
Almost K-Wise vs. K-Wise Independent Permutations, and Uniformity for General Group Actions
Glauber Dynamics for Ising Model on Convergent Dense Graph Sequences
Polynominal time approximation schemes for class-constrained packing problem
Low-Degree Polynomials Are Good Extractors
Mixing Points on a Circle
Flow-time Optimization for Concurrent Open-Shop and Precedence Constrained Scheduling Models
Lifting with Inner Functions of Polynomial Discrepancy
Strong Parallel Repetition Theorem for Free Projection Games
A Note on Approximate Counting for k-DNF
Dependent Random Graphs and Multi-Party Pointer Jumping
Approximation algorithms for facility location problems
Improved Inapproximability for Submodular Maximization
Distribution-Free Connectivity Testing
Deterministic Approximation Algorithms for the Nearest Codeword Problem
Routing Symmetric Demands in Directed Minor-Free Graphs with Constant Congestion
Consumable Data via Quantum Communication
Independent Sets in Elimination Graphs with a Submodular Objective
Continuous Monitoring of l_p Norms in Data Streams
Cutoff for a Stratified Random Walk on the Hypercube
Lower Bound Methods for Sign-Rank and Their Limitations
Approximation algorithms for a capacitated network design problem
On Strong Diameter Padded Decompositions
Designing Overlapping Networks for Publish-Subscribe Systems
Tight Bounds for Sketching the Operator Norm, Schatten Norms, and Subspace Embeddings
Bounds for Error Reduction with Few Quantum Queries
Improved Mixing of Critical Hardcore Model
Sherali-Adams Gaps, Flow-cover Inequalities and Generalized Configurations for Capacity-constrained Facility Location
Weighted Maximum Independent Set of Geometric Objects in Turnstile Streams
Rainbow Coloring Hardness via Low Sensitivity Polymorphisms
Competitive Query Minimization for Stable Matching with One-Sided Uncertainty
Approximation Algorithms for Combinatorial Optimization, International Workshop APPROX'98, Aalborg, Denmark, July 18-19, 1998, Proceedings
Algorithms for 2-Connected Network Design and Flexible Steiner Trees with a Constant Number of Terminals
Approximating Optimal Binary Decision Trees
Rapid Mixing of the Down-Up Walk on Matchings of a Fixed Size
Matching Drivers to Riders: A Two-Stage Robust Approach
Weighted Matching in the Random-Order Streaming and Robust Communication Models
Constructive Proofs of Concentration Bounds
Finding Dense Subgraphs with Semidefinite Programming
Balanced Allocation on Dynamic Hypergraphs
The Expander Hitting Property When the Sets Are Arbitrarily Unbalanced
Vertex Sparsifiers: New Results from Old Techniques
Approximating Sparsest Cut in Graphs of Bounded Treewidth
A 4/3-Approximation Algorithm for the Minimum 2-Edge Connected Multisubgraph Problem in the Half-Integral Case
Approximation of Geometric Dispersion Problems
Massively Parallel Algorithms for Small Subgraph Counting
Derandomized Constructions of k-Wise (Almost) Independent Permutations
Testing Hereditary Properties of Sequences
A Simplified Reduction for Error Correcting Matrix Multiplication Algorithms
Approximation Guarantees for the Minimum Linear Arrangement Problem by Higher Eigenvalues
Streaming Verification for Graph Problems: Optimal Tradeoffs and Nonlinear Sketches
Consequences of Randomized Reductions from SAT to Time-Bounded Kolmogorov Complexity
Locating Depots for Capacitated Vehicle Routing
Towards Optimal Moment Estimation in Streaming and Distributed Models
Universal Optimization for Non-Clairvoyant Subadditive Joint Replenishment
Testing Permanent Oracles - Revisited
Collapsing Superstring Conjecture
Fast Synchronization of Random Automata
Optimal Pseudorandom Generators for Low-Degree Polynomials over Moderately Large Fields
Improved Online Algorithms for Knapsack and GAP in the Random Order Model
Propagation Connectivity of Random Hypergraphs
Efficient Black-Box Identity Testing for Free Group Algebras
An AFPTAS for Bin Packing with Partition Matroid via a New Method for LP Rounding
Proving Weak Approximability Without Algorithms
Truly Asymptotic Lower Bounds for Online Vector Bin Packing