A threshold of ln n for approximating set cover

DOI10.1145/285055.285059zbMath1065.68573OpenAlexW2143996311WikidataQ56443116 ScholiaQ56443116MaRDI QIDQ3158517

Uriel Feige

Publication date: 25 January 2005

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/285055.285059

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

A-priori upper bounds for the set covering problem, Streaming algorithms for robust submodular maximization, Greedy approximation for the minimum connected dominating set with labeling, Faster approximation algorithms for maximizing a monotone submodular function subject to a \(b\)-matching constraint, Beyond Moulin mechanisms, Approximation algorithms for solving the constrained arc routing problem in mixed graphs, Set multi-covering via inclusion-exclusion, Give-and-take based peer-to-peer content distribution networks, Analysis of approximation algorithms for \(k\)-set cover using factor-revealing linear programs, Multi-level facility location as the maximization of a submodular set function, Approximation algorithms for requirement cut on graphs, Node-weighted Steiner tree approximation in unit disk graphs, Constant approximation algorithms for the one warehouse multiple retailers problem with backlog or lost-sales, Construction algorithms and approximation bounds for the streaming cache placement problem in multicast networks, Finding a collective set of items: from proportional multirepresentation to group recommendation, Sparse approximation is provably hard under coherent dictionaries, Partial multicuts in trees, Refined algorithms for hitting many intervals, Approximation algorithms for inventory problems with submodular or routing costs, Directed Steiner trees with diffusion costs, Towards the price of leasing online, A practical greedy approximation for the directed Steiner tree problem, Experiments on data reduction for optimal domination in networks, Exact algorithms and applications for tree-like Weighted Set Cover, Cost sharing and strategyproof mechanisms for set cover games, New dominating sets in social networks, Black-box Trace\&Revoke codes, Reoptimization of constraint satisfaction problems with approximation resistant predicates, Thresholded covering algorithms for robust and max-min optimization, Heuristic algorithms in computational molecular biology, On the approximability of robust spanning tree problems, An improved algorithm for the red-blue hitting set problem with the consecutive ones property, Scheduling large-scale micro/nano biochemical testing: Exact and heuristic algorithms, Maximizing non-monotone submodular set functions subject to different constraints: combined algorithms, Fast approximate energy minimization with label costs, Geometric rounding: A dependent randomized rounding scheme, A closest vector problem arising in radiation therapy planning, Complexity of majority monopoly and signed domination problems, Steiner tree reoptimization in graphs with sharpened triangle inequality, The complexity of minimum convex coloring, The class cover problem with boxes, On the approximation ability of evolutionary optimization with application to minimum set cover, Uniform unweighted set cover: the power of non-oblivious local search, A unified approach to approximating partial covering problems, Towards strong nonapproximability results in the Lovász-Schrijver hierarchy, Improved approximation for guarding simple galleries from the perimeter, Algorithms for the minimum weight \(k\)-fold (connected) dominating set problem, Approximating some network design problems with node costs, NP-completeness and APX-completeness of restrained domination in graphs, Online maximum \(k\)-coverage, GMPLS label space minimization through hypergraph layouts, Complexity and approximation of the connected set-cover problem, Approximation algorithms for supply chain planning and logistics problems with market choice, Algorithmic aspects of \(k\)-tuple total domination in graphs, A survey on the structure of approximation classes, On the complexity of searching in trees and partially ordered structures, On the existence of polynomial-time approximation schemes for the reoptimization of discrete optimization problems, A note on `Algorithms for connected set cover problem and fault-tolerant connected set cover problem', Reoptimization of max \(k\)-cover: approximation ratio threshold, Computing on binary strings, Bounding the payment of approximate truthful mechanisms, Inapproximability of dominating set on power law graphs, Total domishold graphs: a generalization of threshold graphs, with connections to threshold hypergraphs, Detecting monomials with \(k\) distinct variables, Budgeted nature reserve selection with diversity feature loss and arbitrary split systems, The computational complexity and approximability of a series of geometric covering problems, On the computational complexity of measuring global stability of banking networks, Evader interdiction: algorithms, complexity and collateral damage, Computing cooperative solution concepts in coalitional skill games, On the hardness of full Steiner tree problems, On the complexity of making a distinguished vertex minimum or maximum degree by vertex deletion, A note on the clustered set covering problem, On nonlinear multi-covering problems, Benders decomposition for set covering problems. Almost satisfying the consecutive ones property, Improved approximation algorithms for projection games, Maximizing a submodular function with viability constraints, Optimization with uniform size queries, The within-strip discrete unit disk cover problem, Hanabi is NP-hard, even for cheaters who look at their cards, An improved approximation algorithm for the most points covering problem, Minimum entropy combinatorial optimization problems, Capacitated domination problem, Evaluation of Combinatorial Optimisation Algorithms for c-Optimal Experimental Designs with Correlated Observations, Video distribution under multiple constraints, Teaching randomized learners with feedback, Hyperbolic set covering problems with competing ground-set elements, The ordered covering problem, Performance bounds with curvature for batched greedy optimization, A set covering based approach to find the reduct of variable precision rough set, Phylogenetic diversity and the maximum coverage problem, On the maximum betweenness improvement problem, Hitting sets online and unique-MAX coloring, Multi-path algorithms for minimum-colour path problems with applications to approximating barrier resilience, Approximation algorithms for the partition vertex cover problem, A randomised approximation algorithm for the hitting set problem, Approximating the minimum independent dominating set in perturbed graphs, Prototype selection for interpretable classification, An order-based algorithm for minimum dominating set with application in graph mining, Iterative Dutch combinatorial auctions, Multi-rooted greedy approximation of directed Steiner trees with applications, Siting renewable power generation assets with combinatorial optimisation, The maximum exposure problem, A new greedy strategy for maximizing monotone submodular function under a cardinality constraint, Clustering with or without the approximation, On the complexity of optimising variants of phylogenetic diversity on phylogenetic networks, Adding cardinality constraints to integer programs with applications to maximum satisfiability, Ranking with submodular functions on a budget, On maximizing the difference between an approximately submodular function and a linear function subject to a matroid constraint, Streaming submodular maximization under differential privacy noise, On the \(k\)-colored rainbow sets in fixed dimensions, A multi-pass streaming algorithm for regularized submodular maximization, Logical analysis of data -- the vision of Peter L. Hammer, Maximizing a non-decreasing non-submodular function subject to various types of constraints, Learning in auctions: regret is hard, envy is easy, Tight approximation bounds for combinatorial frugal coverage algorithms, Approximation algorithm for uniform bounded facility location problem, Leafy spanning \(k\)-forests, Approximating activation edge-cover and facility location problems, On the geometric set multicover problem, Domination chain: characterisation, classical complexity, parameterised complexity and approximability, GRMA: generalized range move algorithms for the efficient optimization of MRFs, The approximability of multiple facility location on directed networks with random arc failures, Scalable influence maximization for independent cascade model in large-scale social networks, Exact algorithms for edge domination, A 6/5-approximation algorithm for the maximum 3-cover problem, Energy-efficient communication in multi-interface wireless networks, Algorithm and hardness results on neighborhood total domination in graphs, Community-based rumor blocking maximization in social networks: algorithms and analysis, A simple deterministic algorithm for symmetric submodular maximization subject to a knapsack constraint, Donation center location problem, PASS approximation: a framework for analyzing and designing heuristics, Greed is good for deterministic scale-free networks, Heuristic-based feature selection for rough set approach, On the establishment of distinct identities in overlay networks, On approximation of dominating tree in wireless sensor networks, Feedback robustness in structured closed-loop system, Maximize a monotone function with a generic submodularity ratio, Improved budgeted connected domination and budgeted edge-vertex domination, The Small Set Vertex expansion problem, Online budgeted maximum coverage, Deterministic approximation algorithm for submodular maximization subject to a matroid constraint, The projection games conjecture and the hardness of approximation of Super-SAT and related problems, Easy capacitated facility location problems, with connections to lot-sizing, Better lower and upper bounds for the minimum rainbow subgraph problem, A note on solving DiDi's driver-order matching problem, Network construction with subgraph connectivity constraints, A multi-parameter analysis of hard problems on deterministic finite automata, Hardness results, approximation and exact algorithms for liar's domination problem in graphs, Restricted parameter range promise set cover problems are easy, Timetabling with passenger routing, Temporal vertex cover with a sliding time window, Optimal RSUs placement with delay bounded message dissemination in vehicular networks, Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs, On the approximability of positive influence dominating set in social networks, Minimization problems for parity OBDDs, Optimizing node infiltrations in complex networks by a local search based heuristic, Dominating set of rectangles intersecting a straight line, Approximating constrained minimum cost input-output selection for generic arbitrary pole placement in structured systems, Smooth and strong PCPs, Algorithms and complexity for a class of combinatorial optimization problems with labelling, Two-stage combinatorial optimization problems under risk, Polyhedral circuits and their applications, Community-based rumor blocking maximization in social networks, Non-submodular streaming maximization with minimum memory and low adaptive complexity, Approximation algorithms for the connected sensor cover problem, Near-linear algorithms for geometric hitting sets and set covers, Constrained submodular maximization via greedy local search, Approximability of open \(k\)-monopoly problems, Generalized budgeted submodular set function maximization, On the complexity and approximability of repair position selection problem, Algorithmic aspects of Roman domination in graphs, Mixed integer programming with convex/concave constraints: fixed-parameter tractability and applications to multicovering and voting, Non-submodular maximization on massive data streams, Approximation algorithms for connected maximum coverage problem for the discovery of mutated driver pathways in cancer, A refined analysis of submodular greedy, The ordered \(k\)-median problem: surrogate models and approximation algorithms, Efficient approximation algorithms for maximum coverage with group budget constraints, An almost optimal approximation algorithm for monotone submodular multiple knapsack, Computing a small agreeable set of indivisible items, Set cover problems with small neighborhood covers, Parameterized analysis of the online priority and node-weighted Steiner tree problems, Better streaming algorithms for the maximum coverage problem, On interval and circular-arc covering problems, Bicriteria streaming algorithms to balance gain and cost with cardinality constraint, Fractionally subadditive maximization under an incremental knapsack constraint, Approximation algorithms for the geometric firefighter and budget fence problems, Problems and algorithms for covering arrays via set covers, Private non-monotone submodular maximization, A local search 4/3-approximation algorithm for the minimum 3-path partition problem, The metric distortion of multiwinner voting, An \(O(\lg \lg {\mathrm {OPT}})\)-approximation algorithm for multi-guarding galleries, Informative path planning as a maximum traveling salesman problem with submodular rewards, Capacitated domination: problem complexity and approximation algorithms, Approximability of the upper chromatic number of hypergraphs, Minimum budget for misinformation detection in online social networks with provable guarantees, Maximum coverage with cluster constraints: an LP-based approximation technique, Tight bounds on subexponential time approximation of set cover and related problems, Tight approximation bounds for maximum multi-coverage, Approximability of guarding weak visibility polygons, A heuristic for cumulative vehicle routing using column generation, Towards optimal lower bounds for clique and chromatic number., Inapproximability results for equations over finite groups, On the hardness of the minimum height decision tree problem, On domain-partitioning induction criteria: worst-case bounds for the worst-case based, Domination in some subclasses of bipartite graphs, A new approximation algorithm for \(k\)-set cover problem, Dynamic algorithms via the primal-dual method, Probabilistic distributed algorithms for energy efficient routing and tracking in wireless sensor networks, Submodular learning and covering with response-dependent costs, Randomized approximation algorithms for set multicover problems with applications to reverse engineering of protein and gene networks, Calculating approximation guarantees for partial set cover of pairs, Secluded connectivity problems, Decision trees for function evaluation: simultaneous optimization of worst and expected cost, On the approximability of the minimum rainbow subgraph problem and other related problems, Maximum coverage problem with group budget constraints, Multiple facility location on a network with linear reliability order of edges, A simple approximation algorithm for minimum weight partial connected set cover, FPT approximation schemes for maximizing submodular functions, Min-energy broadcast in mobile ad hoc networks with restricted motion, Domination parameters with number 2: interrelations and algorithmic consequences, An accelerated continuous greedy algorithm for maximizing strong submodular functions, Minimizing energies with hierarchical costs, The knapsack problem with neighbour constraints, Committee polyhedral separability: complexity and polynomial approximation, The probabilistic minimum dominating set problem, Spider covers and their applications, Strong LP formulations for scheduling splittable jobs on unrelated machines, Exponential inapproximability of selecting a maximum volume sub-matrix, Welfare maximization with friends-of-friends network externalities, Improved approximation for spanning star forest in dense graphs, Maximum subset intersection, On the approximability of covering points by lines and related problems, On good algorithms for determining unsatisfiability of propositional formulas, An exact algorithm for the maximum leaf spanning tree problem., A logarithmic approximation for polymatroid congestion games, On the adaptivity gap in two-stage robust linear optimization under uncertain packing constraints, Computing the arrangement of circles on a sphere, with applications in structural biology, On approximability of linear ordering and related NP-optimization problems on graphs., Tight results on minimum entropy set cover, On the computational complexity of the minimum committee problem, A note on maximizing a submodular set function subject to a knapsack constraint, Hardness of optimal spaced seed design, Recommending links through influence maximization, Parameterized and approximation complexity of \textsc{Partial VC Dimension}, Counting the number of independent sets in chordal graphs, Designing cost-sharing methods for Bayesian games, On the complexity of minimizing interference in ad-hoc and sensor networks, Efficient sensor network design for continuous monitoring of moving objects, Computational study on a PTAS for planar dominating set problem, Rounding to an integral program, Inapproximability results for combinatorial auctions with submodular utility functions, Online dominating set, Complete partitions of graphs, Near-linear time approximation schemes for geometric maximum coverage, Towards flexible demands in online leasing problems, Improved algorithms and complexity results for power domination in graphs, Short cycles make \(W\)-hard problems hard: FPT algorithms for \(W\)-hard problems in graphs with no short cycles, Approximation hardness of dominating set problems in bounded degree graphs, Complexity of distance paired-domination problem in graphs, On the approximability of Dodgson and Young elections, Approximability of clausal constraints, A note on line broadcast in digraphs under the edge-disjoint paths mode, Inapproximability results for equations over infinite groups, Algorithms for storage allocation based on client preferences, A \(\Theta (\log n)\)-approximation for the set cover problem with set ownership, Improved approximation algorithms for capacitated facility location problems, Domination in graphs with bounded propagation: Algorithms, formulations and hardness results, Broadcast routing with minimum wavelength conversion in WDM optical networks, Exponential-time approximation of weighted set cover, Incremental deployment of network monitors based on Group Betweenness Centrality, Risk averse submodular utility maximization, Assortment optimization over time, Maximizing expected utility over a knapsack constraint, A constructive proof of swap local search worst-case instances for the maximum coverage problem, Semi-preemptive routing on trees, Lift-and-project methods for set cover and knapsack, Computational complexity of the minimum committee problem and related problems, Robust monotone submodular function maximization, Maximizing monotone submodular functions over the integer lattice, Reduced error pruning of branching programs cannot be approximated to within a logarithmic factor, Path hitting in acyclic graphs, Red-blue covering problems and the consecutive ones property, Efficient approximation of Min Set Cover by moderately exponential algorithms, On approximating four covering and packing problems, An application of the greedy heuristic of set cover to traffic checks, An analysis of the size of the minimum dominating sets in random recursive trees, using the Cockayne-Goodman-Hedetniemi algorithm, Independent sets in bounded-degree hypergraphs, A new approach for approximating node deletion problems, On approximation algorithms for the terminal Steiner tree problem, Hardness results and approximation algorithms of \(k\)-tuple domination in graphs, Hardness results and approximation algorithms for (weighted) paired-domination in graphs, Computational study on planar dominating set problem, Absolute \(o(\log m)\) error in approximating random set covering: an average case analysis, Worst-case analysis of the greedy algorithm for a generalization of the maximum \(p\)-facility location problem, The labeled perfect matching in bipartite graphs, A note on submodular set cover on matroids, Steiner trees in uniformly quasi-bipartite graphs., A note on the minimum label spanning tree., On bounded occurrence constraint satisfaction, A note on the MST heuristic for bounded edge-length Steiner trees with minimum number of Steiner points, Approximation of the Clustered Set Covering Problem, The load-distance balancing problem, A PTAS for the Weighted Unit Disk Cover Problem, On the Approximability of Orthogonal Order Preserving Layout Adjustment, Dominating problems in swapped networks, Experimental Design for Nonparametric Correction of Misspecified Dynamical Models, Exact learning from an honest teacher that answers membership queries, An Improved Approximation Bound for Spanning Star Forest and Color Saving, Energy-Efficient Communication in Multi-interface Wireless Networks, Robust Monotone Submodular Function Maximization, Submodular Stochastic Probing on Matroids, Improved approximation algorithms for the spanning star forest problem, On the Complexity of the Minimum Independent Set Partition Problem, Linear Time Approximation Schemes for Geometric Maximum Coverage, AN ALGORITHMIC FRAMEWORK FOR SOLVING GEOMETRIC COVERING PROBLEMS — WITH APPLICATIONS, Computing approximate Nash equilibria in network congestion games with polynomially decreasing cost functions, Generalized threshold processes on graphs, A multiple testing method for hypotheses structured in a directed acyclic graph, Extending the kernel for planar Steiner tree to the number of Steiner vertices, Complexity and Approximation Results for the Balance Optimization Subset Selection Model for Causal Inference in Observational Studies, Stochastic-lazier-greedy algorithm for monotone non-submodular maximization, Line segment covering of cells in arrangements, Randomized Online Algorithms for Set Cover Leasing Problems, A Practical Greedy Approximation for the Directed Steiner Tree Problem, Bounds on Double-Sided Myopic Algorithms for Unconstrained Non-monotoneSubmodular Maximization, On maximizing a monotone \(k\)-submodular function under a knapsack constraint, Minimal observability of Boolean control networks, Hedonic expertise games, Strong Inapproximability of the Shortest Reset Word, Discrete Stochastic Submodular Maximization: Adaptive vs. Non-adaptive vs. Offline, Higher order monotonicity and submodularity of influence in social networks: from local to global, Optimization with demand oracles, Revisiting connected dominating sets: an almost optimal local information algorithm, Multiwinner analogues of the plurality rule: axiomatic and algorithmic perspectives, On the computational complexities of three problems related to a privacy measure for large networks under active attack, Capacitated Domination and Covering: A Parameterized Perspective, Submodular maximization over data streams with differential privacy noise, Multi-objective evolutionary algorithms are generally good: maximizing monotone submodular functions over sequences, Parameterized exact and approximation algorithms for maximumk-set cover and related satisfiability problems, An improved approximation algorithm for the minimum 3-path partition problem, Approximation of the quadratic set covering problem, Approximability of the firefighter problem. Computing cuts over time, Near-linear approximation algorithms for geometric hitting sets, The multi-budget maximum weighted coverage problem, Super-Polylogarithmic Hypergraph Coloring Hardness via Low-Degree Long Codes, Scheduling to minimize gaps and power consumption, Approximation algorithms for priority Steiner tree problems, Constrained hitting set problem with intervals, The subdivision-constrained routing requests problem, Maximizing coverage while ensuring fairness: a tale of conflicting objectives, Optimal approximability of bookmark assignments, Inequalities on submodular functions via term rewriting, A note on the hardness of sparse approximation, On the \(k\)-edge-incident subgraph problem and its variants, On the complexity of the selective graph coloring problem in some special classes of graphs, Approximation Algorithm for the Uniform Bounded Facility Problem, On Variants of the Spanning Star Forest Problem, Complexity of Total {k}-Domination and Related Problems, Tight Approximation Bounds for Greedy Frugal Coverage Algorithms, Set Covering with Ordered Replacement: Additive and Multiplicative Gaps, Approximation Algorithms for Single and Multi-Commodity Connected Facility Location, Domination When the Stars Are Out, Primal-Dual Approximation Algorithms for Node-Weighted Steiner Forest on Planar Graphs, Maximum patterns in datasets, Approximating the online set multicover problems via randomized winnowing, Minimum cost source location problems with flow requirements, Tight approximability results for test set problems in bioinformatics, Combinatorial approximation algorithms: a comparative review, A modified greedy algorithm for dispersively weighted 3-set cover, Approximating the two-level facility location problem via a quasi-greedy approach, Disjoint bases in a polymatroid, Cost-effective designs of fault-tolerant access networks in communication systems, Integrating facility location and production planning decisions, On the Complexity Landscape of the Domination Chain, An LP-Based Correlated Rounding Scheme for Multi-Item Ecommerce Order Fulfillment, On covering by translates of a set, Bulk-robust combinatorial optimization, Limitations of randomized mechanisms for combinatorial auctions, Line planning, path constrained network flow and inapproximability, Recognizing when heuristics can approximate minimum vertex covers is complete for parallel access to NP, Spatially-Dimension-Adaptive Sparse Grids for Online Learning, Maximum Betweenness Centrality: Approximability and Tractable Cases, Stackelberg network pricing is hard to approximate, Algorithms and Complexity of Power Domination in Graphs, On Capacitated Set Cover Problems, Online Maximum k-Coverage, Hardness, Approximability, and Exact Algorithms for Vector Domination and Total Vector Domination in Graphs, Designing Cost-Sharing Methods for Bayesian Games, Unnamed Item, Defending Planar Graphs against Star-Cutsets, Approximability issues of guarding a set of segments, A refined search tree technique for dominating set on planar graphs, Fast distributed algorithms for (weakly) connected dominating sets and linear-size skeletons, The minimum-entropy set cover problem, Efficiently computing succinct trade-off curves, A greedy approximation algorithm for the group Steiner problem, Improved approximation of maximum vertex cover, Steiner Problems with Limited Number of Branching Nodes, Moderately exponential time and fixed parameter approximation algorithms, Unnamed Item, Algorithms for maximizing monotone submodular function minus modular function under noise, <scp>Decomposition‐based</scp> approximation algorithms for the <scp>one‐warehouse multi‐retailer</scp> problem with concave batch order costs, On the correlation gap of matroids, Roman \(k\)-domination: hardness, approximation and parameterized results, FPT-Algorithms for the \(\ell\) -Matchoid Problem with a Coverage Objective, Pseudorandom sets in Grassmann graph have near-perfect expansion, Improved bounds for metric capacitated covering problems, Maximization of nonsubmodular functions under multiple constraints with applications, Distributed strategy selection: a submodular set function maximization approach, Exact algorithms and hardness results for geometric red-blue hitting set problem, Resource time-sharing for IoT applications with deadlines, Real-time passenger bus routing problems with preferences and tradeoffs, Geometric dominating-set and set-cover via local-search, Improved deterministic algorithms for non-monotone submodular maximization, Improved deterministic algorithms for non-monotone submodular maximization, A note for approximating the submodular cover problem over integer lattice with low adaptive and query complexities, On solving simplified diversified top-\(k\,s\)-plex problem, Streaming submodular maximization with the chance constraint, Nash welfare guarantees for fair and efficient coverage, Auditing for core stability in participatory budgeting, Approximation algorithms for capacitated assignment with budget constraints and applications in transportation systems, Hitting geometric objects online via points in \(\mathbb{Z}^d\), Locating service and charging stations, Tight approximation algorithms for ordered covering, Observation routes and external watchman routes, Algorithmic and complexity aspects of problems related to total restrained domination for graphs, Online hitting of unit balls and hypercubes in \(\mathbb{R}^d\) using points from \(\mathbb{Z}^d\), Mathematics of computation through the lens of linear equations and lattices, Constrained hitting set problem with intervals: hardness, FPT and approximation algorithms, Fractionally Subadditive Maximization under an Incremental Knapsack Constraint with Applications to Incremental Flows, Polylogarithmic Approximation Algorithm for k-Connected Directed Steiner Tree on Quasi-Bipartite Graphs, Approximation algorithms for minimum weight partial connected set cover problem, Power domination with bounded time constraints, An approximation algorithm for the partial vertex cover problem in hypergraphs, Improved Budgeted Connected Domination and Budgeted Edge-Vertex Domination, The Limitations of Optimization from Samples, Tight Approximation Bounds for Maximum Multi-coverage, A primer on the application of neural networks to covering array generation, Simple analysis of graph tests for linearity and PCP, Robust Adaptive Submodular Maximization, Improving the Betweenness Centrality of a Node by Adding Links, Some Inapproximability Results of MAP Inference and Exponentiated Determinantal Point Processes, Fairness in Influence Maximization through Randomization, Unnamed Item, Partial Resampling to Approximate Covering Integer Programs, Fast Adaptive Non-Monotone Submodular Maximization Subject to a Knapsack Constraint, Exact Algorithms for Edge Domination, Technical Note—Online Hypergraph Matching with Delays, Moderately Exponential Approximation: Bridging the Gap Between Exact Computation and Polynomial Approximation, Constrained Submodular Maximization via a Nonsymmetric Technique, An Improved Analysis of Local Search for Max-Sum Diversification, Clustering in Hypergraphs to Minimize Average Edge Service Time, Unnamed Item, Unnamed Item, Bicriteria Approximation Tradeoff for the Node-Cost Budget Problem, Unnamed Item, $(2+\varepsilon)$-Sat Is NP-hard, From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More, Unnamed Item, Near-Optimal Disjoint-Path Facility Location Through Set Cover by Pairs, Formulations and Approximation Algorithms for Multilevel Uncapacitated Facility Location, Parallel Repetition of Two-Prover One-Round Games: An Exposition, Stabbing Convex Polygons with a Segment or a Polygon, Manipulation in Games, The Constant Inapproximability of the Parameterized Dominating Set Problem, Coresets for the Nearest-Neighbor Rule, Fractional Set Cover in the Streaming Model., Approximation algorithm for partial set multicover versus full set multicover, Improved Approximation Algorithm for Set Multicover with Non-Piercing Regions., A (1-e^{-1}-ε)-Approximation for the Monotone Submodular Multiple Knapsack Problem, The Maximum Exposure Problem., The Optimal Design of Low-Latency Virtual Backbones, Algorithms for the line-constrained disk coverage and related problems, Helly-type theorems for approximate covering, Election Manipulation on Social Networks: Seeding, Edge Removal, Edge Addition, AN APPROXIMATION ALGORITHM FOR LOCATING MAXIMAL DISKS WITHIN CONVEX POLYGONS, The complexity for partitioning graphs by monochromatic trees, cycles and paths, Minimum Entropy Combinatorial Optimization Problems, Algorithms for the line-constrained disk coverage and related problems, Unnamed Item, A 6/5-Approximation Algorithm for the Maximum 3-Cover Problem, Unnamed Item, Set covering approach for reconstruction of sibling relationships, Unnamed Item, Unnamed Item, Unnamed Item, Efficient algorithms for measuring the funnel-likeness of DAGs, Unnamed Item, Unnamed Item, More efficient queries in PCPs for NP and improved approximation hardness of maximum CSP, On the complexity of the minimum outer-connected dominating set problem in graphs, Approximation for maximizing monotone non-decreasing set functions with a greedy method, Constant-time distributed dominating set approximation, The strong domination problem in block graphs and proper interval graphs, Recent Developments in Algorithmic Teaching, Sequence submodular maximization meets streaming, Approximating Steiner Networks with Node Weights, Domination in Geometric Intersection Graphs, Fast algorithms for maximizing monotone nonsubmodular functions, Analyzing the Optimal Neighborhood: Algorithms for Partial and Budgeted Connected Dominating Set Problems, Unnamed Item, Maximum independent and disjoint coverage, Approximability of covering cells with line segments, Approximation Algorithms for Dynamic Assortment Optimization Models, Online Submodular Maximization with Preemption, Unnamed Item, On Approximating an Implicit Cover Problem in Biology, Hardness of approximate two-level logic minimization and PAC learning with membership queries, Distributed set cover approximation: Primal-dual with optimal locality, A Simple Gap-Producing Reduction for the Parameterized Set Cover Problem, A Tight Approximation for Submodular Maximization with Mixed Packing and Covering Constraints, Maximizing a Monotone Submodular Function with a Bounded Curvature under a Knapsack Constraint, Unnamed Item, Efficient Black-Box Reductions for Separable Cost Sharing, Tight Bounds for Single-Pass Streaming Complexity of the Set Cover Problem, Polynomial-Time Approximation Schemes for Maximizing Gross Substitutes Utility Under Budget Constraints, On Partial Covering For Geometric Set Systems, Preventing Unraveling in Social Networks: The Anchored $k$-Core Problem, Nearly Optimal NP-Hardness of Unique Coverage, Complexities of Some Problems Related to Synchronizing, Non-Synchronizing and Monotonic Automata, Parameterized Algorithms for Generalized Domination, Two Constant Approximation Algorithms for Node-Weighted Steiner Tree in Unit Disk Graphs, A Tight Bound for Stochastic Submodular Cover, Lower bounds on approximating some variations of vertex coloring problem over restricted graph classes, k-Submodular maximization with two kinds of constraints, Parameter Estimation in Epidemic Spread Networks Using Limited Measurements, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, A distributed algorithm for a set cover game, Randomized Parallel Algorithm for Maximizing Nonsubmodular Function Subject to Cardinality Constraint, Approximability of Monotone Submodular Function Maximization under Cardinality and Matroid Constraints in the Streaming Model, Minimum Power Dominating Sets of Random Cubic Graphs