The Optimization and Applications Lab conducts research in the field of optimization theory and applications. We develop and analyze algorithms to find optimal solutions for various problems and apply them to real-world problems. Our main research areas include continuous optimization, combinatorial optimization, machine learning, and data science.

최적화 및 응용 연구실은 최적화 이론 및 응용 분야를 연구합니다. 다양한 문제에 대한 최적해를 찾는 알고리즘 개발 및 분석, 그리고 실제 문제에 적용하는 연구를 수행합니다. 주요 연구 분야는 연속 최적화, 조합 최적화, 기계 학습, 데이터 과학 등입니다.

Dynamic Audit Services for Outsourced Storages in Clouds

Energy Optimization in Multicore Systems with Wake-Up Overhead Awareness

Handling LP-rounding for hierarchical clustering and fitting distances by ultrametrics

Improved algorithms for overlapping and robust clustering of edge-colored hypergraphs: an LP-based combinatorial approach

Improved learning-augmented algorithms and (tight) lower bounds for multi-option ski rental problem

Improved Learning-Augmented Algorithms for the Multi-Option Ski Rental Problem via Best-Possible Competitive Analysis

Value-aware real-time scheduling for intelligent transportation systems

On the connected minimum sum of radii problem

Constant-factor approximation algorithms for parity-constrained facility location and k-center

Facility location is a prominent optimization problem that has guided a large volume of studies in combinatorial optimization. However, unlike other problems, it was not previously known how this problem behaves in conjunction with parity constraints. In this paper, we present the first constant-factor approximation algorithm for the facility location problem with parity constraints. Although the unconstrained facility location problem as a relaxation for the parity-constrained generalization has unbounded gap, we demonstrate that it yields a structured solution whose parity violation can be corrected at small cost.

Constant-factor approximation algorithms for the parity-constrained facility location problem

We present a strengthened version of a lemma due to Bondy and Lovász. This lemma establishes the connectivity of a certain graph whose nodes correspond to the spanning trees of a 2-vertex-connected graph, and implies the k=2 case of the Győri-Lovász Theorem on partitioning of k-vertex-connected graphs. Our strengthened version constructively proves an asymptotically tight O(|V|2) bound on the worst-case diameter of this graph of spanning trees.

A diameter-revealing proof of the Bondy-Lovász lemma

Two-way online correlated selection (two-way OCS) is an online algorithm that, at each timestep, takes a pair of elements from the ground set and irrevocably chooses one of the two elements, while ensuring negative correlation in the algorithm's choices. Fahrbach, Huang, Tao, and Zadimoghaddam first invented OCS to solve the edge-weighted online bipartite matching problem, and posed the following tantalizing open question: Can we obtain n-way OCS for n>2, in which the algorithm can be given n>2 elements to choose from at each timestep? In this paper, we affirmatively answer this open question by presenting a three-way OCS.

Making three out of two: three-way online correlated selection

In the design of real-time systems, it is important to take soft-error tolerance into account. While hardening techniques such as error detection and correction enable us to better tolerate soft-errors, they are inevitably accompanied with execution time overhead. In order to mitigate its impact, Chen et al. proposed to identify the (m, k)-constraints of real-time tasks, which demand that at least m jobs out of k consecutive task invocations must be fault-free, and to design hardening policies based on it. In this paper, we propose a new method to design hardening policies that are adaptive and stochastic. At the heart of our method is a new linear program (LP) formulation that finds an adaptive stochastic policy optimizing the CPU utilization.

Fully adaptive stochastic handling of soft-errors in real-time systems

Approximation algorithms for the bottleneck asymmetric traveling salesman problem

We present the first nontrivial approximation algorithm for the bottleneck asymmetric traveling salesman problem. Given an asymmetric metric cost between n vertices, the problem is to find a Hamiltonian cycle that minimizes its bottleneck (or maximum-length edge) cost. We achieve an O(log n / log log n) approximation performance guarantee by giving a novel algorithmic technique to shortcut Eulerian circuits while bounding the lengths of the shortcuts needed. This allows us to build on the result of Asadpour, Goemans, Mądry, Oveis Gharan, and Saberi to obtain this guarantee.

Dynamic facility location via exponential clocks

We present a new LP-rounding algorithm for facility location problems, which yields the first constant approximation algorithm for the dynamic facility location problem. This problem is a generalization of the classic facility location problem, proposed by Eisenstat, Mathieu, and Schabanel to model the dynamics of evolving social/infrastructure networks. Our algorithm, based on competing exponential clocks, exhibits several properties that distinguish our approach from previous LP-roundings for facility location problems. We demonstrate that these properties enable us to apply our new algorithm to the dynamic problem.

LP-based algorithms for capacitated facility location

Linear programming (LP) has played a key role in the study of algorithms for combinatorial optimization problems. In particular, a variety of LP-based methodologies have been applied to and evolved from the uncapacitated facility location problem. Unfortunately, this collection of powerful techniques had not yet been applicable to the more general capacitated facility location problem. In this paper, we present a linear programming relaxation with constant integrality gap for capacitated facility location. Our algorithmic proof of integrality gap is obtained by finally accessing the rich toolbox of LP-based methodologies: we present a constant factor approximation algorithm based on LP-rounding.

The interaction between the cyber and physical components of CPSs induces delay-workload dependence, creating the unique challenge of power optimization with delay-workload dependence awareness. In this paper, we identify this challenge and present the first formal and comprehensive model to enable rigorous investigations on this topic. We propose a simple power management policy, and show that this policy achieves a best possible notion of optimality. We also experimentally validate the efficiency of our policy.

A formal approach to power optimization in CPSs with delay-workload dependence awareness

Improving Christofides' algorithm for the s-t path TSP

We present a deterministic (1+√5)/2-approximation algorithm for the s-t path TSP for an arbitrary metric. Given a symmetric metric cost between n vertices including two prespecified endpoints, the problem is to find a shortest Hamiltonian path between the two endpoints. The present result surpasses the 20-year-old barrier of 5/3 originating from Hoogeveen's analysis of the natural path-variant of Christofides' algorithm. The present techniques can be applied to other optimization problems as well: these applications include the prize-collecting s-t path problem and the unit-weight graphical metric s-t path TSP.

Centrality of trees for capacitated k-center

There is a large discrepancy in our understanding of uncapacitated and capacitated versions of network location problems. This paper aims to bridge this discrepancy, by presenting a simple algorithm for the capacitated k-center problem. Our algorithm has a clean analysis that allows us to prove an improved approximation ratio of 9, narrowing down the integrality gap of the standard LP relaxation to either 7, 8, or 9. We present extensions of our techniques to related problems, and also give evidence to show that more powerful preprocessing could lead to better algorithms, by giving an approximation algorithm that beats the integrality gap for instances where all non-zero capacities are uniform.

시스템 활성화 오버헤드를 고려한 멀티코어 시스템의 에너지 최적화

그래프 채색 알고리즘의 GPGPU 상 구현 및 최적화

용량 제약이 있는 설비 배치 문제에 대한 휴리스틱 및 선형계획법 완화의 계산적 분석

홀짝성 제약이 있는 k-센터 및 설비 위치 선정 문제에 대한 알고리즘의 효율적이고 강건한 구현

트리의 최적 경로 분할을 위한 다항시간 알고리즘

Recent developments in approximation algorithms for facility location and clustering problems

LP-based approximation algorithms for traveling salesman problems (in Korean)

A Novel Algorithm for Large-Scale Continuous Optimization

Combinatorial Optimization in Logistics Networks

Machine Learning for Predictive Maintenance

Data-Driven Approach for Supply Chain Optimization

Constant-Factor Approximation Algorithms for Parity-Constrained Facility Location and k-Center

Facility location is a prominent optimization problem that has inspired a large quantity of both theoretical and practical studies in combinatorial optimization. Although the problem has been investigated under various settings reflecting typical structures within the optimization problems of practical interest, little is known on how the problem behaves in conjunction with parity constraints.
In this paper, we present the first constant-factor approximation algorithm for the facility location problem with parity constraints. We are given as the input a metric on a set of facilities and clients, the opening cost of each facility, and the parity requirement - odd, even, or unconstrained - of every facility in this problem. The objective is to open a subset of facilities and assign every client to an open facility so as to minimize the sum of the total opening costs and the assignment distances, but subject to the condition that the number of clients assigned to each open facility must have the same parity as its requirement.
Although the unconstrained facility location problem as a relaxation for this parity-constrained generalization has unbounded gap, we demonstrate that it yields a structured solution whose parity violation can be corrected at small cost. This correction is prescribed by a T-join on an auxiliary graph constructed by the algorithm. This auxiliary graph does not satisfy the triangle inequality, but we show that a carefully chosen set of shortcutting operations leads to a cheap and sparse T-join. Finally, we bound the correction cost by exhibiting a combinatorial multi-step construction of an upper bound.

Constant-Factor Approximation Algorithms for the Parity-Constrained Facility Location Problem

Two-way online correlated selection (two-way OCS) is an online algorithm that, at each timestep, takes a pair of elements from the ground set and irrevocably chooses one of the two elements, while ensuring negative correlation in the algorithm's choices. Whilst OCS was initially invented by Fahrbach, Huang, Tao, and Zadimoghaddam to break a natural long-standing barrier in the edge-weighted online bipartite matching problem, it is an interesting technique on its own due to its capability of introducing a powerful algorithmic tool, namely negative correlation, to online algorithms. As such, Fahrbach et al. posed two tantalizing open questions in their paper, one of which was the following: Can we obtain n-way OCS for n > 2, in which the algorithm can be given n > 2 elements to choose from at each timestep? In this paper, we affirmatively answer this open question by presenting a three-way OCS. Our algorithm uses two-way OCS as its building block and is simple to describe; however, as it internally runs two instances of two-way OCS, one of which is fed with the output of the other, the final output probability distribution becomes highly elusive. We tackle this difficulty by approximating the output distribution of OCS by a flat, less correlated function and using it as a safe "surrogate" of the real distribution. Our three-way OCS also yields a 0.5093-competitive algorithm for edge-weighted online matching, demonstrating its usefulness.

최적화 및 응용 연구실

교수님 소개

안형찬

연구실 소개

연구실 키워드

알럼나이가 간 회사

연구실 지원 방법

대우 조건

연도별 논문 인용수

저널 & 학회 논문 출판 수

연구실 논문 목록

Handling LP-rounding for hierarchical clustering and fitting distances by ultrametrics

Improved algorithms for overlapping and robust clustering of edge-colored hypergraphs: an LP-based combinatorial approach

Improved learning-augmented algorithms and (tight) lower bounds for multi-option ski rental problem

연구실 보유 특허

대학별 입시끈

우리 연구실 모집

교수님 소개

안형찬

연구실 키워드

알럼나이가 간 회사

연구실 지원 방법

대우 조건

연도별 논문 인용수

저널 & 학회 논문 출판 수

연구실 논문 목록

Handling LP-rounding for hierarchical clustering and fitting distances by ultrametrics

Improved algorithms for overlapping and robust clustering of edge-colored hypergraphs: an LP-based combinatorial approach

Improved learning-augmented algorithms and (tight) lower bounds for multi-option ski rental problem

연구실 보유 특허

최근 3년간 연구실적 높은 연구실

대학별 입시끈

우리 연구실 모집