Exercises
Multiple Choice
Articles
Open Problems
Login
4 exercises
Subject:
Optimization
Start over
- to expand, or dig in by adding more tags and revising the query.
Sort By:
trending ▼
date
0
Graduate
By
Shiva Kintali
on Sept. 11, 2012 | Updated Dec. 6, 2017
Vertex cover in bipartite graphs
The Vertex Cover of a graph \(G(V,E)\) is a set of vertices \(S \subseteq V\) such that each edge of the graph is incident to at least one vertex of the set \(S\). Minimum cost vertex cover : Given a…
Mathematics
Optimization
Graph Theory
Linear Programming
bipartite graph
vertex cover
0
Graduate
By
Shiva Kintali
on June 9, 2012 | Updated Dec. 6, 2017
Minimum edge cover vs Maximum matching
An edge cover of a graph \(G(V,E)\) is a subset \(F \subseteq E\) of edges such that every node is incident to at least one edge in \(F\). Show that a minimum cardinality edge cover can be determine…
Mathematics
Optimization
Graph Theory
Linear Programming
edge cover
matching
reduction
0
Graduate
By
Shiva Kintali
on June 6, 2012 | Updated Dec. 6, 2017
Perfect Matchings in Cubic Graphs
Let \(G\) be a cubic graph with no cut-edge. Let \(PM(G)\) be the convex hull of the perfect matchings of \(G\). Prove that the vector \((1/3, 1/3, \dots, 1/3) \in PM(G)\). Prove that every two-conn…
Mathematics
Optimization
Combinatorial Optimization
Graph Theory
matching
0
Undergraduate
By
Shiva Kintali
on June 9, 2012 | Updated Dec. 6, 2017
Linear inequalities satisfied with equality
Let \(Ax \leq b\) be a system of linear inequalities. Describe a linear program to determine which inequalities among \(Ax \leq b\) are always satisfied with equality.
Optimization
Linear Programming
optimization
icon
Sign In or Sign Up
icon
Invite Friends
Post Something
x
Select What You'd Like To Post
POST AN ARTICLE
POST AN OPEN PROBLEM
POST AN EXERCISE
POST A MULTIPLE-CHOICE QUESTION
Content Types
Articles
Open Problems
Exercises
Multiple-Choice Questions
Levels
High school
Undergraduate
Graduate
Subjects
Mathematics
Computer Science
Puzzles
Optimization
Trending tags
trees
dynamic programming
polynomials
infinite series
counting
complete graph
crossing number
planar graphs
extremal graph theory
graph cut
Topics
Algebra
Algorithms
Approximation Algorithms
Calculus
Combinatorial Optimization
Combinatorics
Complexity Theory
Data Structures
Discrete Mathematics
Game Theory
Geometry
Graph Theory
Linear Algebra
Linear Programming
Logic
Mathematical Analysis
Mathematics
Matrix Theory
Number Theory
Optimization
Probability
Programming
Puzzles
Randomized Algorithms
Real Analysis
Trigonometry
×