LAB LOGA page on LabLog, a review site (not the lab's official page)
Applied Mathematics Division (Kobayashi) Lab
Machine-translated · View original
A lab that studies, from a theoretical standpoint, algorithms that efficiently solve discrete optimization problems.
AboutAbout the lab
Exploring the boundary of what can be solved efficiently.
The Kobayashi Lab studies the theory of algorithms for discrete optimization problems.
Discrete optimization problems ask for maximizing or minimizing some measure over discrete structures such as networks and graphs, and they appear in every part of modern society.
The lab investigates where the essential difference lies between problems that can be solved efficiently (solvable in polynomial time) and hard problems.
It works on the design and theoretical analysis of efficient algorithms, mathematical proofs of hardness, and the construction of mathematical frameworks that encompass a wide variety of efficiently solvable problems.
Key terms
- Discrete optimization problem
- A problem of choosing, from among discrete values or combinations, the one that maximizes or minimizes a given measure. Also called a combinatorial optimization problem
- Polynomial-time algorithm
- An efficient computational procedure whose running time is bounded by a polynomial in the input size
- Matroid
- A combinatorial structure that abstracts the notion of "independence" shared by things such as the linear independence of vectors
NewsLab news
Research group proves the "5/6 conjecture" on round-robin allocation using mathematics and computers
ResearchResearch themes
The lab conducts theoretical research on algorithms for discrete optimization problems. It investigates the essential difference between problems that can be solved efficiently and hard problems, and works on the design and theoretical analysis of more efficient algorithms, mathematical proofs of hardness, and the construction of mathematical frameworks that encompass a wide variety of efficiently solvable problems.
*Illustrative imageWeighted linear matroid parity problem
In joint research, the lab gave the first polynomial-time algorithm, using a primal-dual algorithm and the combinatorial relaxation method.
*Illustrative imageNetwork robustness and optimization
The lab studies algorithms for optimization problems that model the robustness and fault tolerance of networks.
MembersFaculty
- Associate ProfessorYusuke Kobayashi
VoicesStudent voices
Ratings and reviews reflect the experiences of individual current or former students, not the lab's official views. Whether a lab has reviews, or how many, says nothing about the lab itself.
Students who take part in an interview may receive a thank-you gift worth ¥1,000, regardless of what they say.
Student ratings (0 students)
--
--
--
--
--
--
Student voices answer questions like these
- What's great about this lab?
- What did you learn after joining?
- What's the vibe, and what is the professor like?
- Who is this lab for?
- Where do graduates go?
Your experience can help younger students choose their lab. Your name won't be shown.
Write a lab reviewAnonymous · Your draft is saved if you stopRelatedLabs similar to Applied Mathematics Division (Kobayashi) Lab
Applied Mathematics Lab (Kazuhisa Makino)Research Institute for Mathematical Sciences, Division of Applied Mathematical SciencesApplied mathematics and computational science / discrete mat…
Applied Mathematics Division (Kawamura) LabResearch Institute for Mathematical Sciences, Division of Applied Mathematical SciencesComputer science / theory of computation (computability and …
Applied Mathematics Lab (Masahito Hasegawa)Research Institute for Mathematical Sciences, Division of Applied Mathematical SciencesComputer science / theoretical computer science, software sc…
Isono LabResearch Institute for Mathematical Sciences, Division of Applied Mathematical SciencesAnalysis / operator algebras and ergodic theory (von Neumann…The information on this page is compiled by the LabLog team from the lab's public information and interviews. For corrections or removal requests, please contact LabLog, not the lab.
Report an errorAbout the images
The top and research theme images are illustrative and were not taken at the lab. They are cropped from Wikimedia Commons images. Cropped CC BY-SA images are provided under the same CC BY-SA license as the original (version shown on each line).
- Top image: “Graph-matroid” Didia / CC BY-SA 4.0 (cropped)
- Weighted linear matroid parity problem: “Vektoren-matroid” Didia / CC BY-SA 4.0 (cropped)
- Network robustness and optimization: “Network-graph” Savionasc / CC BY-SA 4.0 (cropped)
- Related lab (Applied Mathematics Lab (Kazuhisa Makino)): “B functies 2var versie02” Bob.v.R / CC BY-SA 4.0 (cropped)
- Related lab (Applied Mathematics Division (Kawamura) Lab): “Turing Machine” Porao / Public domain (cropped)
- Related lab (Applied Mathematics Lab (Masahito Hasegawa)): “Kleisli Category - morphism composition” AugPi / CC BY-SA 4.0 (cropped)
- Related lab (Isono Lab): “Bernoullishift” Andreas Mandl / CC BY-SA 3.0 (cropped)
About LabLog
LabLog is a lab review app for students only. Student members at each university interview students in labs and publish what they say. Student voices can only be read by students who sign up with a university email address. Operated by bestiee Inc.
Learn more about LabLog ↗Search engines and AI may reference the basic lab info and rating summaries on this page and the description of LabLog. Student voices are for student members only. Automated collection by programs (scraping, or input to or training of AI) is prohibited under Article 8 of the Terms of Service. If you need data for research or analysis, please contact us.