yusuke1997/dblp-id-title huggingface dataset:
Regret Minimization for Reserve Prices in Second-Price Auctions
Buying cheap is expensive: hardness of non-parametric multi-product pricing
Interdependent Public Projects
Randomized Variants of Johnson's Algorithm for MAX SAT
Prize-collecting Steiner Problems on Planar Graphs
Minors and Dimension
Width of points in the streaming model
Computing Minimal Persistent Cycles: Polynomial and Hard Cases
How Good is the Chord Algorithm?
Maintaining deforming surface meshes
A 2+epsilon approximation algorithm for the k -MST problem
A Blossom Algorithm for Maximum Edge-Disjoint T -Paths
Deterministic Partially Dynamic Single Source Shortest Paths for Sparse Graphs
Compact Interval Trees: A Data Structure for Convex Hulls
Improved algorithms for fault tolerant facility location
Minimization is Harder in the Prophet World
Fast and Simple Sorting Using Partial Information
A Deterministic Linear Program Solver in Current Matrix Multiplication Time
Equidistribution of Point Sets for the Traveling Salesman and Related Problems
Average Sensitivity of Graph Algorithms
Tight Bounds and Phase Transitions for Incremental and Dynamic Retrieval
On Multi-Dimensional Packing Problems
Maintaining approximate extent measures of moving points
Assigning chain-like tasks to a chain-like network
A tight condition for triangle factors in pseudorandom graphs
Raising The Bar For Vertex Cover: Fixed-parameter Tractability Above A Higher Guarantee
On approximating the achromatic number
Region-fault tolerant geometric spanners
A unified approach to truthful scheduling on related machines
Optimal Search in Trees: Extended Abstract + Appendix
Weighted isotonic regression under the L 1 norm
EPTAS for k -means Clustering of Affine Subspaces
Lossless Online Rounding for Online Bipartite Matching (Despite its Impossibility)
Persistent Predecessor Search and Orthogonal point Location on the Word RAM
An Extension of the Lovász Local Lemma, and its Applications to Integer Programming
Exact algorithms for partial curve matching via the Fréchet distance
Solving the Replacement Paths Problem for Planar Directed Graphs in O(n log n) Time
Near-Optimal-Time Quantum Algorithms for Approximate Pattern Matching
Beating Brute Force for Systems of Polynomial Equations over Finite Fields
Weighted capacitated, priority, and geometric set cover via improved quasi-uniform sampling
Squarepants in a tree: sum of subtree clustering and hyperbolic pants decomposition
All-to-All Optical Routing in Optimal Chordal Rings of Degree Four
Foundations of Transaction Fee Mechanism Design
Trees and Markov convexity
Polynomiality for Bin Packing with a Constant Number of Item Types
On the approximability of influence in social networks
A New Perspective on Vertex Connectivity
On the Number of Minimum Size Separating Vertex Sets in a Graph and How to Find All of Them
A Polynomial Time Approximation Scheme for k-Consensus Clustering
Approximating the Minimum Degree Spanning Tree to Within One from the Optimal Degree
Computing Replacement Paths in Surface Embedded Graphs
Online ascending auctions for gradually expiring items
Euclidean spanners in high dimensions
A (2 + epsilon)-approximation scheme for minimum domination on circle graphs
Hierarchical Clustering better than Average-Linkage
Multiprocessor Scheduling with Rejection
Solving MAX-r-SAT Above a Tight Lower Bound
Even Faster (Δ + 1)-Edge Coloring via Shorter Multi-Step Vizing Chains
Efficient 2-dimensional Approximate Matching of Non-Rectangular Figures
Coresets Meet EDCS: Algorithms for Matching and Vertex Cover on Massive Graphs
Fast Hierarchical Clustering and Other Applications of Dynamic Closest Pairs
Equilibria of atomic flow games are not unique
Dynamic DFS in Undirected Graphs: breaking the O( m ) barrier
The optimal absolute ratio for online bin packing
On the temporal HZY compression scheme
List-coloring embedded graphs
Improved Approximation Algorithms for the Joint Replenishment Problem with Outliers, and with Fairness Constraints
Fully polynomial FPT algorithms for some classes of bounded clique-width graphs
I/O-Complexity of Graph Algorithms
Assignment Mechanisms under Distributional Constraints
Separable attributes: a technique for solving the sub matrices character count problem
Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2009, New York, NY, USA, January 4-6, 2009
Tree exploration with little memory
Tree Compatibility and Inferring Evoluationary History
Typical random 3-SAT formulae and the satisfiability threshold
Clustering to Minimize Cluster-Aware Norm Objectives
On the Uniqueness of Bayesian Coarse Correlated Equilibria in Standard First-Price and All-Pay Auctions
Ranking with Submodular Valuations
Approximating the maximum quadratic assignment problem
Positivity Certificates for Linear Recurrences
Concurrent Range Reporting in Two-Dimensional Space
Stochastic Submodular Cover with Limited Adaptivity
Multicoloring unit disk graphs on triangular lattice points
Improved Topological Approximations by Digitization
The Classical Complexity of Boson Sampling
Algorithms for facility location problems with outliers
Minimizing the number of lattice points in a translated polygon
LP-Based Robust Algorithms for Noisy Minor-Free and Bounded Treewidth Graphs
Dimensionality reduction techniques for proximity problems
Pricing Online Decisions: Beyond Auctions
Community Detection on Euclidean Random Graphs
Incremental Single Source Shortest Paths in Sparse Digraphs
Solving random satisfiable 3CNF formulas in expected polynomial time
An Improved Upper Bound for the Universal TSP on the Grid
New Techniques for Some Dynamic Closest-Point and Farthest-Point Problems
A computational study of external-memory BFS algorithms
Probabilistic clustering of high dimensional norms
Many distances in planar graphs
The maximum number of faces of the Minkowski sum of two convex polytopes
Coloring non-uniform hypergraphs: a new algorithmic approach to the general Lovász local lemma
Improved Approximation Algorithms for k -Submodular Function Maximization
Designing Networks with Good Equilibria under Uncertainty
A subexponential parameterized algorithm for Subset TSP on planar graphs
A Las Vegas O(n 2.38 ) Algorithm for the Cardinality of a Maximum Matching
Approximating Shallow-Light Trees (Extended Abstract)
Roots of a Polynomial and its Derivatives
Scheduling When You Don't Know the Number of Machines
The Power of Non-Uniform Wireless Power
Fast, Fair, and Frugal Bandwidth Allocation in ATM Networks
A Nearly Time-Optimal Distributed Approximation of Minimum Cost k -Edge-Connected Spanning Subgraph
Improved Sliding Window Algorithms for Clustering and Coverage via Bucketing-Based Sketches
Constructing a Tree from Homeomorphic Subtrees, with Applications to Computational Evolutionary Biology
Input Sparsity Time Low-rank Approximation via Ridge Leverage Score Sampling
Sharing one secret vs. sharing many secrets: tight bounds on the average improvement ratio
Two-Point Euclidean Shortest Path Queries in the Plane
Networks of random cycles
A Cell Probe Lower Bound for the Predecessor Search Problem in PRAM
On the Spanning and Routing Ratio of Theta-Four
Connectivity of Triangulation Flip Graphs in the Plane (Part I: Edge Flips)
A dynamic data structure for 3-d convex hulls and 2-d nearest neighbor queries
Resource-Efficient Common Randomness and Secret-Key Schemes
Matching Composition and Efficient Weight Reduction in Dynamic Matching
Lower Bounds for SRPT-Subsequence Algorithms for Nonpreemptive Scheduling
Linear index coding via semidefinite programming
Simple approximation algorithm for nonoverlapping local alignments
On differentially private low rank approximation
On the diameter of Eulerian orientations of graphs
Extremal Distances in Directed Graphs: Tight Spanners and Near-Optimal Approximation Algorithms
Allocating vertex pi-guards in simple polygons via pseudo-triangulations
The Fine-Grained Complexity of Computing the Tutte Polynomial of a Linear Matroid
A Lower Bound for the n-queens Problem
(Near-)Linear-Time Randomized Algorithms for Row Minima in Monge Partial Matrices and Related Problems
Robust Algorithms for Online Convex Problems via Primal-Dual
A 4 + ε approximation for k -connected subgraphs
Characterization and Algorithms for Greedily Solvable Transportation Problems
An n -to-1 Bidder Reduction for Multi-item Auctions and its Applications
Playing Anonymous Games using Simple Strategies
Near-Optimal Bounds for Online Caching with Machine Learned Advice
Direct Routing on Trees (Extended Abstract)
An almost O (log k )-approximation for k -connected subgraphs
Approximating the spanning star forest problem and its applications to genomic sequence alignment
Two algorithms for general list matrix partitions
A comparison of labeling schemes for ancestor queries
Randomized MWU for Positive LPs
Fair and efficient router congestion control
Euclidean Bottleneck Bounded-Degree Spanning Tree Ratios
Efficient pattern-matching with don't cares
Space-efficient dynamic orthogonal point location, segment intersection, and range reporting
Simple, deterministic, fast (but weak) approximations to edit distance and Dyck edit distance
Pass efficient algorithms for approximating large matrices
Optimally scheduling video-on-demand to minimize delay when server and receiver bandwidth may differ
Quantum algorithms for some hidden shift problems
Average-Case Analyses of First Fit and Random Fit Bin Packing
Restricted strip covering and the sensor cover problem
The diameter of random massive graphs
Approximation algorithms for data placement in arbitrary networks
Tight Bounds for Coalescing-Branching Random Walks on Regular Graphs
Fast approximation of the permanent for very dense problems
Tabulation based 4-universal hashing with applications to second moment estimation
Reducing Curse of Dimensionality: Improved PTAS for TSP (with Neighborhoods) in Doubling Metrics
Optimality of belief propagation for random assignment problem
Tight Running Time Lower Bounds for Strong Inapproximability of Maximum k -Coverage, Unique Set Cover and Related Problems (via t -Wise Agreement Testing Theorem)
A note on random 2-SAT with prescribed literal degrees
The Parameterized Complexity of k -Biclique
Visibility with a Moving Point of View
Partitioning into Expanders
Super-resolution and Robust Sparse Continuous Fourier Transform in Any Constant Dimension: Nearly Linear Time and Sample Complexity
Sparse Dynamic Programming
On-line Generalized Steiner Problem
Generosity Helps, or an 11-Competitive Algorithm for Three Servers
Approximate Nearest Neighbor Searching with Non-Euclidean and Weighted Distances
Transitive-closure spanners
k-means++: the advantages of careful seeding
Simple Concurrent Labeling Algorithms for Connected Components
Prophet Inequalities: Competing with the Top ℓ Items is Easy
Speed scaling with an arbitrary power function
Approximate String Matching: A Simpler Faster Algorithm
Foundations of Differentially Oblivious Algorithms
Differential Privacy in New Settings
(2Δ - l)-Edge-Coloring is Much Easier than Maximal Matching in the Distributed Setting
A Model of Computation for MapReduce
Approximating submodular functions everywhere
Lower bounds for asymmetric communication channels and distributed source coding
Splay Trees for Data Compression
Graph Products Revisited: Tight Approximation Hardness of Induced Matching, Poset Dimension and More
3rd Symposium on Simplicity in Algorithms, SOSA 2020, Salt Lake City, UT, USA, January 6-7, 2020
Fully dynamic all-pairs shortest paths with worst-case update-time revisited
Packing directed cycles through a specified vertex set
Smoothed Analysis of the Successive Shortest Path Algorithm
Sampling on Lattices with Free Boundary Conditions Using Randomized Extensions
On the value of coordination in network design
Efficient Suffix Trees on Secondary Storage (extended Abstract)
An O ( nm ) time algorithm for finding the min length directed cycle in a graph
I/O-Efficient Contour Queries on Terrains
An Intersection Model for Multitolerance Graphs: Efficient Algorithms and Hierarchy
A Near-Linear Approximation Scheme for Multicuts of Embedded Graphs with a Fixed Number of Terminals
Distributed algorithms for multicommodity flow problems via approximate steepest descent framework
The probabilistic relationship between the assignment and asymmetric traveling salesman problems
Edge Coloring Planar Graphs with Two Outerplanar Subgraphs
Speed scaling for weighted flow time
Online conflict-free coloring for intervals
How Many Vertices Does a Random Walk Miss in a Network with Moderately Increasing the Number of Vertices?
LSH Forest: Practical Algorithms Made Theoretical
An Upper Bound and Linear-Space Queries on the LZ-End Parsing
Online Stochastic Matching with Unequal Probabilities
The Complexity of Optimal Multidimensional Pricing
Interleaved Prefetching
Fast Algorithms for Interactive Coding
Strong Algorithms for the Ordinal Matroid Secretary Problem
Fast Low-Space Algorithms for Subset Sum
Local-on-Average Distributed Tasks
Approximation algorithms for projective clustering
On minimizing the total flow time on multiple machines
Quantum algorithms for the triangle problem
Near-optimal labeling schemes for nearest common ancestors
Fine-Grained Optimality of Partially Dynamic Shortest Paths and More
Efficient Computation of Representative Weight Functions with Applications to Parameterized Counting (Extended Version)
Submodular Function Maximization in Parallel via the Multilinear Relaxation
A Faster External Memory Priority Queue with DecreaseKeys
Optimal online bounded space multidimensional packing
Minor-matching hypertree width
Learning k -modal distributions via testing
Optimal Algorithms for Tree Partitioning
On the Performance of Spectral Graph Partitioning Methods
An Efficient Parallel Algorithm for the General Planar Monotone Circuit Value Problem
A Slique Size Bounding Technique with Application to Non-Linear Codes
On Buffon Machines and Numbers
Better Approximation Algorithms for the Graph Diameter
Ergodic Effects in Token Circulation
Fully Dynamic Min-Cut of Superconstant Size in Subpolynomial Time
Counting independent sets in unbalanced bipartite graphs
The Complexity of All-switches Strategy Improvement
Revenue Maximization for Buyers with Costly Participation
Concentration inequalities for nonlinear matroid intersection
An Empirical Study of Dynamic Graph Algorithms (Extended Abstract)
Massively Parallel Algorithms for High-Dimensional Euclidean Minimum Spanning Tree
New Approximations for Reordering Buffer Management
Cut Sparsification of the Clique Beyond the Ramanujan Bound: A Separation of Cut Versus Spectral Sparsification
Single-minded unlimited supply pricing on sparse instances
Complexity classification of network information flow problems
Ordinal embeddings of minimum relaxation: general properties, trees, and ultrametrics
Improved Bounds for Orthogonal Point Enclosure Query and Point Location in Orthogonal Subdivisions in ℝ 3
Sparse 0-1-Matrices and Forbidden Hypergraphs (Extended Abstract)
Directed s-t Bumberings, Rubber Bands, and Testing Digraph k -Vertex Connectivity
A Max-Flow/Min-Cut Algorithm for a Class of Wireless Networks
On the Extremal Functions of Acyclic Forbidden 0-1 Matrices
Faster Sublinear Algorithms using Conditional Sampling
Job shop scheduling with unit processing times
Non-Uniform Graph Partitioning
LAST but not Least: Online Spanners for Buy-at-Bulk
Sampling Equilibria: Fast No-Regret Learning in Structured Games
Simplicity and Hardness of the Maximum Traveling Salesman Problem Under Geometric Distances
Conflict Checkable and Decodable Codes and Their Applications
Pattern discovery on character sets and real-valued data: linear bound on irredundant motifs and an efficient polynomial time algorithm
An improved bound on the fraction of correctable deletions
Nearly Optimal NP-Hardness of Unique Coverage
Approximating the Arboricity in Sublinear Time
In-Place Sparse Suffix Sorting
A Combinatorial Algorithm for Minimizing Symmetric Submodular Functions
Competitive Routing of Virtual Circuits with Unknown Duration
Weisfeiler-Leman and Graph Spectra
On the red-blue set cover problem
Faster algorithms for string matching with k mismatches
Caching with expiration times
Polygon Placement Revisited: (Degree of Freedom + 1)-SUM Hardness and an Improvement via Offline Dynamic Rectangle Union
Persistent Homology and Nested Dissection
On the Complexity of Approximating a Nash Equilibrium
Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2006, Miami, Florida, USA, January 22-26, 2006
A nearly linear time algorithm for the half integral parity disjoint paths packing problem
Lower bounds for the parameterized complexity of Minimum Fill-In and other completion problems
A (3 + ɛ)-Approximate Correlation Clustering Algorithm in Dynamic Streams
Planar Distance Oracles with Better Time-Space Tradeoffs
Sublinear Algorithms for (Δ + 1) Vertex Coloring
Approximating Multiroot 3-Outconnected Subgraphs
New Approximation Algorithms and Reductions for n -Pairs Shortest Paths and All-Nodes Shortest Cycles
A Sublinear-Time Quantum Algorithm for Approximating Partition Functions
Wavelength assignment and generalized interval graph coloring
8/7-approximation algorithm for (1, 2)-TSP
A generic top-down dynamic-programming approach to prefix-free coding
The Johnson-Lindenstrauss lemma almost characterizes Hilbert space, but not quite
The Power of Two Choices with Simple Tabulation
Capacity of Interactive Communication over Erasure Channels and Channels with Feedback
An approximate truthful mechanism for combinatorial auctions with single parameter agents
Kernelization for Graph Packing Problems via Rainbow Matching
Competitive Information Design for Pandora's Box
Dynamic Set Cover: Improved Amortized and Worst-Case Update Time
Performance study of phylogenetic methods: (unweighted) quartet methods and neighbor-joining
Improved Cheeger's Inequality and Analysis of Local Graph Partitioning using Vertex Expansion and Expansion Profile
A Subquadratic Approximation Scheme for Partition
On the Entropy of DNA: Algorithms and Measurements Based on Memory and Rapid Convergence
Parallel Integer Sorting is More Efficient than Parallel Comparison Sorting on Exclusive Write PRAMs
The rainbow skip graph: a fault-tolerant constant-degree distributed data structure
Counting perfect matchings as fast as Ryser
Algorithmic Thresholds for Refuting Random Polynomial Systems
A logic-based algorithmic meta-theorem for mim-width
New Bounds for Matrix Multiplication: from Alpha to Omega
Optimal Oblivious Parallel RAM
Linear-time compression of bounded-genus graphs into information-theoretically optimal number of bits
Parallel Exact Shortest Paths in Almost Linear Work and Square Root Depth
Fast Estimation of Diameter and Shortest Paths (without Matrix Multiplication)
Natural algorithms
Cutting cycles of rods in space: hardness and approximation
Rényi-infinity constrained sampling with d 3 membership queries
Exploring Unknown Undirected Graphs
Scheduling Parallel DAG Jobs Online to Minimize Average Flow Time
Near Linear Time Approximation Schemes for Uncapacitated and Capacitated b-Matching Problems in Nonbipartite Graphs
A Grid-Based Approximation Algorithm for the Minimum Weight Triangulation Problem
Deterministic Algorithms for Decremental Shortest Paths via Layered Core Decomposition
Fast Approximate Graph Partitioning Algorithms
Fast mixing for independent sets, colorings and other models on trees
Balls into Bins via Local Search
Finding Stabbing Lines in 3-Dimensional Space
Using Randomized Sparsification to Approximate Minimum Cuts
Approximating TSP on metrics with bounded global growth
Broadcast in Radio Networks
(Un)expected behavior of digital search tree profile
Marriage, honesty, and stability
Strategies for Stable Merge Sorting
Scheduling heterogeneous processors isn't as easy as you think
Center and diameter problems in plane triangulations and quadrangulations
Sampling Random Colorings of Sparse Random Graphs
On the orbit closure intersection problems for matrix tuples under conjugation and left-right actions
Sharp Dichotomies for Regret Minimization in Metric Spaces
Testing bounded arboricity
Faster Algorithms for the Quickest Transshipment Problem with Zero Transit Times
A nearly linear time algorithm for the half integral disjoint paths packing
Multi-Item Inventory Staggering Problems: Heuristic and Bounds
Random Walks with the Minimum Degree Local Rule Have O ( N 2 ) Cover Time
Random Walks and Evolving Sets: Faster Convergences and Limitations
How to Morph Graphs on the Torus
Optimality of Glauber dynamics for general-purpose Ising model sampling and free energy approximation
A Õ ( n 2 ) Time-Space Trade-off for Undirected s-t Connectivity
A note on the nearest neighbor in growth-restricted metrics
Searching Tree Structures on a Mesh of Processors
A Faster Algorithm for Minimum-Cost Bipartite Perfect Matching in Planar Graphs
Testing Surface Area
Succinct indexes for strings, binary relations and multi-labeled trees
On stars and Steiner stars
New Prophet Inequalities via Poissonization and Sharding
The rectilinear Steiner arborescence problem is NP-complete
How to Make a Square Grid Framework with Cables Rigid
The price of being near-sighted
A Polynomial Time Algorithm for the k -Disjoint Shortest Paths Problem
Adaptive local ratio
On Nonlinear Forbidden 0-1 Matrices: A Refutation of a Füredi-Hajnal Conjecture
Interpolating Between Truthful and non-Truthful Mechanisms for Combinatorial Auctions
The Communication Complexity of Set Intersection and Multiple Equality Testing
Greedy drawings of triangulations
Weighted dynamic finger in binary search trees
Output-sensitive construction of the union of triangles
Improved schedule for radio broadcast
Partial Matching of Planar Polylines Under Similarity Transformations
Metrical task systems on trees via mirror descent and unfair gluing
An O(n log n) Algorithm for the Maximum Agreement Subtree Problem for Binary Trees
Multiple-source shortest paths in planar graphs
Optimal Inapproximability with Universal Factor Graphs
Improved output-sensitive quantum algorithms for Boolean matrix multiplication
Towards a Unified Theory of Sparsification for Matching Problems
Recovering Branches on the Tree of Life: An Approximation Algorithm
Isomorphism Testing and Display of Symmetries in Dynamic Trees
On-line Search in a Simple Polygon
Scheduling Parallel Tasks to Minimize Average Response Time
Overhang
Adaptive Quantum Simulated Annealing for Bayesian Inference and Estimating Partition Functions
Detecting Weakly Simple Polygons
Single-Pass Streaming Algorithms for Correlation Clustering
Minimizing the stabbing number of matchings, trees, and triangulations
Geometric and topological guarantees for the WRAP reconstruction algorithm
Terrain Guarding is NP-Hard
Skip graphs
Linear-Time Modular Decomposition and Efficient Transitive Orientation of Comparability Graphs
Sampling algorithms for l 2 regression and applications
Randomized Communication and Implicit Representations for Matrices and Graphs of Small Sign-Rank
A simple combinatorial algorithm for submodular function minimization
Inplace 2D matching in compressed images
Improved fast integer sorting in linear space
How fast is the k-means method?
Gathering despite mischief
Greedy Strikes Back: Improved Facility Location Algorithms
Ultra-fast rumor spreading in social networks
Ironing in Dynamic Revenue Management: Posted Prices & Biased Auctions
Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2008, San Francisco, California, USA, January 20-22, 2008
Graph Coloring via The Probabilistic Method
Approximating Optimal Transport With Linear Programs
Computing the writhing number of a polygonal knot
On Rationality of Nonnegative Matrix Factorization
Asymptotically optimal frugal colouring
Deterministic Budget-Feasible Clock Auctions
Computing the Local Consensus of Trees
LP Based Approach to Optimal Stable Matchings
A Constant-Factor Approximation for Wireless Capacity Maximization with Power Control in the SINR Model
Distinguishing String Selection Problems
Beating Brute Force for (Quantified) Satisfiability of Circuits of Bounded Treewidth
Learning Binary Matroid Ports