Related Experiment Video
Updated: May 2, 2026
07:12
Using Informational Connectivity to Measure the Synchronous Emergence of fMRI Multi-voxel Information Across Time
Published on: July 1, 2014
12.3K
An FPTAS for Connectivity Interdiction
Chien-Chung Huang1, Nidia Obscura Acosta2, Sorrachai Yingchareonthawornchai3
1Department of Computer Science, École Normale Supérieure, Paris, France.
Mathematical Programming
|May 1, 2026
Summary
This study provides a fully polynomial-time approximation scheme (FPTAS) for the connectivity interdiction problem. Faster exact and approximation algorithms are also developed for unit edge costs, advancing graph cut research.
Area of Science:
- Graph Theory
- Combinatorial Optimization
- Computer Science
Background:
- The connectivity interdiction problem involves minimizing remaining edge weights after removing edges under a budget.
- This NP-hard problem is a generalization of the knapsack problem.
- Prior work established a polynomial-time approximation scheme (PTAS) and exact algorithms for unit edge costs.
Purpose of the Study:
- To determine if a fully polynomial-time approximation scheme (FPTAS) is achievable for the general connectivity interdiction problem.
- To develop faster exact and approximation algorithms for the special case of unit edge costs.
Main Methods:
- Establishing a connection to a novel intermediate problem: the normalized min-cut.
- The normalized min-cut problem penalizes remaining edge weights based on the number of edges removed for free.
Main Results:
- An affirmative answer to the existence of an FPTAS for the general connectivity interdiction problem.
- Development of improved exact and approximation algorithms for the unit edge cost variant.
Conclusions:
- The FPTAS for the connectivity interdiction problem is now established.
- The normalized min-cut provides a key technical advancement for solving related graph cut problems.
More Related Videos
09:36Continuous-Wave Propagation Channel-Sounding Measurement System - Testing, Verification, and Measurements
Published on: June 25, 2021
2.7K
07:49Automated Deployment of an Internet Protocol Telephony Service on Unmanned Aerial Vehicles Using Network Functions Virtualization
Published on: November 26, 2019
9.7K
Related Concept Videos
01:15Thevinin's Theorem
2.2K
Thévenin's theorem plays a pivotal role in electrical circuit analysis, offering a solution to the challenges posed by variable loads within a circuit. In practical applications, it is common to encounter circuits where certain elements remain fixed while others fluctuate, often referred to as the "load." A typical household electrical outlet serves as a prime example of a variable load, as it can be connected to a variety of appliances, each with its own unique electrical characteristics.
2.2K
01:10Interference: Path Lengths
2.5K
Consider two sources of sound, that may or may not be in phase, emitting waves at a single frequency, and consider the frequencies to be the same.
Two special sources may be considered when they are in phase. This can be easily achieved by feeding the two sources from the same source. An example would be synchronizing the two speakers by feeding them with the same source, such as the sound waves produced by a tuning fork. This setup ensures that the two sources have the same frequency and are...
Two special sources may be considered when they are in phase. This can be easily achieved by feeding the two sources from the same source. An example would be synchronizing the two speakers by feeding them with the same source, such as the sound waves produced by a tuning fork. This setup ensures that the two sources have the same frequency and are...
2.5K
01:26Reclosers and Fuses
685
Automatic circuit reclosers enhance the protection of distribution circuits by interrupting and auto-reclosing an AC circuit according to a preset sequence. They effectively manage temporary faults on overhead distribution lines, often caused by tree limbs or wildlife, by briefly disrupting service to improve overall reliability. However, contact with reclosers or energized broken conductors on the ground can pose serious hazards.
A comprehensive protection scheme for radial distribution...
A comprehensive protection scheme for radial distribution...
685
01:23Transmission Line Design Considerations
815
Aluminum has become the material of choice for overhead transmission lines, surpassing copper due to its abundance and cost-effectiveness. The most prevalent type is the aluminum conductor, steel-reinforced (ACSR), which combines aluminum strands around a steel core. Other variants include all-aluminum conductors (AAC), all-aluminum alloy conductors (AAAC), aluminum conductor alloy-reinforced (ACAR), and aluminum-clad steel conductors. Advanced designs, such as aluminum conductors with steel...
815
01:41Social Traps
20.5K
Social traps are negative situations where people get caught in a direction or relationship that later proves to be unpleasant, with no easy way to back out of or avoid. The concept was orignally introduced by John Platt who applied psychology to Garrett Hardin's "Tragedy of the Commons", where in New England herd owners could let their cattle graze in the common ground. This situation seems like a good idea, but an individual could have an advantage. If they owned...
20.5K
01:23Circuit Breaker and Fuse Selection
747
A circuit breaker is a device engineered to interrupt fault currents and sometimes reclose automatically. When a fault current is detected, the breaker separates the electrical contacts, which generates an arc. This arc is extinguished by methods such as elongation, cooling, or splitting, depending on the breaker's design. Breakers are categorized based on the voltage they operate at and the medium used for arc extinction, such as air, oil, SF6 gas, or vacuum.
In high-voltage systems,...
In high-voltage systems,...
747