Jove
Visualize
Contact Us
JoVE
x logofacebook logolinkedin logoyoutube logo
ABOUT JoVE
OverviewLeadershipBlogJoVE Help Center
AUTHORS
Publishing ProcessEditorial BoardScope & PoliciesPeer ReviewFAQSubmit
LIBRARIANS
TestimonialsSubscriptionsAccessResourcesLibrary Advisory BoardFAQ
RESEARCH
JoVE JournalMethods CollectionsJoVE Encyclopedia of ExperimentsArchive
EDUCATION
JoVE CoreJoVE BusinessJoVE Science EducationJoVE Lab ManualFaculty Resource CenterFaculty Site
Terms & Conditions of Use
Privacy Policy
Policies

Related Concept Videos

Design Example: Analyzing Capacity Contours for Flood Risk Assessment01:17

Design Example: Analyzing Capacity Contours for Flood Risk Assessment

270
Flood risk assessment involves careful planning and analysis to ensure the safety of communities near water retention structures. Capacity contours are a vital tool in this process, as they illustrate the potential spread of water at specific levels in a given area. In the context of building a bund across a small valley, these contours play a critical role in evaluating the safety of nearby residential areas.In this example, the bund is intended to store stormwater in the valley. The engineers...
270
Estimation of the Physical Quantities01:05

Estimation of the Physical Quantities

7.2K
On many occasions, physicists, other scientists, and engineers need to make estimates of a particular quantity. These are sometimes referred to as guesstimates, order-of-magnitude approximations, back-of-the-envelope calculations, or Fermi calculations. The physicist Enrico Fermi was famous for his ability to estimate various kinds of data with surprising precision. Estimating does not mean guessing a number or a formula at random. Instead, estimation means using prior experience and sound...
7.2K
Design Example: Alignment of a Road Line Using GIS01:17

Design Example: Alignment of a Road Line Using GIS

317
The alignment of a road line using Geographic Information Systems (GIS) is a critical process in civil engineering, combining advanced technology with practical decision-making. This methodology begins with the collection of geospatial data, including information on land cover, geomorphology, drainage patterns, slope, and contour details. Such data is typically acquired through satellite imagery and GIS tools, offering a comprehensive understanding of the terrain.Once the data is gathered, it...
317
Maxwell-Boltzmann Distribution: Problem Solving01:20

Maxwell-Boltzmann Distribution: Problem Solving

2.8K
Individual molecules in a gas move in random directions, but a gas containing numerous molecules has a predictable distribution of molecular speeds, which is known as the Maxwell-Boltzmann distribution, f(v).
This distribution function f(v) is defined by saying that the expected number N (v1,v2) of particles with speeds between v1 and v2 is given by
2.8K
Radiation Pressure: Problem Solving01:09

Radiation Pressure: Problem Solving

774
The radiation pressure applied by an electromagnetic wave on a perfectly absorbing surface equals the energy density of the wave. The wave's momentum also gets transferred to the surface when an electromagnetic wave is entirely absorbed by it. The rate at which momentum is transmitted to an absorbing surface perpendicular to the propagation direction equals the force on the surface.
The average value of the rate of momentum transfer divided by the absorbing area represents the average force...
774
Taping Over Different Ground Profiles01:12

Taping Over Different Ground Profiles

317
Taping over varying ground profiles requires careful adaptation to achieve accurate measurements. On smooth, level ground with minimal vegetation, the tape can rest directly on the ground. Here, the taping team, typically consisting of a head and a rear tapeman, coordinates their positions with clear communication. The rear tapeman holds the tape at the starting point and guides the head tapeman toward a range pole placed beyond the endpoint, using hand or voice signals to ensure alignment.On...
317

You might also read

Related Articles

Articles linked to this work by shared authors, journal, and citation graph.

Sort by
Same journal

FullSynesth: Syntenic Reconciliation of a Set of Consistent Gene Trees.

Theory of computing systems·2026
Same journal

Tight Approximation and Kernelization Bounds for Vertex-Disjoint Shortest Paths.

Theory of computing systems·2026
Same journal

Rudin-Shapiro Sums Via Automata Theory and Logic.

Theory of computing systems·2025
Same journal

Prediction and MDL for infinite sequences.

Theory of computing systems·2024
Same journal

On Polynomial Recursive Sequences.

Theory of computing systems·2024
Same journal

Space Lower Bounds for the Signal Detection Problem.

Theory of computing systems·2021
See all related articles

Related Experiment Video

Updated: Jan 10, 2026

Proton Therapy Delivery and Its Clinical Application in Select Solid Tumor Malignancies
08:34

Proton Therapy Delivery and Its Clinical Application in Select Solid Tumor Malignancies

Published on: February 6, 2019

20.9K

The Ground-Set-Cost Budgeted Maximum Coverage Problem.

Irving van Heuven van Staereling1, Bart de Keijzer2, Guido Schäfer1,3

  • 1Networks & Optimization Group, Centrum Wiskunde & Informatica, Science Park 123, Amsterdam, 1098 XG The Netherlands.

Theory of Computing Systems
|November 24, 2025
PubMed
Summary
This summary is machine-generated.

This study introduces a budgeted maximum coverage variant for bid optimization. Researchers developed approximation algorithms, including a fully polynomial-time approximation scheme for specific hypergraph structures.

Keywords:
Approximation algorithmsHypergraphsMaximum coverage problemSponsored searchSubmodular optimization

More Related Videos

Setting Limits on Supersymmetry Using Simplified Models
07:46

Setting Limits on Supersymmetry Using Simplified Models

Published on: November 15, 2013

8.9K
Radiation Planning Assistant - A Streamlined, Fully Automated Radiotherapy Treatment Planning System
08:25

Radiation Planning Assistant - A Streamlined, Fully Automated Radiotherapy Treatment Planning System

Published on: April 11, 2018

15.8K

Related Experiment Videos

Last Updated: Jan 10, 2026

Proton Therapy Delivery and Its Clinical Application in Select Solid Tumor Malignancies
08:34

Proton Therapy Delivery and Its Clinical Application in Select Solid Tumor Malignancies

Published on: February 6, 2019

20.9K
Setting Limits on Supersymmetry Using Simplified Models
07:46

Setting Limits on Supersymmetry Using Simplified Models

Published on: November 15, 2013

8.9K
Radiation Planning Assistant - A Streamlined, Fully Automated Radiotherapy Treatment Planning System
08:25

Radiation Planning Assistant - A Streamlined, Fully Automated Radiotherapy Treatment Planning System

Published on: April 11, 2018

15.8K

Area of Science:

  • Combinatorial Optimization
  • Algorithm Design
  • Computational Complexity

Background:

  • The budgeted maximum coverage problem is a fundamental NP-hard problem with applications in various fields.
  • A natural variant is introduced where vertex costs, rather than hyperedge costs, are considered within a budget constraint.
  • This problem is motivated by applications in sponsored search auctions, specifically bid optimization.

Purpose of the Study:

  • To investigate a novel variant of the budgeted maximum coverage problem with vertex costs.
  • To develop efficient approximation algorithms for this problem.
  • To analyze the approximability of the problem and identify conditions for exact or near-exact solutions.

Main Methods:

  • The study employs techniques from approximation algorithms and complexity theory.
  • Reductions from known hard problems like Densest k-Subgraph are used to establish inapproximability results.
  • Specific algorithmic approaches are developed for different classes of hypergraphs, including greedy strategies and dynamic programming.

Main Results:

  • The problem is shown to be at least as hard as the standard budgeted maximum coverage problem, implying [Formula: see text]-inapproximability.
  • A [Formula: see text]-approximation algorithm is presented for general graphs.
  • A fully polynomial-time approximation scheme (FPTAS) is derived for hypergraphs whose incidence graphs are forests (Berge-acyclic), with extensions for fixed feedback sets.
  • A [Formula: see text]-approximation algorithm is provided for general hypergraphs based on maximum vertex degree.

Conclusions:

  • The developed algorithms offer significant improvements for specific instances of the budgeted maximum coverage problem.
  • The findings provide a theoretical understanding of the problem's complexity and its practical implications for bid optimization.
  • Future work could explore further extensions and applications of these algorithmic techniques.